Diffie-Hellman: how two strangers agree on a secret while everyone listens

When you open a website that starts with https://, your browser and the website have never met, yet within a fraction of a second they share a secret key and start scrambling everything they say. Anyone listening on the Wi-Fi sees every message and still cannot work out the key. How can two strangers agree on a secret in public?

The problem: a secret you must send over a wire you cannot trust

Encryption means scrambling data so that only someone with the right key (a secret number) can read it. Fast, everyday encryption uses the same key to scramble and unscramble. That is great, with one catch: both sides need the key before they start, and sending it across the internet would let anyone along the route copy it.

The trick that solves this was published in 1976 by Whitfield Diffie and Martin Hellman, and is called Diffie-Hellman key exchange. It lets two sides build a shared secret out of numbers that are safe to say out loud.

The one-way street: modular arithmetic

The trick needs an operation that is easy to do forwards and painfully slow to undo. It uses modular arithmetic, which is clock arithmetic: x mod 23 is the remainder after dividing by 23, so the numbers wrap around like the hours on a clock face.

Take two public numbers: a prime p (the size of the clock) and a number g (the "base"). Computing gx mod p is quick even for huge numbers. Going backwards, from the result to the x that produced it, has no known shortcut for well-chosen numbers. It is called the discrete logarithm problem.

The exchange, in four steps

Here Alice is your browser and Bob is the website. Everyone may know p = 23 and g = 5.

1. Alice picks a private number a and keeps it secret. Bob picks his own private number b.
2. Alice sends A = ga mod p. Bob sends B = gb mod p. These travel in the open.
3. Alice computes Ba mod p. Bob computes Ab mod p.
4. Both results are the same number, because (gb)a = (ga)b = gab. That number is the shared secret.

Here it is as Python (I ran this exact code):

p, g = 23, 5          # public: everyone may see these
a, b = 6, 15          # private: each side keeps its own secret

A = pow(g, a, p)      # Alice sends this
B = pow(g, b, p)      # Bob sends this
print("Alice sends", A)
print("Bob sends  ", B)
print("Alice computes", pow(B, a, p))
print("Bob computes  ", pow(A, b, p))

# What an eavesdropper must do: try every exponent until g**x matches A
for x in range(1, p):
    if pow(g, x, p) == A:
        print("Eavesdropper finds x =", x, "after", x, "tries")
        print("...and then computes", pow(B, x, p))
        break

Output:

Alice sends 8
Bob sends   19
Alice computes 2
Bob computes   2
Eavesdropper finds x = 6 after 6 tries
...and then computes 2

Try it: you are the eavesdropper's problem

Move the sliders to choose each side's private number. Watch the shared secret match on both sides. Then pick the bigger clock and see what the eavesdropper has to do.

Why a bigger clock matters

With p = 23 an eavesdropper needs at most 22 guesses, which is no protection at all. Make p a thousand times bigger and the guessing takes a thousand times longer in the worst case, and the bigger toy above already takes thousands of guesses. Real systems go much further. Instead of the plain numbers used here, TLS 1.3 typically uses the same idea on elliptic curves (a different kind of one-way maths), most commonly a curve called X25519, where the secrets are around 256 bits long. Brute-force guessing at that size is out of reach.

What this has to do with the padlock

TLS (Transport Layer Security) is the protocol behind https://. Version 1.3 is defined in RFC 8446. Its handshake uses exactly this kind of Diffie-Hellman exchange to produce a fresh shared secret for every connection, then derives the actual encryption keys from it.

There is one thing the exchange does not do: it does not tell Alice who she is talking to. Someone sitting in the middle could run one exchange with Alice and another with Bob. That is why the website also sends a certificate and proves it holds the matching private key. The certificate is vouched for by a certificate authority your browser already trusts. Key exchange gives you a secret; the certificate tells you the secret is shared with the right party.

So what, for your own code

• Never invent your own key exchange or encryption. Use TLS through your language's HTTPS libraries and let it do the maths.
• A tiny p is as good as no secret. Real software chooses sizes carefully, which is another reason to use well-tested libraries.
• The padlock means "the connection is encrypted to the site that owns this certificate", not "this site is honest".

Next time you load an https:// page, remember the handshake: two sides shout numbers across a crowded room, and both walk away with a secret nobody else heard.