CSci 4554 Lab 4: Diffie-Hellman key exchange

Due Wednesday, April 12 at 11:59pm (by e-mail)

Overview and background

This lab is done in groups of 2 or individually.

The purpose of the lab is to implement cryptographic algorithms based on the DLP problem and attacks on them.

1. Each group finds a partner group (feel free to form cycles of three groups)
2. Each group generates at least two Diffie-Hellman public keys:
1. Choose a safe prime p greater than 1000000000. A safe prime is a prime equal to 2q+1, where q is also a prime. You will need a first to choose a smaller prime q, then compute 2q+1, and check if it is a prime as well. If it's not, try another q. You may use your own primality checker or genenerate primes using BigInteger class.
2. Find a generator in the cyclic group mod p. To check if a number g is a generator, check that g^2 and g^q are both not equal to 1 (that is because the order of the group is 2q, so it only has cyclic subgroups of the orders 2 and q). This means that g does not belong to any of the cyclic subgroups of p, so it is a generator.
A small generator is fine. Use square-and-multiply for your computations.
3. Send your p and generator g to your partner group via the google docs (mark the message with your initials and theirs), then follow the Diffie-Hellman key exchange protocol to generate a shared key (send your A, receive their B). Your key would be a number smaller p, you don't need to convert it into an AES key or some such.
4. Use email (not the google doc) to verify that you got the same key.
5. Use the p and g sent to you by your partner group to generate another shared key, also check it.