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.2.1. The first paragraph of the article *New Directions in Cryptography* by Whitfield Diffie and Martin Hellman
🔗

To start secure communication, it is enough to create a shared secret in the form of a cryptographic key. This key can be used with a symmetric cryptographic protocol, such as AES. This uses fewer resources than a public key protocol. The Diffie-Hellman key exchange is a cryptographic protocol for exchanging keys over a public channel. Ralph Merkle proposed it [9], and it is named after Whitfield Diffie and Martin Hellman [2].

🔗

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

🔗

When the identity of the other party is certain, the Diffie-Hellman key exchange does not need more infrastructure, such as a key directory.

🔗

Figure 16.2.3. 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.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.

🔗

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

🔗

Suppose Eve listened to the communication between Alice and Bob and now knows \(p\text{,}\) \(g\text{,}\) \(A\text{,}\) and \(B\text{.}\) To find the shared secret \(s\text{,}\) Eve needs either Alice’s secret \(a\) or Bob’s secret \(b\text{.}\) She can find either secret only by computing 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 how hard it is to compute discrete logarithms in \((\Z_p^\otimes,\otimes)\text{.}\)

🔗

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

🔗

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

🔗

Study the dependencies of the steps in the Diffie Hellman key exchange in the interactive Example 16.2.5.

🔗

Example 16.2.5. Diffie Hellman interactive.

🔗

In Example 16.2.6 we show 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.2.6. 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.2.7 we give another example.

🔗

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

🔗

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

🔗

Problem 16.2.8. 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 17=8\text{.}\)

🔗

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

🔗

Problem 16.2.9. Bad random numbers.

The software company DH insecurity has implemented the random number generator from Figure 16.2.11, 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,\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 show how large the prime \(p\) should be for a secure Diffie-Hellman key exchange, we give an example of a discrete logarithm computed in 2014.

🔗

Example 16.2.10. 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)\) has generator \(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*}

🔗

Finding the solution took under 130 core years (the time a single computer core would need) on a parallel computing cluster:

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

🔗

They reused the data from this computation to find more discrete logarithms. Each additional logarithm then required only a few hours.

🔗

The example shows that a prime with 180 decimal digits (596 digits in base 2) is too small for cryptography. With enough computing power, the discrete logarithm problem can be solved in a relatively short time. A commonly recommended prime size for the Diffie-Hellman key exchange is 2048 base 2 digits.

🔗

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

🔗

Prev Top Next