# 10.4 Diffie-Hellman Key Exchange

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.

1. 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.

2. Alice chooses a secret random  with , and Bob selects a secret random  with .

3. Alice sends  to Bob, and Bob sends  to Alice.

4. 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).