Question

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 q = 383, so that the modulus is N = 21 5629. She also chooses the encryption key e-49. She posts the num- bers N = 215629 and e-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 N = 563-383, compute a decryption key d for Alice, so that M mod 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 21 5629. He then encrypts M, again to generate M2 = M49 mod 215629, And so on. Thus Henry computes the sequence Mi, M2, ..., defined recursively by: def M49 mod 215629 for i = 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 M49 mod 215629 Bob sends to Alice, the hacker Henry will always observe that M10 M (c) Having observed that M10-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 inteo

Answer 1

a) The inverse of c is d such that e^* d (mod phi (N)) = 1 here N = 215629 and we know that N = 563 * 383 phi (N) = phi (p *q) = phi (p) * phi (q) = (p - 1) * (q - 1) = 562*382 = 214684 so we need to find d such that 49 * d = 1 (mod 214684) d = 56957 b) since M_10 = m^49 times 10 (mod 215629) = M (mod 215629) Since 49^10 mod (214684) = 1, where 214684 = phi (215629) So irrespective of M, always M_10 = M c) since M_10 = m^49 times 10 (mod 215629) = M (mod 215629) m 49 times 11 (mod 215629) = m^49 (mod 215629) we have M_4 m^49 times 10 (mod 215629) From therevalues He wry will calculate M.