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.

Tasks for the lab

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.
  3. Post your group and your public materials in the google document that is given. Specifify whom it is addressed to.
  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
  3. All your code.

CSci 4554 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.