10.4 Diffie-Hellman Key Exchange – Introduction to Cryptography with Coding Theory, 3rd Edition

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 K. All of their communications in the following algorithm are over public channels.

  1. Either Alice or Bob selects a large prime number p for which the discrete logarithm problem is hard and a primitive root α (mod p). Both p and α can be made public.

  2. Alice chooses a secret random x with 1xp2, and Bob selects a secret random y with 1yp2.

  3. Alice sends αx (mod p) to Bob, and Bob sends αy (mod p) to Alice.

  4. Using the messages that they each have received, they can each calculate the session key K. Alice calculates K by K(αy)x (mod p), and Bob calculates K by K(αx)y (mod p).

There is no reason that Alice and Bob need to use all of K as their key for their communications. Now that they have the same number K, they can use some prearranged procedure to produce a key. For example, they could use the middle 56 bits of K to obtain a DES key.

Suppose Eve listens to all the communications between Alice and Bob. She will know αx and αy. If she can compute discrete logs, then she can find the discrete log of αx to obtain x. Then she raises αy to the power x to obtain αxyK. Once Eve has K, 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 x or y to find K. What she needs to do is solve the following:

Computational Diffie-Hellman Problem: Let p be prime and let α be a primitive root mod p. Given αx (mod p) and αy (mod p), find αxy (mod p).

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 p be prime and let α be a primitive root mod p. Given αx (mod p) and αy (mod p), and c  0 (mod p), decide whether or not cαxy (mod p).

In other words, if Eve claims that she has found c with cαxy (mod p), 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 αxy (mod p) and check whether it is c (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 c and check each value until one equals αxy (mod p). 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).