You have to write a program (in the language of your choice) 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 discussed in class and the textbook; you will get partial credit if you implement the simple, inefficient and straightforward method for modular exponentiation.

(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. A softcopy of the program needs to be turned in on blackboard. Both your program and the output should be easy to understand.