Agreeing a secret in public

Two jugs each pour out a ribbon of colour — deep green on the left, blue on the right — which cross in the middle and end up in two bowls of exactly the same ochre.

The last chapter ended at a wall. You and your friend need the same key, but you can't send it over — then the eavesdropper reads along. And you can't send it encrypted either, because for that you'd need a key all over again. In 1976 two mathematicians showed that the wall isn't there. You can agree on a secret while everyone is listening in. This chapter is about nothing else, and by the end you'll have done it yourself.

Words you might need

Key exchange: Two people ending up on the same secret number, without that number ever going over the line. Not: sending a key across. Instead: both working one out separately that happens to be identical.
Shared secret: The number you both end up on. You then turn it into an AES key, and you're back at the previous chapter.
Diffie–Hellman: The name of this trick, after Whitfield Diffie and Martin Hellman, who published it in 1976. Often shortened to DH.
Clock arithmetic (modulo): Arithmetic where you start again at 0 past a limit, the way a clock starts again at 1 after 12 hours. 17 mod 12 = 5. Sounds like a trick for children; it's the engine underneath this whole thing, and you'll see why in a moment.

The magic trick with paint

This is the picture the inventors used to explain it themselves:

You and your friend pick a colour together, out loud: yellow. Everyone hears that.
Each of you secretly picks a colour of your own. You red, she blue. You tell nobody.
Each of you mixes your secret colour with yellow, and sends the mixture to the other. Everyone sees orange and green go past.
You mix the green you got with your red. She mixes your orange with her blue. You both end up on exactly the same brown.

The eavesdropper has seen yellow, orange and green. But paint can't be unmixed — he can't get your secret red and blue back out of it. You have a shared secret, and nobody else has it.

From paint to numbers

Mixing paint is easy and unmixing it is impossible. There's a calculation with exactly that property: raising to a power on a clock. Replace the colours with numbers and you get this, with a clock of 23:

Paint	Number	Who knows it?
yellow (agreed)	g = 5 and p = 23	everyone
your red	a	only you
her blue	b	only her
your orange	A = 5^a mod 23	everyone, it goes over the line
her green	B = 5^b mod 23	everyone, it goes over the line
the brown	B^a mod 23 = A^b mod 23	only the two of you

That last line is the whole trick, and it holds for a reason you already know from maths class: (5^b)^a and (5^a)^b are both 5^a·b. You and she do the same multiplication in a different order, so you end up on the same thing.

Try it yourself

Everything happens in your browser. Nothing is sent to the server.

Click Agree on a secret. The demo plays both you and Noor at once: a secret number each, a calculation each.
Look at the two bottom lines. Different sums, same answer.
Click a few more times. Different secret numbers, different outcome, and still always the same on the left and the right.
Click Now with real keys. Same trick, but on the curve from the next chapter and with a 256-bit secret.

Why the eavesdropper gets stuck

He has seen everything except a and b. He knows that A = 5^a mod 23, and he wants a. On a clock of 23 that's done in no time: he tries 5¹, 5², 5³… until it fits. Twenty-one attempts at most.

But without a clock it would have been just as quick — then raising to a power rises neatly, and he can simply guess roughly how big a is. It's the clock arithmetic that wrecks it: because of that modulo the outcomes jump about all over the place, and the size of A no longer says anything about a. Set p to a number of 600 digits and there's no other way than trying them all. That's the wall he runs into.

What this does and doesn't solve

Does	Doesn't
Two people who have never met end up on the same key with everyone watching.	Who you agreed that key with. There was no name attached to that number. For that you need chapter 7.1.
The key never goes over the line, so it can't be intercepted.	Sending something to someone who isn't online. This needs two parties taking part at the same time.

That first gap is no detail. If someone plants himself in the middle and agrees a secret separately with each of you, then you think you're talking to each other while he reads everything. He's called a man-in-the-middle, and keeping him out is a problem of its own — chapter 7.1.

This is not encryption. Nothing here has been encrypted and nothing decrypted. All you've done is agree on a key. What you do with that key afterwards is plain AES from chapter 4. So don't confuse this with the next chapter, where things really are encrypted directly with a key that anyone may have. Two different ideas, both from the same years, and they get mixed up constantly.

This is math: the discrete logarithm

An ordinary logarithm is the way back from raising to a power: out of 5^x = 125 you get x = 3, and your calculator does that in a blink. Put a clock around it and that way back disappears. From 5^x mod 23 = 8 it follows that x = 6, but there's no formula that gives you that — you can only try. That's called the discrete logarithm problem.

The strange thing is that nobody has proved that it is hard. It's just that in fifty years no fast way has been found. The entire security of the internet rests on a hunch — and on the fact that an awful lot of clever people have tried. That's number theory, and it's one of the few subjects where "nobody knows" is a workable answer.