## Section16.2Diffie Hellman key exchange

To initiate secure communication it is sufficient to determine a shared secret in the form of a cryptographic key. This key can be used for communication using a symmetric cryptographic protocol, such as AES, which requires less resources than communicating using a public key protocol. The Diffie-Hellman key exchange is a cryptographic protocol for exchanging cryptographic keys over a public channel. It was proposed by Ralph Merkle [9] and is named after Whitfield Diffie and Martin Hellman [2].

If there is no doubt about the identity of the other party, the Diffie-Hellman key exchange does not need any additional infrastructure, such as a key directory.

To create a shared secret Alice (A) and Bob (B) follow the following steps (also see Figure 16.2.3). First Alice and Bob agree on the group they want to work in. All powers are to be computed in this group.

Alice and Bob

Alice and Bob agree on a prime number $$p$$ and a $$g\in\Z_p^\otimes\text{.}$$ They will work in $$(\Z_p^\otimes,\otimes)$$ where $$a\otimes b=(a\cdot b)\fmod p\text{.}$$

Alice: Secret

Alice chooses her secret $$a\text{,}$$ uses it to compute her public information $$A$$ and sends it to Bob.

1. Alice randomly chooses her secret $$a\in\N\text{.}$$

2. Alice computes $$A=\gexp{g}{a}{\otimes}=(g^a)\fmod p$$ to Bob.

3. Alice sends $$A$$ to Bob.

Bob: Secret

Bob chooses his secret $$b\text{,}$$ uses it to compute his public information $$B$$ and sends it to Alice.

1. Bob randomly his secret $$b\in\N\text{.}$$

2. Bob computes $$B=\gexp{g}{b}{\otimes}=(g^b)\fmod p\text{.}$$

3. Bob sends $$B$$ to Alice.

Alice: Shared secret

Alice uses her secret $$a$$ and Bob's public information $$B$$ to compute the shared secret.

1. Alice receives $$B$$ from Bob. Alice now knows the values of $$p\text{,}$$ $$g\text{,}$$ $$a\text{,}$$ and $$B\text{.}$$

2. Alice computes the shared secret $$s_A=\gexp{B}{a}{\otimes}=(B^a)\fmod p\text{.}$$

Bob: Shared secret

Bob uses his secret $$b$$ and Alice's public information $$A$$ to compute the shared secret.

1. Bob receives $$A$$ from Alice. Bob now knows the values of $$p\text{,}$$ $$g\text{,}$$ $$b\text{,}$$ and $$A\text{.}$$

2. Bob computes the shared secret $$s_B=\gexp{A}{b}{\otimes}=(A^b)\fmod p\text{.}$$

Alice has computed the secret

\begin{equation*} s_A=\gexp{B}{a}{\otimes}=\gexp{\left(\gexp{g}{b}{\otimes}\right)}{a}{\otimes}=\gexp{g}{(a\cdot b)}{\otimes}\text{.} \end{equation*}

Bob has computed

\begin{equation*} s_B=\gexp{A}{b}{\otimes}=\gexp{\left(\gexp{g}{a}{\otimes}\right)}{b}{\otimes}=\gexp{g}{(b\cdot a)}{\otimes}\text{.} \end{equation*}

Since $$a\cdot b=b\cdot a$$ now Alice and Bob share the secret $$s_A=s_B\text{.}$$

In the Diffie Hellman Key Exchange:

Alice and Bob agree on a prime number p and a generator g for the group ({1,2,3,...,p-1},*) where a*b = (a$$\cdot$$b) mod p. We write g^c for $$g^{c*}\text{.}$$

Bob chooses an element b in {1,2,3,...,p-1} and computes B :=

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

Alices chooses an element a in {1,2,3,...,p-1} and computes A :=

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

Bob sends

• select

• a

• b

• g

• p

• A

• B

to Alice.

Alice sends

• select

• a

• b

• g

• p

• A

• B

to Bob.

• select

• a

• b

• g

• p

• A

• B

from Bob.

• select

• a

• b

• g

• p

• A

• B

from Alice

Bob computes the shared secret

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

Alice computes the shared secret

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

$${\verb!g^b!}$$

$${\verb!g^a!}$$

$$\text{B}$$

$$\text{A}$$

$$\text{B}$$

$$\text{A}$$

$${\verb!A^b!}$$

$${\verb!B^a!}$$

