For this assignment well be creating a public and private key for the RSA cryptosystem, and then decrypting a message which was encrypted using your public key.

You can use your book, your notes, a calculator, and WolframAlpha (or write a program! If you do, include your source with the solution) to complete this assignment.

Pick two primes. For the purposes of this assignment, lets keep them relatively small: p, q < 10,000, (but each larger than 55 so that n > 2525). (I also expect you generate them yourself. I wont accept the primes we use in this activity, the text, or class examples). The primes are private.

Determine n = pq. This is public information.

Now compute two numbers:

Pick your encryption exponent e, which is relatively prime to (p-1)(q-1).

Compute your decryption exponent d, which is the inverse of e modulo (p-1)(q-1). I.e. de = 1 (mod (p-1)(q-1)). d is private.

Record all your information (p, q, n, e, d) somewhere. If you lose your decryption exponent, you cant complete the assignment, so you will receive a zero grade.

Email me (n, e). This is your public key. For convenience (and since Ive written a program to partially automate it) please use the following form when you email me:

n = 1234567

e = 751

Ill come up with some message to send.

Youll receive a message which is in blocks (depending on the size of n, theyll be blocks of 4, if key is less than 252525 or of size 6, since n should be less than 25252525).

Your task is to decode the message using your private key (n, d) in the RSA decryption algorithm. Email me back with the decoded message in English, adding correct spacing to separate the words.

For example, using the above (n, e), youd receive:

Ciphertext: 347306 945459 293142 584584 347306 945459 1025846 601607

And youd decrypt, decode (KEEPITSECRETKEEPITSAFEXX), and email me / send me a Slack DM back:

KEEP IT SECRET KEEP IT SAFE

(and your source code if you created a program to do it).

I want the English decrypted statement. Please no padded Xs.

Please explain this thoroughly!!