Try doing this with a friend. Nothing to hand in. Going through this exercise will help
you do the Being Eve assignment.
The people at your computer should partner with the people at a nearby computer. One computer
will by 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). Recall that 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?