Categories: Cryptography.

Diffie-Hellman key exchange

In cryptography, the Diffie-Hellman key exchange is a method for two parties, who can only communicate over an insecure channel, to securely agree on an encryption key.

The fundamental assumption of the Diffie-Hellman scheme, upon which its security rests, is that the following function f(n)f(n) is a trapdoor function, which means that calculating ff is easy, but its inverse f1f^{-1} is extremely hard:

f(n)gnmodp\begin{aligned} f(n) \equiv g^n \bmod p \end{aligned}

Where nn is a natural number, and pp is a prime. The natural number gg is a so-called primitive root modulo pp. Importantly, gg and pp have been specifically chosen such that f(n)f(n) can take any value in {1,...,p ⁣ ⁣1}\{1, ..., p \!-\! 1\} for nn in {0,...,p ⁣ ⁣2}\{0, ..., p \!-\! 2\}. The trapdoor assumption is that, given gg, pp and f(n)f(n), there is no efficient algorithm to recover nn.

Suppose that Alice and Bob want to exchange encrypted data in the future, so they need to agree on an encryption key to use. However, they can only exchange messages with each other over an insecure channel, which is being eavesdropped.

After they publicly agree on the values of gg and pp, Alice and Bob each choose a secret number from {0,...,p ⁣ ⁣2}\{0, ..., p \!-\! 2\}, respectively aa and bb, and then privately calculate AA and BB as follows:

AgamodpBgbmodp\begin{aligned} A \equiv g^a \bmod p \qquad \qquad B \equiv g^b \bmod p \end{aligned}

Finally, they transmit these numbers AA and BB to each other over the insecure connection, and then each side calculates kk, which is the desired secret key:

kAbmodp=Bamodp=gabmodp\begin{aligned} \boxed{ k \equiv A^b \bmod p = B^a \bmod p = g^{ab} \bmod p } \end{aligned}

The point is that kk includes both aa and bb, but each side only needs to know either aa or bb. Thanks to the trapdoor assumption, the eavesdropper knows AA and BB, but cannot recover aa or bb.

This assumption is just that: an assumption. So far, nobody has been able to prove or disprove it for classical computation. However, for quantum computers, it has already been disproven! In this case, another method must be used, for example the BB84 protocol.


  1. J.B. Brask, Quantum information: lecture notes, 2021, unpublished.