Diffie Hellman and RSA by hand

Nothing to hand in

The people at your computer should partner with the people at a nearby computer. One computer will be Alice and the other will be Bob. You can send your messages via Slack direct message or sliding pieces of paper across the table or whatever works for you.

To do the computations you need to do, I recommend running python or python3 in interactive mode (just type "python3" at the command line):

Alternatively, you can use "python3 -c" to run arbitrary code, like this:

Fortunately, python's integer arithmetic supports arbitrary integer sizes, so you don't need to worry about your integers getting too big.

Diffie Hellman

• Start by agreeing that g = 13, p = 59.
• Alice: pick a secret number X < p. Don't send it to Bob.
• Bob: pick a secret number Y < p. Don't send it to Alice.
• Alice: send A = gX mod p to Bob.
• Bob: send B = gY mod p to Alice.
• Alice: compute BX mod p. That's your shared secret.
• Bob: compute AY mod p. That's your shared secret.
• Go ahead and compare. Did you both end up with the same shared secret? If not, try to figure out what went wrong.

RSA

• Alice:
  • Pick two prime numbers pA and qA and compute nA = pAqA. Make sure that nA > 128. (Note: this 128 constraint isn't about RSA generally—it's just to make this current exercise work.)
  • Compute λ(nA) = lcm(pA - 1, qA - 1), where lcm(a, b)  is the least common multiple of a and b.
  • Pick 1 < eA < λ(nA)  such that gcd(e, λ(nA)) = 1, where gcd(a, b)  is the greatest common divisor of a and b.
  • Find an integer dA such that eAdA mod λ(nA) = 1.
  • Share (eA, nA)  with Bob. This ordered pair is your RSA public key.
  • Keep (dA, nA)  secret. This ordered pair is your RSA private key.
• Bob:
  • Pick two prime numbers pB and qB and compute nB = pBqB. For this exercise, make sure that nB > 128.
  • Compute λ(nB) = lcm(pB - 1, qB - 1).
  • Pick 1 < eB < λ(nB)  such that gcd(e, λ(nB)) = 1.
  • Find an integer dB such that eBdB mod λ(nB) = 1.
  • Share (eB, nB)  with Alice. This ordered pair is your RSA public key.
  • Keep (dB, nB)  secret. This ordered pair is your RSA private key.
• Alice: write a very short message for the other person, and write it as a sequence of ASCII values. (For example, "Hi!" becomes 72 105 33.) For each number x in the sequence, compute xeB mod nB. That is, you're applying Bob's public key to each character in the message. Finally, send Bob the sequence of numbers you ended up with. That is, send Bob the ciphertext you computed from the original plaintext message.
• Bob: take each integer y in Alice's ciphertext and compute ydB mod nB. That is, apply your private key to the encrypted message to get the decrypted original back. Use the ASCII chart ot translate the plaintext sequence of integers back into a character string.
• Alice and Bob: switch roles, with Bob sending a message to Alice encrypted using Alice's public key.

Observations about this use of RSA

• IMPORTANT. READ THIS! Encrypting one character at a time is insecure. By encrypting each character separately, we essentially used a complicated procedure to create a simple substitution cipher, like the ones used in the cryptogram puzzles you can find in many newspapers and online. These tend to be very easy to decrypt using letter frequencies and a dictionary. So don't use RSA on one letter at a time.
• RSA is slow. The "exponentiation mod n" operation is slow, especially compared to the operations performed in a typical symmetric cipher like AES. So RSA is seldom used to encrypt an entire message. Rather, you might use RSA to send an AES encryption key from Alice to Bob, and then use AES to encrypt the message. (Even that approach, though computationally faster, has its own problems. We'll discuss this further as we learn more about the applications of public key cryptography.)
• Key exchange is a problem. How can Alice be sure that she has the real public key that Bob intends for her to use?