I read about an algorithm called Diffie-Hellman Key Exchange yesterday. Basically, it's a way for two people to come up with the same number without allowing a third person who's listening in on them figure out what the number is.

It's not even that mathematically difficult; the only math you need that most people don't know is called a

modulus

. Modulus is used a lot by programmers; it really just means

divide and take the remainder

. (Remember remainders from third-grade long division?) So when I write

Something mod X

, that means

divide Something by X and take the remainder

.

Without further ado, the algorithm:

Alice and Bob want to communicate securely. Unfortunately, the only communications medium they have available to them is a telephone line which Eve, an eavesdropper, has tapped. (Or maybe it's an Internet connection and Eve has access to the routers between them, or it's a shortwave radio that Eve can listen in on, or it's snail-mailed postcards and Eve works at the post office. It doesn't matter—the principle is the same.) They have some kind of encryption available to them, but they need a shared secret value to use as a key.

- Alice and Bob agree on a large random prime number,
*P*, and a small prime number, *g*. (*g* is often 2 or 5; *P* should be hundreds of digits long.) They can do this beforehand and are free to reuse these values. They need not be kept secret. - Alice generates a large random number
*a*, which does not need to be prime. She then calculates *a′* = *g*^{a} mod *P* and sends that to Bob over the insecure line. The operation needed to get *a* from *g*^{a} mod *P* given *g* and *P* is called a discrete logarithm, and is very slow and difficult to perform. - Bob generates a large random number
*b*, calculates *b′* = *g*^{b} mod *P* and sends it to Alice over the insecure line. Note that this also requires a discrete logarithm to reverse. - Alice calculates
*K* = *(b′)*^{a} mod *P*. Bob calculates *K* = *(a′)*^{b} mod *P*. Both Alice and Bob arrive at the same *K* because *g*^{ba} mod *P* is just another way of writing *g*^{ab} mod *P*. - Alice and Bob use
*K* as the key to an encryption algorithm, and happily communicate in complete secrecy. Eve, having only the fairly useless values of *g*, *P*, *g*^{a} mod *P*, and *g*^{b} mod *P*, can't understand what they're saying.

That's actually not too bad for a field famed for its mathematical difficulty. And it's very elegant: there are few secrets (just

*a*,

*b*, and the shared secret

*K*), it's built on elementary-school arithmetic, it scales to your computational resources (you could do it with pencil and paper, a calculator, a handheld, a PC, or a supercomputer, each time using larger numbers), and it very cleverly leverages a difficult problem in math. And the context of this makes it even more amazing—Diffie-Hellman was the first time anybody figured out how to communicate securely over an insecure channel without needing a secure one to set things up.

You could teach this to sixth-graders. Actually, I kind of wish they

*would* teach it to sixth-graders; it's certainly more interesting than anything

*I* studied in sixth-grade math.