Math 480, Spring 2015, Assignment 4
Carefully define the following terms, then give one example and one non-example of each:[edit]
- Vernam one-time pad.
- Discrete exponential function $\mathrm{exp}_g:\mathbb{Z}_{p-1}\rightarrow\mathbb{Z}_p^*$ (as an example, do a sample calculation).
- Discrete logarithm function $\mathrm{log}_g:\mathbb{Z}_p^*\rightarrow\mathbb{Z}_{p-1}$.
- Discrete logarithm problem.
- Diffie-Hellman problem.
Carefully describe the following algorithms:[edit]
- Diffie-Hellman key exchange.
Solve the following problems:[edit]
- Exercises 2.4 and 2.6.
Coding projects:[edit]
- (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.
- (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.
- (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.)
Warning: If you succeed in identifying a primitive root $g$ by any obvious algorithm, then your modulus $p$ is certainly too small for a secure Diffie-Hellman implementation. In addition, even very large moduli can be vulnerable to attack by the Pohlig-Hellman algorithm when carelessly chosen (we will discuss these issues later in the course). For now, you may wish to use the following parameters in your Diffie-Hellman implementation:
- Modulus: b460cb3d292e6330099c10f1a95080a08bf28af9566c1077141e6b098dd0b1e35de0206a1a94984d1895582e629866515ace1a07cdad04a80a8d5f1296e8ce60234f791608617fe9bd6947f09bacec44f1caa853261893caba098fbd73798df43a42d11cf8040b0b22a292a4edd1b2d2128749f95aaefc1136e4c42f5d23599750f1797dc545e0c7b3e654356261c2b7c1049860136d7faaafbab290e77bc5c0ea17474b6382749a331da4381d4cd47c81fe79aca15370b2434310b54a3240b9caff6ebf5fca8baa8e4d6808fa2ef202c2ea7837ee22f3555fd0a4bc5d6acb2fd506a035cec9da6bae75dfad5ba7ea3bff9d443087863e8a7bcb83150c50649f
- Primitive root: 5
(the values are in hexadecimal). This modulus is a so-called "safe prime," i.e. it has the form $p=2q+1$ where $q$ is also prime. These are preferred for security against Pohlig-Hellman. They have the added advantage that the only possible orders of elements of $\mathbb{Z}_p^*$ are $1, 2, q,$ and $p-1$; hence only two exponentiations are required to determine whether an element of $\mathbb{Z}_p^*$ is a primitive root.
We will learn how to generate safe primes later in the course, when we discuss probabilistic primality testing.
The modulus listed above has width 2048 bits. NIST estimates that properly implemented discrete-log ciphers based on this modulus will be secure until approximately 2030.
