Figure16.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].
Figure16.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.
Figure16.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{.}\)
Since \(a\cdot b=b\cdot a\) now Alice and Bob share the secret \(s_A=s_B\text{.}\)
Checkpoint16.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.
Figure16.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.
Example16.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.
Example16.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=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{.}\)
Now Alice and Bob share the secret \(s=3\text{.}\)
In the video Figure 16.13 we give another example.
Figure16.13.Diffie Hellman (part 2) -- an example by Frances Clerk
Checkpoint16.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.
Problem16.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{.}\)
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
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.
Example16.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:
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
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.
