Diffie-Hellman Key Exchange

This post is about the public-key Diffie-Hellman key exchange.

The Diffie-Hellman Key Exchange Protocol

This is the problem the Diffie-Hellman protocol is trying to address. Two parties, Alice and Bob, would like to exchange secret messages using a symmetric cipher. For that to be possible, they have to exchange a secret key to be used in the encryption and decryption of the messages. However, their only means of communication is through an insecure public channel. Any information they exchange can be intercepted by Eve the eavesdropper. How can Alice and Bob resolve this dilemma? With the Diffie–Hellman key exchange protocol, Alice and Bob can share a secret key securely over an insecure channel even even though they have no prior knowledge of each other.

The security of the Diffie-Hellman protocol is based on the difficulty of the discrete logarithm problem for $\mathbb{F}_p$ , the finite field consisting of the integers modulo a prime $p$ . The discrete logarithm is defined here. The discrete logarithm problem is discussed here. The following steps describe the Diffie-Hellman algorithm.

Public Information
The first step in the key exchange is for Alice and Bob to set up the public parameter, which consists of a large prime number $p$ and a positive integer $g$ modulo $p$ . Because $p$ and $g$ are made public, the information is accessible by Eve the eavesdropper.

Private Information
The next step is for Alice to choose a secret positive integer $a$ between 1 and $p-1$ and for Bob to choose a secret positive integer $b$ between 1 and $p-1$ . Alice and Bob keep their respective numbers secret. Then Alice computes the value $A \equiv g^a \ \text{mod} \ p$ and Bob computes the value $B \equiv g^b \ \text{mod} \ p$ .

Public Exchange
In this step, Alice sends the value $A$ to Bob and Bob sends the value $B$ to Alice. Because these values are sent over an insecure channel, Eve the Eavesdropper can see the values.

Private Computation to Derive the Key
Once Alice receives the value $B$ from Bob, she computes $A^* \equiv B^a \ \text{mod} \ p$ . In the meantime, Bob computes $B^* \equiv A^b \ \text{mod} \ p$ . The values $A^*$ and $B^*$ are identical. This common value is their exchanged key.

Remarks

For the base $g$ in the public parameter, we can choose a primitive root modulo the large odd prime $p$ in order to make it as difficult as possible for Eve the Eavesdropper to break the protocol. However, it is not strictly required that $g$ must be a primitive root. If $g$ is not a primitive root, its order in the finite field $\mathbb{F}_p$ should be a large prime. See Example 2 below.
To see that the private computation produces the common secret key, see the following calculation.

$A^* \equiv B^a \equiv (g^b)^a \equiv (g^a)^b \equiv A^b \equiv B^* \ \text{mod} \ p$

Once the secret key is established, Alice and Bob can use it to communicate using a symmetric cipher.

Examples

Example 1
In this example, the agreed upon public information consists of the prime number $p$ = 460,079 and the primitive root $g$ = 13,627. The private secret numbers are $a$ = 397,935 (Alice) and $b$ = 250,460 (Bob). Alice and Bob keep their respective numbers secret. Alice then computes $A \equiv g^a$ and Bob computes $B \equiv g^b$ modulo the prime $p$ .

$\displaystyle A \equiv g^a \equiv 13627^{397935} \equiv 3460 \ \text{mod} \ 460079$

$\displaystyle B \equiv g^b \equiv 13627^{250460} \equiv 312029 \ \text{mod} \ 460079$

Alice sends $A$ = 3460 to Bob and Bob sends $B$ = 312029 to Alice. Then Alice performs the calculation $B^a$ and Bob perform the calculation $A^b$ modulo $p$ .

$\displaystyle A^* \equiv B^a \equiv 312029^{397935} \equiv 282228 \ \text{mod} \ 460079$

$\displaystyle B^* \equiv A^b \equiv 3460^{250460} \equiv 282228 \ \text{mod} \ 460079$

As a result, the number 282,228 is the shared secret key for Alice and Bob. They can then use this key to communicate using a symmetric cipher. $\square$

Remarks
Eve can see the entire exchange of information between Alice and Bob. If Eve were to pay attention, she would know $p$ , $g$ (the public parameters) and the numbers $A$ (from Alice) and $B$ (from Bob). Eve can break the Diffie-Hellman algorithm, i.e., uncover the secret numbers of Alice and Bob, if she can solve either one of the congruence equations from Example 1:

$13627^a \equiv 3460 \ \text{mod} \ 460079$
$13627^b \equiv 312029 \ \text{mod} \ 460079$

If Eve the Eavesdropper can solve either one of these equations, she would be able to obtain the shared secret key between Alice and Bob. Solving either one of these two congruence equations is precisely the discrete logarithm problem (discussed here). Based on the information Eve can gather in the exchange between Alice and Bob via an insecure channel, solving the discrete logarithm problem is the one way for Eve to find the shared secret key.

Example 1 is only an illustration of the Diffie-Hellman algorithm. The prime number 460079 is too small to provide any real security. All Eve has to do is to check all the possible powers of 13,627 modulo 460,079 using a computer. How large does $p$ have to be? The current guidelines suggest that if $p$ is 2000-bit prime ( $p$ is roughly $2^{2000}$ ) and the order of the base $p$ is a prime that is roughly $\frac{p}{2}$ , then solving the discrete logarithm problem will be a daunting task.