Assume Eve has eavesdropped on the communication between Alice and Bob and now knows the $$p\text{,}$$ $$g\text{,}$$ $$A\text{,}$$ and $$B\text{.}$$ To obtain the shared secret $$s\text{,}$$ Eve needs either Alice's secret $$a$$ or Bob's secret $$b\text{,}$$ which can only be obtained by finding the discrete logarithm of $$A$$ to base $$g$$ in $$(\Z_p^\otimes,\otimes)$$ or the discrete logarithm of $$B$$ to base $$g$$ in $$(\Z_p^\otimes,\otimes)\text{.}$$ So, the security of the Diffie-Hellman key exchange depends on the difficulty of computing discrete logarithms in $$(\Z_p^\otimes,\otimes)\text{.}$$

In the video in Figure 16.2.5 we summarize what we have just described.

Investigate the dependencies of the steps in the Diffie Hellman key exchange in the interactive Example 16.2.6.

In Example 16.2.7 we illustrate how the Diffie-Hellman key exchange works with small numbers. The discrete logarithm problem is solved so quickly with these small numbers that it is very easy to break the encryption.

We give an example for a Diffie-Hellman key exchange with small numbers.

Alice and Bob: Group

Alice and Bob agree on the prime $$p=11$$ and the generator $$g=2\text{.}$$ They work in the group $$(\Z_{11}^\otimes,\otimes)$$ where $$a\otimes b=(a\cdot b)\fmod 11\text{.}$$

Alice: Secret
1. Alice randomly chooses $$a=8\text{.}$$

2. Alice computes $$A=\gexp{2}{a}{\otimes}=\gexp{2}{8}{\otimes}=2^{8}\fmod=256\fmod 11=3\text{.}$$

3. Alice sends $$A=3$$ to Bob.

Bob: Secret
1. Bob randomly chooses $$b=6\text{.}$$

2. Bob computes $$B=\gexp{g}{b}{\otimes}=\gexp{2}{6}{\otimes}=2^{6}\fmod 11=64\fmod 11=9\text{.}$$

3. Bob sends $$B=9$$ to Alice.

Alice: Shared Secret
1. Alice receives $$B=9$$ from Bob.

2. Alice computes the shared secret

$$s =\gexp{B}{a}{\otimes}$$ $$=\gexp{9}{8}{\otimes}$$ $$=\gexp{\left(\gexp{\left(\gexp{9}{2}{\otimes}\right)}{2}{\otimes}\right)}{2}{\otimes}$$ $$=\gexp{\left(\gexp{4}{2}{\otimes}\right)}{2}{\otimes}$$ $$=\gexp{5}{2}{\otimes}=3 \text{.}$$

Bob: Shared Secret
1. Bob receives $$A=3$$ from Alice.

2. Bob computes the shared secret

$$s=\gexp{A}{b}{\otimes}=$$ $$\gexp{3}{6}{\otimes} =$$ $$\gexp{3}{2}{\otimes}\otimes\gexp{3}{4}{\otimes} =$$ $$9\otimes\gexp{9}{2}{\otimes} =9\otimes4=3 \text{.}$$

Now Alice and Bob share the secret $$s=3\text{.}$$

In the video Figure 16.2.8 we give another example.

Alice and Bob use the Diffie Hellman key exchange to generate a shared secret.

Alice and Bob: The Group

For their Diffie Hellman key exchange Alice and Bob agree to work in the group of $$(\mathbb{Z}^\otimes_{29},\otimes)$$ where $$a\otimes b=(a\cdot b)\bmod 29\text{.}$$ They also agree on the generator $$g=2\text{.}$$

Alice: Secret

Alice chooses her secret $$a=3$$ and sends $$A=g^{a\otimes}=(g^a)\bmod 29=$$ to Bob.

Bob: Secret

Bob chooses his secret $$b=4$$ and sends $$B=g^{b\otimes}=(g^b)\bmod 29=$$ to Alice.

Alice: Shared Secret

Alice receives $$B=$$ from Bob, and she computes the shared secret $$B^{a\otimes}=(B^a)\bmod 29=$$

Bob: Shared Secret

Bob receives $$A=$$ from Alice, and he computes the shared secret $$A^{b\otimes}=(A^b)\bmod 29=$$

Alice and Bob: Shared Secret

Now Alice and Bob share the secret .

$$8$$

$$16$$

$$16$$

$$7$$

$$8$$

$$7$$

