Skip to content

Diffie-Hellman Key Exchange

The Story Behind the Math

In the early 1970s, cryptography had a fundamental problem. If Alice and Bob wanted to communicate secretly, they first needed to share a secret key. But how do you share a secret key... without already having a secure channel? It was a chicken-and-egg problem that had plagued cryptography for millennia.

Whitfield Diffie and Martin Hellman, working at Stanford University, solved this seemingly impossible problem in 1976. Their paper, "New Directions in Cryptography," is one of the most important publications in computer science history. They showed that two people could agree on a shared secret by exchanging information in public — even if an eavesdropper watched every message.

The key insight is a beautiful one-way property of modular exponentiation. Computing \(g^a \mod p\) given \(g\), \(a\), and \(p\) is fast. But given \(g^a \mod p\), finding \(a\) — the discrete logarithm problem — appears to be extraordinarily hard.

The analogy Diffie and Hellman used: Imagine mixing paint colors. It's easy to mix yellow and blue to get green, but nearly impossible to "unmix" green back into yellow and blue. In the protocol, Alice and Bob each add their secret "color" to a shared base color. They exchange the mixtures publicly, then each adds their own secret color to the other's mixture. Both end up with the same final color — but an eavesdropper who saw only the intermediate mixtures cannot determine it.

What Diffie and Hellman didn't know was that Malcolm Williamson at GCHQ had discovered the same protocol in 1974, but his work was classified. Like the RSA discovery by Clifford Cocks, the British invention remained secret for decades.

Diffie and Hellman received the 2015 Turing Award "for fundamental contributions to modern cryptography."

Why It Matters

  • TLS/HTTPS — Every secure web connection begins with a Diffie-Hellman (or ECDH) key exchange
  • SSH — Secure shell connections use DH to establish session keys
  • VPN — IPsec and WireGuard use DH variants for key establishment
  • Signal Protocol — The Double Ratchet uses repeated ECDH exchanges for forward secrecy
  • Perfect forward secrecy — Even if long-term keys are compromised, past sessions remain secure
  • Foundation of public-key cryptography — DH opened the door to RSA and all subsequent public-key systems

Prerequisites

  • Modular arithmetic (\(a \mod n\), modular inverse)
  • Exponentiation (\(g^a \mod p\))
  • Prime numbers
  • Basic group theory (cyclic groups, generators)

The Protocol

Public parameters: A large prime \(p\) and a generator \(g\) of the multiplicative group \(\mathbb{Z}_p^*\).

Step Alice Public Channel Bob
1 Picks secret \(a\) Picks secret \(b\)
2 Computes \(A = g^a \mod p\) \(A \longrightarrow\)
3 \(\longleftarrow B\) Computes \(B = g^b \mod p\)
4 Computes \(s = B^a \mod p\) Computes \(s = A^b \mod p\)

Shared secret: \(s = g^{ab} \mod p\)

The formula that makes it work:

\[ B^a \equiv (g^b)^a \equiv g^{ab} \equiv (g^a)^b \equiv A^b \pmod{p} \]

Derivation

Step 1: The Multiplicative Group \(\mathbb{Z}_p^*\)

