An important problem in cryptography is how to establish keys for use in cryptographic protocols such as DES or AES, especially when the two parties are widely separated. Public key methods such as RSA provide one solution. In the present section, we describe a different method, due to Diffie and Hellman, whose security is very closely related to the difficulty of computing discrete logarithms.
There are several technical implementation issues related to any key distribution scheme. Some of these are discussed in Chapter 15. In the present section, we restrict ourselves to the basic Diffie-Hellman algorithm. For more discussion of some security concerns about implementations of the Diffie-Hellman protocol, see [Adrian et al.].
Here is how Alice and Bob establish a private key . All of their communications in the following algorithm are over public channels.
Either Alice or Bob selects a large prime number for which the discrete logarithm problem is hard and a primitive root . Both and can be made public.
Alice chooses a secret random with , and Bob selects a secret random with .
Alice sends to Bob, and Bob sends to Alice.
Using the messages that they each have received, they can each calculate the session key . Alice calculates by , and Bob calculates by .
There is no reason that Alice and Bob need to use all of as their key for their communications. Now that they have the same number , they can use some prearranged procedure to produce a key. For example, they could use the middle 56 bits of to obtain a DES key.
Suppose Eve listens to all the communications between Alice and Bob. She will know and . If she can compute discrete logs, then she can find the discrete log of to obtain . Then she raises to the power to obtain . Once Eve has , she can use the same procedure as Alice and Bob to extract a communication key. Therefore, if Eve can compute discrete logs, she can break the system.
However, Eve does not necessarily need to compute or to find . What she needs to do is solve the following:
Computational Diffie-Hellman Problem: Let be prime and let be a primitive root mod . Given and , find .
It is not known whether or not this problem is easier than computing discrete logs. The reasoning above shows that it is no harder than computing discrete logs. A related problem is the following:
Decision Diffie-Hellman Problem: Let be prime and let be a primitive root mod . Given and , and , decide whether or not .
In other words, if Eve claims that she has found with , and offers to sell you this information, can you decide whether or not she is telling the truth? Of course, if you can solve the computational Diffie-Hellman problem, then you simply compute and check whether it is (and then you can ignore Eve’s offer).
Conversely, does a method for solving the decision Diffie-Hellman problem yield a solution to the computational Diffie-Hellman problem? This is not known at present. One obvious method is to choose many values of and check each value until one equals . But this brute force method takes at least as long as computing discrete logarithms by brute force, so is impractical. There are situations involving elliptic curves, analogous to the present setup, where a fast solution is known for the decision Diffie-Hellman problem but no practical solution is known for the computational Diffie-Hellman problem (see Exercise 8 in Chapter 22).