Crypto Have fun with RSA 1 Intro RSA RSA s one the widely used public key cryptosystem in real world It's composed of three algorithms key generation (Gen) encryption (Enc). and decryption (Dec). In RSA the public key is pair of integers (e,N), and the private key s an integer d. Gen The key pair generated by the following steps: 1. Choose two distinct big prime numbers with the same bit sizesay and q. 2. Let N p*q and o(N) (p- 1) ( (g - 3. Pick up an integer such that 4. Get the modular inverse ofe: mod d*c=l moo ((N)). 5. Return (N,c) public key, and das private key. Enc Conerypt integer m with public key the cipher integer m² mod N Dec To decrypt cipher d,the integer emod N. 2 Taskl Get Familiar with RSA The goal of this familiar with RSA. You're given RSA key and unique message You're required toget the student key pair cipher text can be found in You're only required 3 Task2 Attack Small Key Space In real world. he commonly used RSA key size 1024 bits. which Is hard for attackers traversal the whole space with limited Now you're given unique RSA public which pretty small (64 bits). your goal is to get the private key. All public found in You're required write some in get the private key: . TODOI: implement get factors. n s the given public key (64 bits). your goali get its factors. You this subtask (i.e., search engine pencil and paper) as long you get the right def get ,factors(n): # your starts here # your code ends here return (p. q) . TODO2: implement function get the private key. def get key(p. 9. e): d = 0 # your code starts here # your code ends here return You're required osubmit: (1)your unique private keyi hex format (2) the "get_pri_key.py" file;(3) briefdescriptionabout your private key. 4 Task3 Where Is Waldo? Read paper "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices" You're given unique RSA public key the RNG (random number generator) used in the key Also. all your classmates's public kevs are generated by the same RNG o the same system. Your goal is to get your unique private key. All keys can found in You're required to complete some code in "find. toget the private key: . TODOI: implement function nl your own key. n21 one of your class- mate's key tryto find out whether this classmate Waldo, def is .waldo(n1 n2): result False #your code stert here #your code ends here return result TODO2: since you've successfully found your Waldo among your classmates now you have implement function get,private.key toget your own unique private key. nlis your public key, n2is Waldo's public key def get_privatekey (nl, n2, e): #your code sterts here #your code ends here return You're required submit (1) your unique private key in hex format; (2) your class- (Walde) name: (3) the areldo.pg file: your about weak key problem caused by Ps and Qs: (5) simple description about your steps get the private kev. 5 Task4 Broadcasting RSA Attack A message was encrypted with three different 1024 bit RSA public keys, all of them have public exponent resulting thrve different encrypted messages You'regiven three pairs ofpublic kevs and encrypter messages, pleasi the original message You're required implement the frecover msg function "recover .py": def recover msg(nl, n2, n3, c1, c2, c3): - 42 # your code sterts here: to calculate the original message m . Nole "m' should be en integer # your code ends here # comvert the iml 10 message string ISS = hex(m).rstripC'L')[2:].decode('hex') return msg You're required submit the original message, your understanding about the attack and brief explanation about how you recover the message.