2. Alice is a student in CSE20. Having learned about the RSA cryptosystem in class, she decides to set-up her own public key as follows. She chooses the primes p=563 and 9-383, so that the modulus is N - 215629. She also chooses the encryption key e-49. She posts the num bers N - 215629 ande - 49 to her website. Bob, who is in love with Alice, desires to send her messages every hour. To do so, he chooses his messages m such that gcd(m, N) 1 and encrypts them as follows: M-m49 mod 215629, duly using the public key posted by Alice (a) Using the knowledge that N563 383, compute a decryption key d for Alice, so that M"-mmod 215629. (Hint: the Euclidean algorithm is helpful here.) A hacker Henry intercepts the encrypted messages. He does not want to bother factoring the modulus N - 215629. Instead, he mounts the following attack on Alice's cryptosystem. Given the encrypted message M, he encrypts it again to generate M1 - M49 mod 215629. He then encrypts M again to generate M2 - Mi mod 215629. And so on. Thus Henry computes the sequence Mi,M2, ..., defined recursively by: 49 def etMa9 mod 215629 for 1-1,2, At each step, Henry checks whether Mi - M, where M is the original encrypted message. If this happens he is in luck, as we shall now see (b) Prove that no matter what message Mm49 mod 215629 Bob sends to Alice, the hacker Henry will always observe that M10- M (c) Having observed that M1o- M, Henry can now recover Bob's message m from its encrypt- ed version M. How does he do that? Note: In part (b), you might need to use a program that makes it possible to handle very large integers. Some examples are MATHEMATICA (or WOLFrAMALPHA), MAPLE, and bc on Unix