## CSci 4554 Lab 4: Diffie-Hellman key exchange

### Due Monday, Nov 4th 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.

#### Task 1: 30 points total

1. Each group is given a random letter, you don't know which one is which.
2. Each group generates at least two Diffie-Hellman public keys:
1. Choose a safe prime p greater than 1000000000 (you will need a smaller prime q, then compute 2q+1, and check if it is a prime as well)
2. Find a generator in the cyclic group mod p. To checkm if a number g is a generator, check that g^2 and g^q are both not equal 1. 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 computations.
4. Choose more key exchange materials, some under your group name, and one under another group's name (your goal is to established a shared key with two groups under other group's name for a successful "man-in-the-middle" attack).
5. Respond to requests adressed to you by following the rest of the protocol steps.
6. At least a half of your posted materials must be under your own group name, and you must respond to at least a half of requests addressed to you.
7. At the end all the shared keys would be revealed

#### Task 2: 15 points total

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. When we open all the keys, you will be able to know if your computation was correct.

#### 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