Example 2
We continue to explore the Diffie-Hellman algorithm using Example 1. The base $g$ (= 13,627) in Example 1 is a primitive root modulo the prime 460,079. This means that every number between 1 and $p-1$ (= 470078) can be expressed as a unique power of 13,627. Thus for any $y$ with $1 \le y \le p-1$ , there is a unque $x$ such that $g^x \equiv y$ modulo $p$ . As a result, the order of this $g$ is $p-1$ , which means that the smallest integer $x$ such that $g^x \equiv 1$ is $p-1$ . For the working of the Diffie-Hellman algorithm, using a primitive root as the base is not necessary. As long as the order of $g$ is a large prime, the algorithm can be made secure.

Let’s work Example 1 using $g$ = 275,064, which is not a primitive root. The $p$ , $a$ and $b$ are still the same values as in Example 1. The following shows the calculation.

$\displaystyle A \equiv g^a \equiv 275064^{397935} \equiv 151570 \ \text{mod} \ 460079$

$\displaystyle B \equiv g^b \equiv 275064^{250460} \equiv 407220 \ \text{mod} \ 460079$

$\displaystyle A^* \equiv B^a \equiv 407220^{397935} \equiv 305882 \ \text{mod} \ 460079$

$\displaystyle B^* \equiv A^b \equiv 151570^{250460} \equiv 305882 \ \text{mod} \ 460079$

Thus, the shared secret key between Alice and Bob is 305,882. Using a different base $g$ will lead to a different shared secret key. The order of 275,064 is 461, meaning that it is the smallest integer $x$ such that $275064^x$ is congruent to 1 modulo 460,079. This means that after every 461 powers of $g$ , the values of $g^x$ repeat. Of course, this example being only an illustration, the order of the base $g$ is small. In actual practice, we would would want the order of $g$ to be a large, either $p-1$ ( $g$ would be a primitive root) or a large prime that is roughly $\frac{p}{2}$ . Using a $g$ with a small order presents a vulnerability that Eve the Eavesdropper can exploit. Using a base $g$ with a large prime order helps prevent using the Pohlig–Hellman algorithm to obtain the secret numbers $a$ and $b$ .

To see where the base $g$ = 275,064 come from and why its order is 461, note that $p-1$ is factored as $p-1$ = 2 x 461 x 499. Then $\frac{p-1}{461}=998$ and $2^{998} \equiv 275064$ modulo 460079. This indicates that the order of 275,964 is 461, which means that 461 is the smallest exponent $x$ such that $275064^x$ is congruent to 1. As a result, the powers of 275,064 repeat after every 461 iterations. In general, it is a good practice to chose a large prime $p$ so that $p-1$ has large prime factors. $\square$

Remarks
As discussed in Example 2, we can either use a primitive root $g$ for the base or a base $g$ such that the order of $g$ is a large prime. Given a prime $p$ , see here for some pointers on finding primitive roots. If the approach is not to use primitive root, here’s some ideas on how to find a base $g$ with the order that is a large prime. Let $p$ be a large prime and let $q$ be a prime factor of $p-1$ . Consider $g \equiv a^{\frac{p-1}{q}}$ modulo $p$ . If $g \equiv 1$ , then the order of $a$ is less than or equal to $\frac{p-1}{q}$ . If $g \not \equiv 1$ , then the order of $g$ is the prime $q$ . If $q$ is sufficiently large, we can use it as the base for the Diffie-Hellman algorithm.

The Diffie-Hellman Problem

In the exchange of information between Alice and Bob, Eve knows four pieces of information, $p$ (the large prime), $g$ (the base), $A$ (sent by Alice to Bob) and $B$ (sent by Bob to Alice). The number $A$ is $g^a$ and the number $B$ is $g^b$ modulo $p$ . If Eve can solve the discrete logarithm problem, then she can uncover one of the secret exponents ( $a$ or $b$ ). As a result, she can derive the shared secret key. This seems to suggest that breaking the Diffie-Hellman algorithm is equivalent to solving the discrete logarithm problem. This is not entirely correct. Breaking the Diffie-Hellman protocol is equivalent to solving the following problem.

The Diffie-Hellman Problem
Four values are given – a prime number $p$ , a positive integer $g$ , and two values of exponentiation $g^a$ and $g^b$ modulo $p$ . From these four values, derive the value of $g^{ab}$ modulo $p$ .

How hard is the Diffie-Hellman problem? It is clear that if Eve can solve the discrete logarithm problem, she can solve the Diffie-Hellman problem. How about the other way? If Eve has an efficient algorithm for solving the Diffie-Hellman problem, can she use that algorithm to solve the discrete logarithm problem? It is certainly an intriguing question. No one knows the answer.

$\text{ }$

Dan Ma Diffie-Hellman Key Exchange

Dan Ma Discrete Logarithm Problem

Daniel Ma Diffie-Hellman Key Exchange

Daniel Ma Discrete Logarithm Problem

Dan Ma Diffie-Hellman Problem

Daniel Ma Diffie-Hellman Problem

Mathematical Cryptography

focusing on the math in public key cryptography

Diffie-Hellman Key Exchange

Leave a comment Cancel reply

Share this:

Related

Leave a comment Cancel reply