$$7$$

From Bob's perspective a key exchange looks as follows.

Alice and Bob agree to use the prime number $$p=17$$ and the generator $$g=5$$ for their Diffie-Hellman key exchange. Alice sends Bob $$A=2\text{.}$$ Bob chooses the random number $$b=3\text{.}$$ What is Alice and Bobs shared secret ?

Solution.

The shared secret is $$s=A^b\fmod p=2^3\fmod 11=8\text{.}$$

In Checkpoint 16.2.11 determine the shared secret for Bob.

For a Diffie-Hellman key exchange Alice and Bob use the group $$(\mathbb{Z}_{11}^{\otimes},\otimes)$$ and the generator $$g = 2\text{.}$$

Bob chooses $$b = 6$$ as his secret.

What does Bob send to Alice ?

$$B=$$.

$$9$$

We demonstrate the importance of random numbers in the Diffie-Hellman key exchange.

The software company DH insecurity has implemented the random number generator from Figure 16.2.12, that is, the random numbers are always 4. Alice and Bob both use software from DH insecurity and Eve knows this. Eve eavesdrops on Bob's communication when Alice and Bob are agreeing on the prime $$p$$ and the generator $$g\text{.}$$ She learns that $$p=19$$ and $$g=15\text{.}$$ So Alice and Bob are working in the subgroup of $$(\Z_{19},\otimes)$$ generated by $$15\text{.}$$ Eve now can find Alice's and Bob's shared secret generated by the Diffie Hellman key exchange. What is Alice and Bob's shared secret ?

Solution.

As the random number generator always returns 4, Alice's secret $$a$$ is 4 and Bob's secret $$b$$ is 4. Thus

$$A=\gexp{g}{a}{\otimes} =$$ $$\gexp{15}{4}{\otimes}=$$ $$\gexp{\left(\gexp{15}{2}{\otimes}\right)}{2}{\otimes}$$ $$= \gexp{(15^2\fmod 19)}{2}{\otimes}$$ $$= \gexp{(225\fmod 19)}{2}{\otimes}$$ $$= \gexp{16}{2}{\otimes}$$ $$= 256\fmod 19=9$$

Alice and Bob's shared secret is

$$s=\gexp{A}{b}{\otimes}$$ $$= \gexp{9}{4}{\otimes}$$ $$= \gexp{\left(\gexp{9}{2}{\otimes}\right)}{2}{\otimes}$$ $$= \gexp{(81\fmod 19)}{2}{\otimes}$$ $$= \gexp{5}{2}{\otimes}$$ $$= 25\fmod 19=6 \text{.}$$

To give an idea how large the prime $$p$$ should be for the Diffie-Hellman key exchange to be secure, we present an example for a discrete logarithm that was computed in 2014.

Let $$p$$ be the 80 decimal digit (596 digits in base 2) prime above:

\begin{align*} p= \amp 191147927718986609689229466631454649812986246276667354864188\\ \amp 503638807260703436799058776201365135161278134258296128109200\\ \amp 046702912984568752800330221777752773957404540495707852046983\text{.} \end{align*}

The group $$(\Z_p^\otimes,\otimes)$$ is generated by $$g=5\text{,}$$ that is $$\Z_p^\otimes=\{5^n\mid n\in\N\}\text{.}$$ In 2014 the researchers Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli, and Emmanuel Thomé announced that they computed the discrete logarithm to base 5 of

\begin{align*} a= \amp 68188080109582330879868861330998506151774854600403700625797\\ \amp 299927558995162740321112260973638619757922646242302104885437\\ \amp 536745080299248852065080008358309735875192480724496530325927\text{.} \end{align*}

It took them under 130 core years (that is, on a single core computer it would take that long) on a parallel computing cluster to find the solution

\begin{align*} n= \amp 138670566126823584879625861326333326312363943825621039220215\\ \amp 583346153783336272559955521970357301302912046310782908659450\\ \amp 758549108092918331352215751346054755216673005939933186397777\text{.} \end{align*}

They applied the data computed for finding this discrete logarithm in the computation of further discrete logarithms which only required a few hours each.

The example illustrates that a 180 decimal digits (596 digits in base 2) prime is too small for cryptographic purposes, as the discrete logarithm problem can be solved in a (relatively) short amount of time, provided enough computation power is available. The commonly recommended size of the prime for the Diffie Hellman key exchange is 2048 base 2 digits.