Diffie Hellman key exchange

Section 16.2 Diffie Hellman key exchange

We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science. — Figure 16.6. The first paragraph of the article *New Directions in Cryptography* by Whitfield Diffie and Martin Hellman
🔗

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

🔗

Figure 16.7. An overview of the Diffie Hellman key exchange, including an illustration as color mixing.

🔗

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.

🔗

Figure 16.8. Diffie Hellman key exchange. The agreement on \(p\) and \(g\) takes place over an insecure channel. Alice and Bob generate a shared secret \(s\) without sending the secret. All computations take place in the group \((\Z^\otimes_p,\otimes)\) where \(a\otimes b = (a\cdot b)\fmod p\text{.}\)

🔗

To create a shared secret Alice (A) and Bob (B) follow the following steps (also see Figure 16.8). 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.

🔗

Alice randomly chooses her secret \(a\in\N\text{.}\)
🔗

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

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

🔗

Bob randomly his secret \(b\in\N\text{.}\)
🔗

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

🔗
Bob sends \(B\) to Alice.
🔗

🔗

🔗

Alice: Shared secret 🔗

Alice uses her secret \(a\) and Bob’s public information \(B\) to compute the shared secret.

🔗

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

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

🔗

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

🔗
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{.}\)

🔗

Checkpoint 16.9. Diffie Hellman protocol.

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.

🔗

Alice receives

select
🔗

🔗
a
🔗

🔗
b
🔗

🔗
g
🔗

🔗
p
🔗

🔗
A
🔗

🔗
B
🔗

🔗

from Bob.

🔗

Bob receives

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
🔗

🔗

🔗

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.10 we summarize what we have just described.

🔗

Figure 16.10. Diffie Hellman (part 1) -- how it works by Frances Clerk

🔗

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

🔗

Example 16.11. Diffie Hellman interactive.

🔗

In Example 16.12 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.

🔗

Example 16.12. Diffie-Hellman with small numbers.

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 🔗

Alice randomly chooses \(a=8\text{.}\)
🔗

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

🔗
Alice sends \(A=3\) to Bob.
🔗

🔗

🔗

Bob: Secret 🔗

Bob randomly chooses \(b=6\text{.}\)
🔗

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

🔗
Bob sends \(B=9\) to Alice.
🔗

🔗

🔗

Alice: Shared Secret 🔗

Alice receives \(B=9\) from Bob.
🔗

🔗
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 🔗

Bob receives \(A=3\) from Alice.
🔗

🔗
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.13 we give another example.

🔗

Figure 16.13. Diffie Hellman (part 2) -- an example by Frances Clerk

🔗

Checkpoint 16.14. Diffie Hellman with small numbers.

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 .

🔗

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

🔗

Problem 16.15. Shared secret.

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.16 determine the shared secret for Bob.

🔗

Checkpoint 16.16. Diffie Hellman: Bob’s perspective.

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=\).

🔗

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

🔗

described in detail following the image — Figure 16.17. *Random Number* by Randall Munroe (`https://xkcd.com/221`)
🔗

Problem 16.18. Bad random numbers.

The software company DH insecurity has implemented the random number generator from Figure 16.17, 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.

🔗

Example 16.19. A hard discrete logarithm problem that is not hard enough.

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 prime number with 180 decimal digits (596 digits in base 2) is too small for cryptographic purposes, because 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.

🔗

Prev Top Next