RSA worksheet

Back
RSA Secret-Sharing Worksheet
Step 1: Calculations

Pick two small prime numbers (<30 or so), P and Q. Keep these secret: P = _____ Q = _____.
Find the number Z = (P-1)*(Q-1): Z = _________. Keep Z secret, too.
Find the number N = P*Q: N = _________. You will want to publicize N.
Now, pick a public-key exponent E, such that E has no common factors with Z: E = _________.
Finally, find your secret private-key exponent D. To do this, find the number D such that E*D (mod Z) = 1 — this is in general not easy by hand but can be done by a computer using the Euclidean algorithm. Ask Treven for help if you want it!): D = _________

Step 2: Secret sharing

Find another team with whom you want to exchange messages, and tell them your modulus N and your public-key exponent E. They should also tell you their modulus (call it M) and their public-key exponent (call it F). Their key: M = _______, F = ________.
To send a (short) message, convert it to numbers using the guide:
Thus, if your message is "Hi!", that corresponds to (35, 11, 66). If any of the numbers in your message is larger than M, you need to pick a different letter or symbol.

Your message: ____ ____ ____ ____ ____ ____

Its numerical equivalent: ____ ____ ____ ____ ____ ____

For each number L in your message, calculate L^F (mod M) (each letter must be encrypted separately since our numbers are so small). Use the repeated squaring method from last time to do this.

Your encrypted message: ____ ____ ____ ____ ____ ____
Then, give your encrypted message to the team from whom you got M and F. They should give you a sequence of numbers as well.

Their encrypted message: ____ ____ ____ ____ ____ ____
Now, to decrypt their message, use your secret exponent D. For each number L in their message, compute L^D (mod N). This will reveal the numbers in their original message!

Their decrypted message: ____ ____ ____ ____ ____ ____
Now, look up in the table to see what they sent you in English:

Their message: ____ ____ ____ ____ ____ ____