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
- Each group finds a partner group (feel free to form cycles of
three groups)
- Each group generates at least two Diffie-Hellman public keys:
- 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.
- 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.
- 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.
- Use email (not the google doc) 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: 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)
- A record of all the steps that you did (computations, postings, etc).
- All the computed keys
- All your code.
CSci 4554 course web site.