Brent Dax (brentdax) wrote,
Brent Dax

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: hacking

  • Paging madlori (and anyone who knows her)

    An interesting thing just happened on Facebook chat. Lori Summers [2:29:44] Got my message ? Brent Royal-Gordon [2:33:45] I did. Lori Summers…

  • guest post

    kate is the best better than the rest the best the best haikus about kate: kate's my favourite i want to lick her ballsack it would taste so…

  • Practice

    This December, I will have been practicing programming seriously for ten years. That will mark the tenth anniversary of me starting to learn Perl. I…

  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.