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
- Each group is given a random letter, you don't know which one is which.
- Each group generates at least two Diffie-Hellman public keys:
- 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)
- 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.
- Post your group and your public materials in the google document
that is given. Specifify whom it
is addressed to.
- 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).
- Respond to requests adressed to you by following the rest of the
protocol steps.
- 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.
- 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)
- A record of all the steps that you did (computations, postings, etc).
- All the computed keys
- All your code.
CSci 4554 course web site.