Diffie-Hellman key exchange

Tasks for the lab

Task 1: 20 points total

• Each group finds a partner group (feel free to form cycles of three groups)
• Each group generates a Diffie-Hellman public key:
• Choose a safe prime p between 10000000 and 1000000000. A safe prime is a prime equal to 2q+1, where q is also a prime. The reason for using a safe prime is so that the group has a very large cyclic subgroup. We will later see how having only small cyclic subgroups makes it much easier to solve the DLP problem.
• 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 methods in BigInteger class.
• 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 and reduce modulo p after each step. Send your p and generator g to your partner group via the discussion on canvas (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).
• Use email (not the canvas) to verify that you got the same key.
• Use the p and g sent to you by your partner group to generate another shared key, also check it.

Task 2: 20 points total

• As you are viewing communications by other groups in the canvas discussion, 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.

What to submit

• A record of all the steps that you did (computations, postings, etc).
• Your genrated keys
• All the keys that you broke (and explanation of how you broke them)
• All your code.