For a prime \(p\), the set \(\mathbb{Z}_p^* = \{1, 2, 3, \ldots, p-1\}\) forms a group under multiplication modulo \(p\):

  • Closure: If \(a, b \in \mathbb{Z}_p^*\), then \(ab \mod p \in \mathbb{Z}_p^*\) (since \(p\) is prime, \(p \nmid ab\))
  • Identity: \(1\) is the identity element
  • Inverses: Every element has a multiplicative inverse (by Fermat's little theorem or the Extended Euclidean Algorithm)
  • Associativity: Inherited from integer multiplication

This group has order \(p - 1\) (there are \(p - 1\) elements).

Step 2: Generators and Cyclic Groups

A generator \(g\) of \(\mathbb{Z}_p^*\) is an element whose successive powers produce every element of the group:

\[ \{g^1 \mod p, \; g^2 \mod p, \; \ldots, \; g^{p-1} \mod p\} = \{1, 2, \ldots, p-1\} \]

Such generators exist for every prime \(p\) (a theorem from number theory: \(\mathbb{Z}_p^*\) is always cyclic). They are called primitive roots modulo \(p\).

Why we need a generator: If \(g\) is a generator, then \(g^a \mod p\) can take any value in \(\{1, \ldots, p-1\}\). This ensures that the shared secret is uniformly distributed, maximizing security.

Step 3: Why Both Parties Compute the Same Secret

Alice computes \(s_A = B^a \mod p\) and Bob computes \(s_B = A^b \mod p\). Are these equal?

\[ s_A = B^a = (g^b)^a = g^{ba} \pmod{p} \]
\[ s_B = A^b = (g^a)^b = g^{ab} \pmod{p} \]

Since \(ba = ab\) (multiplication of integers is commutative):

\[ s_A = g^{ab} = s_B \pmod{p} \]

Both parties arrive at the same shared secret \(s = g^{ab} \mod p\).

Step 4: Why an Eavesdropper Can't Compute the Secret

An eavesdropper (Eve) sees: \(p\), \(g\), \(A = g^a \mod p\), and \(B = g^b \mod p\).

To compute \(s = g^{ab} \mod p\), she needs either \(a\) or \(b\). Finding \(a\) from \(A = g^a \mod p\) is the Discrete Logarithm Problem (DLP).

The computational Diffie-Hellman (CDH) assumption states: given \(g\), \(g^a\), and \(g^b\), computing \(g^{ab}\) is hard — even without computing \(a\) or \(b\) individually.

Step 5: The Discrete Logarithm Problem

The best known classical algorithms for DLP in \(\mathbb{Z}_p^*\):

Baby-step giant-step (Shanks): Time and space \(O(\sqrt{p})\). This is why \(p\) must be large.

Index calculus: Sub-exponential time:

\[ O\!\left(\exp\!\left(c \cdot (\ln p)^{1/3} (\ln \ln p)^{2/3}\right)\right) \]

For a 2048-bit prime, this is computationally infeasible.

Comparison with ECDLP: On elliptic curves, index calculus does not apply. The best algorithm is Pollard's rho at \(O(\sqrt{n})\), which is why ECC keys can be much smaller.

Step 6: Efficient Modular Exponentiation

Computing \(g^a \mod p\) naively requires \(a - 1\) multiplications — far too slow when \(a\) has hundreds of digits. The square-and-multiply algorithm reduces this to \(O(\log a)\) multiplications:

To compute g^a mod p:
  Write a in binary: a = b_k b_{k-1} ... b_1 b_0
  Start with result = 1
  For i from k down to 0:
    result = result^2 mod p      (square)
    If b_i = 1:
      result = result * g mod p  (multiply)
  Return result

For a 2048-bit exponent, this requires at most 4096 modular multiplications instead of \(2^{2048}\).

Variables Explained

Symbol Name Description
\(p\) Prime modulus A large prime number (public)
\(g\) Generator A primitive root modulo \(p\) (public)
\(a\) Alice's secret A random integer, \(1 < a < p-1\)
\(b\) Bob's secret A random integer, \(1 < b < p-1\)
\(A\) Alice's public value \(g^a \mod p\)
\(B\) Bob's public value \(g^b \mod p\)
\(s\) Shared secret \(g^{ab} \mod p\)

Worked Examples

Example 1: Small Diffie-Hellman

Public parameters: \(p = 23\), \(g = 5\).

Alice picks \(a = 6\):

\[ A = 5^6 \mod 23 = 15625 \mod 23 = 8 \]

Bob picks \(b = 15\):

\[ B = 5^{15} \mod 23 \]

Using square-and-multiply: \(5^1 = 5\), \(5^2 = 2\), \(5^4 = 4\), \(5^8 = 16\), \(5^{15} = 5^8 \cdot 5^4 \cdot 5^2 \cdot 5^1 = 16 \cdot 4 \cdot 2 \cdot 5 = 640 \equiv 19 \pmod{23}\).

So \(B = 19\).

Shared secret:

Alice: \(s = B^a = 19^6 \mod 23\). Since \(19^2 = 361 \equiv 16\), \(19^4 \equiv 16^2 = 256 \equiv 3\), \(19^6 = 19^4 \cdot 19^2 \equiv 3 \cdot 16 = 48 \equiv 2 \pmod{23}\).

Bob: \(s = A^b = 8^{15} \mod 23\). Since \(8^2 = 64 \equiv 18\), \(8^4 \equiv 18^2 = 324 \equiv 2\), \(8^8 \equiv 4\), \(8^{15} = 8^8 \cdot 8^4 \cdot 8^2 \cdot 8^1 \equiv 4 \cdot 2 \cdot 18 \cdot 8 = 1152 \equiv 2 \pmod{23}\).

Both compute \(s = 2\). An eavesdropper who sees \(p = 23\), \(g = 5\), \(A = 8\), \(B = 19\) would need to solve \(5^a \equiv 8 \pmod{23}\) to find \(a = 6\) — trivial here, but infeasible for 2048-bit primes.

Example 2: Why the Eavesdropper Is Stuck

Eve sees \(A = 8\) and knows \(g = 5\), \(p = 23\). She needs to find \(a\) such that \(5^a \equiv 8 \pmod{23}\).

She could try all values: \(5^1 = 5\), \(5^2 = 2\), \(5^3 = 10\), \(5^4 = 4\), \(5^5 = 20\), \(5^6 = 8\). Found it: \(a = 6\).

But with \(p\) having 600+ digits, brute force is impossible, and the best algorithms are still sub-exponential. That's \(10^{100+}\) operations — more than the number of atoms in the observable universe.

Common Mistakes

  • Using small primes: \(p\) must be at least 2048 bits. Small primes make the discrete logarithm tractable.

  • Not using a safe prime: A safe prime has the form \(p = 2q + 1\) where \(q\) is also prime. This prevents Pohlig-Hellman attacks that exploit small factors of \(p - 1\).

  • Reusing ephemeral keys: DH secrets \(a\) and \(b\) should be freshly generated for each session. Reuse destroys forward secrecy.

  • No authentication: Vanilla DH is vulnerable to man-in-the-middle attacks. An attacker can intercept and replace \(A\) and \(B\) with their own values. Authentication (via digital signatures or certificates) is essential.

  • Confusing DH with encryption: DH establishes a shared secret — it doesn't encrypt messages directly. The shared secret is typically fed into a key derivation function (KDF) to produce symmetric encryption keys.

History

  • 1874 — Jevons speculates about one-way functions in The Principles of Science
  • 1974 — Malcolm Williamson at GCHQ invents the DH protocol (classified until 1997)
  • 1976 — Diffie and Hellman publish "New Directions in Cryptography"
  • 1977 — RSA is invented, realizing the public-key encryption that DH inspired
  • 1990 — ElGamal encryption scheme extends DH to direct encryption
  • 1999 — DH-based key exchange standardized in TLS
  • 2014 — Logjam attack shows many servers used weak 512/1024-bit DH parameters
  • 2015 — Diffie and Hellman receive the Turing Award
  • 2018 — TLS 1.3 mandates ephemeral (EC)DH, removing static DH

References

  • Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644–654.
  • Menezes, A., van Oorschot, P., & Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press.
  • Adrian, D., et al. (2015). Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. Proceedings of the 22nd ACM Conference on Computer and Communications Security.
  • Williamson, M. J. (1974). Non-Secret Encryption Using a Finite Field. CESG Report (declassified 1997).