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.

Tasks for the lab

Task 1: 20 points total

  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.

Task 2: 15 points total

As you are viewing communications by other groups in the google doc, use any of the methods below to solve their DLP to find their a and b (since your numbers are small, and therefore not really secure, that should be possible).

Apply one the following methods: baby-step, giant-step method or Pollard's rho algorithm, to find a secret key for an DLP problem generated by another group. You may use the Chinese remainder theorem, but given that you are using a safe prime, it wouldn't be much of a help.

What to submit (by e-mail to me, CC your partner)

  1. A record of all the steps that you did (computations, postings, etc).
  2. All the computed keys
  3. All your code.

CSci 4554 course web site.