Diffie-Hellman key exchange

How it works

In Diffie-Hellman key exchange both parties know a prime $p$ and a base $g$. Alice picks a secret $a$ and sends $A = g^a \bmod p$; Bob picks $b$ and sends $B = g^b \bmod p$. Alice computes $B^a$ and Bob $A^b$, and both get $K = g^{ab} \bmod p$. An eavesdropper sees $p$, $g$, $A$ and $B$; computing $K$ from them is the computational Diffie-Hellman problem, which is believed to be as hard as computing discrete logarithms in a well chosen group.

The choice of the group matters. The order of $g$ divides $p - 1$, and by the Pohlig-Hellman algorithm a discrete logarithm is only as hard as the largest prime factor of that order. The usual choice is a safe prime $p = 2q + 1$ with $q$ prime, and $g$ of order $q$ (a square), so that the keys live in a subgroup of large prime order. A generator of all of $\mathbb{Z}_p^*$ leaks the parity of the secret through the Legendre symbol.

Plain Diffie-Hellman gives no authentication: a man in the middle can run one exchange with each side. Protocols such as TLS 1.3 therefore sign the exchanged values. Today most deployments use the elliptic curve version (ECDH), and post-quantum key exchange uses lattice-based KEMs instead.