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. (gis often 2 or 5;Pshould 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 calculatesa′=gmod^{a}Pand sends that to Bob over the insecure line. The operation needed to getafromgmod^{a}PgivengandPis called a discrete logarithm, and is very slow and difficult to perform.- Bob generates a large random number
b, calculatesb′=gmod^{b}Pand sends it to Alice over the insecure line. Note that this also requires a discrete logarithm to reverse.- Alice calculates
K=(b′)mod^{a}P. Bob calculatesK=(a′)mod^{b}P. Both Alice and Bob arrive at the sameKbecausegmod^{ba}Pis just another way of writinggmod^{ab}P.- Alice and Bob use
Kas the key to an encryption algorithm, and happily communicate in complete secrecy. Eve, having only the fairly useless values ofg,P,gmod^{a}P, andgmod^{b}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.

## Comments

brentdaxP= 23, DH will produce keys suitable to be used as Caesar shifts, and the numbers involved will be reasonably sized for a calculator and paper.gaalP.("Goes against" in the pedagogical sense, as well as the cryptographic one.)