Write a program in Python implement the RSA algorithm for cryptography.

Set up:

1.Choose two large primes, p and q. (There are a number of sites on-line where you can find large primes.)

2.Compute n = p * q, and = (p-1)(q-1).

3.Select an integer e, with 1 < e < , gcd(e, ) = 1.

4.Compute the integer d, 1 < d < such that ed 1 (mod ). The numbers e and d are called inverses (mod ). To do this, I suggest two possibilities:

a)Research the BigInteger class in Java. It has a method to compute inverses modulo a specified number. (It also has other methods that would be useful!)

b)Look up the Extended Euclidean Algorithm. This is an algorithm to find d. Save this number d in a constant or variable.

5. (Make n and e public)

Encryption:

1. Convert the message into numbers, using the ASCII representation for characters. (For example, in ASCII, A = 65, B = 66, ... , space = 32, period = 46. You may find an ASCII table online.)

2. Obtain the public key (n, e) of who you want to send a message to. (You should choose yourself for testing purposes. Then try a classmate's.)

3. Encipher each letter (now a number, say m) by computing c m^e (mod n).

Decryption:

1.When you receive a string of numbers, such as 1743 452 625, use your private key d to compute 1743^d (mod n), 452^d (mod n) and 625^d (mod n). This n is from your public key.

2.Take the results of these and translate back into letters, using the same scheme as above.