Problem 6 (12 pts) RSA encryption. Assume that the message space consists of all 24-bit non-negative integer numbers. We use N = 60529591 for RSA encryption. a (3 pts) Write a program that computes p and q such that pq = N = 60529591. Provide the values of p, q, and the value of (N). 2 b (3 pt) We choose e = 31. Provide the value of d such that (ed mod 0(N)) = 1. (The algorithm for doing this is known as the extended Euclidean algorithm. If you do not know the algorithm, and do not want to learn the algorithm yourself, you can use an inefficient method such as enumerating over all positive integer numbers less than $(N) and checking which one satisfies the requirement. For large N, this inefficient method takes too long time; but for the number here, it should be fast enough.) c (0 pt) If you are unfamiliar with RSA, write a program that loops through all value x's such that isxs N 1, to verify that (xed mod N) - = x. This is just to help convince yourself that RSA decryption works. Hint: When computing x mod N, directly computing r may overflow the representation of integers you have. You can use the Square and Multiply method, which exploits the fact that xab mod N = (x mod N) mod N. You can also exploit the fact that xy+1 mod N = (x4 mod N)x mod N. d (3 pts) For each of the following ciphertexts 10000, 20000, 30000, 40000, 50000, 60000, show the decrypted message, as a base-10 number. Here we allow these messages to be beyond a 24-bit integer. e (3 pts) Describe how an adversary can recover any message encrypted in this way without factor- ing N. That is, the message space remains the same. However, the value of N is so large that factoring it becomes infeasible