CSE 107 Homework 3

This homework is due Wednesday, July 23, at 23:59.
In this problem set, you'll first review how Diffie-Hellman key exchange works. Then you'll implement an algorithm that solves the discrete log problem mod p faster than brute-force (but still not fast enough to be practical when p is very large). Finally, you'll use your discrete log solver to break the security of a Diffie-Hellman handshake that uses an unsafely-small value of p.

Warmup: Finish the Diffie-Hellman handshake! (1 point)

You and Alice are using Diffie-Hellman key exchange to agree on a shared secret key. The prime modulus p and generator g have already been agreed on.
Alice has sent you g^a mod p. You've chosen your secret value b at random. What do you send to Alice? And what is your shared secret with Alice?

Finding discrete logs mod p in O(sqrt p) time (5 points)

Recall that, given g, p, and X = g^x mod p, the discrete log problem is to recover the value of x. For appropriately chosen p, it's believed to be hard, and an efficient way to find discrete logs would let you break much of modern cryptography.
A brute-force approach for solving the discrete log problem would be to try all possible values of x until you find one where g^x = X mod p. This would take O(p) time.
In Monday's lecture, we covered an algorithm called Baby-Steps-Giant-Steps that solves discrete log in O(sqrt(p)) time and O(sqrt(p)) space. This is much faster than brute force.
Your task is to implement the Baby-Steps-Giant-Steps algorithm. You'll use it in the next question to break a Diffie-Hellman handshake that uses too small a value of p.

Breaking Diffie-Hellman by breaking discrete log (4 points)

You're the attacker Eve, eavesdropping on Alice and Bob's communication. Alice and Bob just ran Diffie-Hellman to agree on a shared secret. Then, using the Diffie-Hellman shared secret to derive a symmetric encryption key, Alice encrypted a message and sent the ciphertext to Bob.
If Alice and Bob had chosen the Diffie-Hellman modulus p correctly, this would be secure. Unfortunately for Alice and Bob, the prime p they used was much too small.
Your task is to recover the plaintext (i.e., find the shared secret and then decrypt the ciphertext Alice sent to Bob) in O(sqrt(p)) time.
p is large enough that brute force will be too slow to run on the autograder, but your O(sqrt(p))-time discrete log solver from the previous question will be fast enough!

Submitting the homework

Download the hw3.py python file and fill in the appropriate functions. You can test your code by running it locally (e.g. python3 hw3.py); as long as it runs in less than about, say, 30 seconds, it should be fast enough for the autograder. If you have into issues running your code locally, please contact us! And feel free to come to office hours or post on piazza if you have questions or are stuck!