One question I get from course participants when I teach Learning Tree’s System and Network Security Introduction is, “How does Diffie-Hellman key exchange work?” I’ll answer that for you here with a slightly simplified explanation (the details I’m leaving out deal with intricacies of discrete math).
First, let’s look at why we need Diffie-Hellman (DH) key exchange in the first place. If you had an office in, say, London, and a new employee in Hong Kong with whom you wanted to communicate – absent any public key encryption – you’d need to somehow share a secret encryption key with the employee. You could fly there and deliver it, I suppose, but as the number of employees grew, managing the keys would be a daunting task.
Enter Diffie-Hellman (or Diffie-Hellman-Merkle) key exchange. The basic idea is simple, but the work to discover the details took a while. While Diffie and Hellman weren’t the first to figure it out, they were the first to publish about it. That’s because the British mathematician and cryptographer who thought it up first, were bound by secrecy laws not to disclose it! To be fair, James Ellis and Clifford Cocks were likely the first to think this stuff up.
Let’s get to it. DH first requires the two communicating parties – we’ll call them Alice and Bob – to agree on two numbers: a large prime p and a random number g less than p-1 and greater than 1. By “large prime” we mean something like 2048 bits. They can exchange these “in the clear” as they are not enough for an attacker to use to discover the secret Alice and Bob are about to generate. In fact, there are standard values for these that are sometimes used.
Next, Alice and Bob each choose a secret number. Let’s say Alice chooses a and Bob chooses b. Alice then computes A = ga mod p, while Bob computes B = gb mod p. Mod is the interesting mathematical function that represents the division remainder. That is x mod y is the remainder when x is divided by y. So 10 mod 3 is 1 because the remainder when 10 is divided by 3 is 1.
Alice sends A to Bob and Bob sends B to Alice. Here is where the interesting math comes in. Alice computes s = Ba mod p and Bob computes s = Ab mod p and they each have the same value for s. Let’s see how that works:
Bob’s s is Ab mod p which can be written as
(ga mod p)b [remember that A = (ga mod p)] or
(ga)b mod p or
(gb mod p)a mod p which is the same as
Ba mod p which is Alice’s s, too.
So Bob and Alice have the same value for s!
Wikipedia has an illustration of this using colors:
The reason this works (the numbers, not the colors) is that finding ga mod p, even knowing g and p is very difficult with current computers. It turns out that the mod function makes this an especially difficult problem called the discrete logarithm problem.
Alice and Bob can now use s as a secret key for AES or other secret-key encryption methods, provided it was generated with the proper length.
There is more to DH key exchange and there is even a version using elliptic curve cryptography. I won’t go into these now, but will likely discuss some of them in the future.
To your safe computing,