The Diffie-Hellman Key Exchange Protocol

Suppose you wish to purchase something from Amazon.com, but have never done so before. You, of course, need to get your credit card number to the folks at Amazon -- and you wish that transmission to be secure.

Given the design of the internet, however, your credit card number must travel through several different machines on its way to its final destination. Your card number must travel through machines not controlled by you or Amazon. Thus, to keep your card number a secret, it will have to be encrypted. This, however, requires that you and Amazon agree upon a key for that encryption.

So, since all communication with Amazon essentially occurs on a public channel -- the discussion about what key to use must be kept secret as well. So it would seem that discussion would then need to be encrypted as well -- which would require yet another key. But then to transmit this other key, we again need a secure conversation...

Do you see "the chicken vs. the egg" problem here?

Amazingly, there is a way for two entities, say "Alice" and "Bob", to securely agree upon a secret key -- even with an eavesdropping enemy agent, say "Eve", listening in on their conversation. Here's one process for doing this, called the Diffie-Hellman Key Exchange Protocol...

  1. Alice and Bob first agree (where Eve can hear) on two large numbers -- a prime modulus $m$, and a base $p$ (which is a primitive root for $m$).

  2. Alice and Bob both choose secret numbers, $a$ and $b$ respectively, that they won't reveal to anyone (including each other). As these numbers are never discussed, Eve never directly learns what their values are.

  3. Using the method of successive squaring, Alice calculates $A \equiv p^a\pmod{m}$ and transmits its value to Bob, while Bob similarly calculates $B \equiv p^b\pmod{m}$ and transmits its value to Alice. Note: Eve sees both of the numbers transmitted, but provided the values of $p$ and $m$ are sufficiently large, she is still unable to ascertain the "secret" values of $a$ and $b$, as solving the corresponding congruences becomes an intractably hard problem.

  4. Finally, Alice takes Bob's transmitted value $B$ and raises it to the $a^{\textrm{th}}$ power$\pmod{m}$, while Bob take's Alice's transmitted value $A$ and raises it to the $b^{\textrm{th}}$ power$\pmod{m}$. Note, that these two values must be the same as
    $$B^a \equiv (p^b)^a = (p^a)^b \equiv A^b \pmod{m}$$
    Alice and Bob may now use this common value (that Eve can't compute, since she doesn't know $a$ or $b$) as a key to encode the rest of their conversation.

This method is called the Diffie-Hellman Key Exchange Protocol.