?

Log in

No account? Create an account

Previous Entry | Next Entry

The beauty of Diffie-Hellman

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.

  1. 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.
  2. Alice generates a large random number a, which does not need to be prime. She then calculates a′ = ga mod P and sends that to Bob over the insecure line. The operation needed to get a from ga mod P given g and P is called a discrete logarithm, and is very slow and difficult to perform.
  3. Bob generates a large random number b, calculates b′ = gb mod P and sends it to Alice over the insecure line. Note that this also requires a discrete logarithm to reverse.
  4. Alice calculates K = (b′)a mod P. Bob calculates K = (a′)b mod P. Both Alice and Bob arrive at the same K because gba mod P is just another way of writing gab mod P.
  5. 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, ga mod P, and gb 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.

Tags:

Comments

( Read 4 comments — Leave a comment )
codepoetica
Oct. 27th, 2005 09:06 pm (UTC)
I got really confused over DH when dealing with OpenID's crypto requirements. I wish I was taught this in grade 6 as well.
gaal
Nov. 7th, 2005 09:28 pm (UTC)
You'd also need to explain to the prospective sixth graders how a secret K is actually useful for encrypting a message. This is as feasible as explaining DH itself, but possibly takes longer.
brentdax
Nov. 7th, 2005 09:55 pm (UTC)
Heck, that's just a matter of teaching them the Caesar cipher. With P = 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.
gaal
Nov. 7th, 2005 10:04 pm (UTC)
That would only be as strong as Caesar, and goes against the bit in the DH description that recommends a large P.

("Goes against" in the pedagogical sense, as well as the cryptographic one.)
( Read 4 comments — Leave a comment )