Math 480, Spring 2015, Assignment 4

Carefully define the following terms, then give one example and one non-example of each:

1. Vernam one-time pad.
2. Discrete exponential function $\mathrm{exp}_g:\mathbb{Z}_{p-1}\rightarrow\mathbb{Z}_p^*$ (as an example, do a sample calculation).
3. Discrete logarithm function $\mathrm{log}_g:\mathbb{Z}_p^*\rightarrow\mathbb{Z}_{p-1}$.
4. Discrete logarithm problem.
5. Diffie-Hellman problem.

Carefully describe the following algorithms:

1. Diffie-Hellman key exchange.

Solve the following problems:

1. Exercises 2.4 and 2.6.

Coding projects:

1. (Primitive roots) Write a (possibly slow) algorithm that takes a prime $p$ as input, and produces a primitive root for $\mathbb{Z}_p$ as output.
2. (Discrete logarithm) Write a program that computes discrete logarithms by some reasonably obvious method. Find out how large you can make the modulus before your program becomes unusably slow and/or runs out of memory.
3. (Diffie-Hellman) Implement the Diffie-Hellman key exchange protocol. (You will need some way to simulate two communicating parties. Perhaps the ideal solution is two have two processes communicating through pipes; for real applications it is easy to replace pipes by TCP sockets. If you don't know how to use pipes, communicating through temporary files is fine too. Better still: find a partner and exchange a key by e-mail. When you meet in person, verify that your computed keys coincide. Copy your e-mails to an adversary, and see how large you need to make the modulus before your adversary is unable to compute the key.)

--------------------End of assignment--------------------