You have to write a program in PYTHON which will trace the execution of the RSA cryptosystem on a simple example. Make sure that you take the modulo after every operation i.e. it is not enough just to take the modulo after a long string of operations because the numbers can get so big that you get an overflow error.

(a) Alice choses her two primes to be p = 29 and q = 17 and multiplies them to obtain n = 493. Next, Alice randomly choses e = 15. Alice makes e and n public.

(b) You first need to calculate what Alices secret d will be. Your program should compute (n) = (p1)(q 1), and then your program should find the unique integer d (using brute force search here is OK) such that d is between 1 and n 1 and d e mod (n) = 1.

(c) The cleartext message Bob wishes to send to Alice is M = 28. Bob looks up Alices public e and n, and then calculates (your program should do this) C = Me mod n. For full credit you should implement the fast divide and conquer modular exponential method.

(d) Alice receives the ciphertext C. She will then use her secret d to decipher Bobs message by calculating (your program should do this) M0 = C d mod n. If you have done this correctly, the decoded message M0 should come out equal to the original message M. Again, for full credit you should implement the fast, divide and conquer modular exponential method.

(e) Your program should print out the following values; p, q, n, (n), e, d, M, C, M0 .

(f) Turn in the program listing (a print out of your program) and a print out of your programs output. Please use comments on the code and explain the steps for easy to understand