Chapter 3

Key agreement — compute Diffie–Hellman by hand

Hand-compute Diffie–Hellman key agreement — building a shared key over a wiretapped path — with small primes. Through ECDHE and forward secrecy.

Building a shared key on a wiretapped path

Recall the homework Chapter 2 left us: symmetric encryption protects the traffic fast, but how do we share that first key? And the premise is harsh — the path between browser and server may already be wiretapped. "On a wiretapped path, create a shared secret the wiretapper cannot know" — the problem sounds impossible, and Diffie–Hellman (DH) key agreement solves it.

This chapter has exactly one goal: compute it yourself and be convinced. The only mathematics you need is powers and remainders (mod). If 17 mod 5 = 2 (17 divided by 5 leaves remainder 2) makes sense, you are ready.

The procedure — four steps

You and a server will build a key together. First, both of you agree — in public — on two numbers: a prime p and its companion g. To keep the arithmetic by hand, we use p = 23, g = 5 (the real thing merely uses a p hundreds of digits long; the procedure is identical).

Step 1 — Pick your secret

You pick a secret number a (say a = 6). The server picks its own secret b (say b = 15). Neither is ever sent

Step 2 — Compute and exchange public values

You send A = g^a mod p = 5⁶ mod 23 = 8. The server sends B = 5¹⁵ mod 23 = 19. Both may be wiretapped, and that is fine

Step 3 — Raise the peer's public value to your own secret

You: s = B^a mod p = 19⁶ mod 23 = 2. Server: s = A^b mod p = 8¹⁵ mod 23 = 2

Step 4 — Use the matching value as the seed of the shared key

Both sides computed g^ab mod p, so the values always match. From here on, a symmetric key derived from it protects the traffic at speed

Don't be intimidated by large exponents. The trick is to square repeatedly, reducing mod p each time. For 5⁶ mod 23: 5² = 25 ≡ 2 → 5⁴ = (5²)² ≡ 4 → 5⁶ = 5⁴ × 5² ≡ 4 × 2 = 8. The intermediate values never exceed 23.

Diagram of Diffie–Hellman key agreement: both parties exchange public values and each reaches the same shared secret locally

Only the public values A and B travel the path. The secrets a, b and the shared secret s never leave either side's hands.

Practice 3-1 — Run the key agreement with your own hands

The public parameters are p = 23, g = 5. Follow the steps in the text, writing intermediate values on paper.

Q1. Warm-up: what is 5³ mod 23?

Q2. Your secret value is a = 6. What public value A = 5⁶ mod 23 do you send? (Hint: build up from 5² mod 23)

Q3. The peer's public value B = 19 arrives. With your secret a = 6, what shared secret s = 19⁶ mod 23 do you compute? (Hint: 19 ≡ −4 (mod 23) makes it fast)

Verify with the simulator

The simulator below reproduces the key agreement with p = 23, g = 5. Drag your secret a and the server's secret b, and confirm two things: the two independently computed shared secrets always match, and no secret ever appears in the eavesdropper-visible values.

What the simulator does (text version): moving the a and b sliders updates the public values A = g^a mod p and B = g^b mod p, along with your side's computation B^a mod p and the server side's A^b mod p. However you choose a and b, the two results coincide, and the display color-codes which values an eavesdropper can see (p, g, A, B) versus cannot see (a, b, and the shared secret).

Why the eavesdropper learns nothing

The eavesdropper holds p = 23, g = 5, A = 8, B = 19. To get the shared secret they could, say, find the a with 5^a mod 23 = 8 — and for p = 23, brute force finds it instantly. It is solvable only because the numbers are tiny.

The real p has hundreds of digits. The "forward" computation — square and reduce — finishes in a flash, while the "reverse" computation of recovering the exponent (the discrete logarithm problem) does not finish in realistic time by any known method. This overwhelming asymmetry between forward and reverse is the entirety of DH's security. Nothing is hidden by encryption; the protection is that the reverse computation cannot keep up.

Actual TLS 1.3 runs the same idea on elliptic curves (ECDH), and the secret values are freshly generated and thrown away per connection (the E in ECDHE, ephemeral). That throwing away is what buys forward secrecy: an attacker who recorded every byte of ciphertext and later obtains the server's long-term private key still cannot reconstruct past session keys — the ephemeral values are long gone.

But one large hole remains

Now that the hand calculation is done, one mean question: whom did you just agree on a key with?

DH guarantees only that "you now share a secret with whoever exchanged public values with you." Whether that party is the genuine server or an attacker spliced into the path, DH alone cannot say. An attacker who sits in the middle and runs separate key agreements with you and with the real server can decrypt, read, and re-encrypt everything in transit (the man-in-the-middle attack). The next chapter's protagonist — the certificate — is the tool that closes exactly this hole.

What to take from this chapter

DH key agreement shares a secret without sending one — only public values travel the path
Security rests on the discrete logarithm being infeasible to reverse, against a fast forward direction
TLS 1.3 uses throwaway values (ECDHE), buying forward secrecy — past traffic stays safe even if keys leak later
DH builds a key with someone — it cannot say with whom. Certificates close that hole next