Diffie-Hellman Key Exchange

Two parties agree on a shared secret over an open channel without ever sending it — security rests on the hardness of the discrete logarithm.

9 min read Watch it move Build it

Diffie-Hellman lets two strangers agree on a shared secret key while everything they send is public. Nobody ever transmits the key itself — both sides *compute* the same number independently. An eavesdropper sees every message and still cannot reconstruct it. It's the move that bootstraps encrypted sessions across the open internet.

The paint analogy

Start from a shared public colour. Each side stirs in a private colour and swaps the *mixtures*. Each then stirs their own private colour into the mixture they received. Both land on the identical blend — yet un-mixing paint to recover a private colour is the hard part an attacker can't do.

The exchange, step by step

1Agree publicly on a large prime p and a generator g (both can be sent in the clear, or be well-known constants).
2Alice picks a private a, computes A = g^a mod p, and sends A.
3Bob picks a private b, computes B = g^b mod p, and sends B.
4Alice computes s = B^a mod p. Bob computes s = A^b mod p.
5Both get the same s = g^(ab) mod p — the shared secret, never transmitted.

It works because exponentiation commutes: (g^a)^b = (g^b)^a = g^(ab) — all taken mod p. The attacker sees g, p, A, and B, but recovering a from A = g^a mod p is the discrete logarithm problem, which has no known efficient solution for large primes.

Public:  p = 23, g = 5
Alice:   a = 6   ->  A = 5^6  mod 23 = 8
Bob:     b = 15  ->  B = 5^15 mod 23 = 19
Alice:   s = B^a mod 23 = 19^6 mod 23 = 2
Bob:     s = A^b mod 23 = 8^15 mod 23 = 2
Shared secret = 2  (never sent on the wire)

Unauthenticated DH is wide open to man-in-the-middle

Plain Diffie-Hellman proves nothing about *who* you exchanged keys with. An attacker who sits in the middle can run two separate exchanges — one with each side — and relay traffic. Real protocols (TLS) pair DH with signatures or certificates to authenticate the parties.

OperationTimeSpace

Compute a public/shared value · square-and-multiply modular exponentiationO(log a)O(1)

Break it (discrete log) · infeasible for large p — the whole pointsub-exponential—

Check yourself

What does an eavesdropper who records the entire exchange need to compute to recover the shared secret?