Diffie-Hellman key exchange

Cryptography is very very old. Over two thousand years ago, Julius Caesar used the Caesar substitution cipher to encrypt communications with his generals. There are examples of similar ciphers going even further back.

Until recently, one of the biggest challenges of all reasonably secure cryptography was that you needed a secret key distributed separately to the encrypted communications. Encryption methods like the famous Enigma machine or the Lorenz cipher required a secret key to ensure the encrypted message could not be decoded by someone with knowledge of the cipher used. Adding a secret key to the Caesar cipher gives you the significantly stronger Vigenère cipher.

So you needed to be prepared to use cryptography, having exchanged keys prior to starting your secure communication. As recently as World War II, armies needed to distribute books of keys to their staff to decrypt messages from headquarters. Enemy capture of an officer with a code book would mean creating an entirely new series of keys and distributing them across much of the world.

In 1976, Whitfield Diffie and Martin Hellman published their method for public exchange of a secret key. This became known as Diffie-Hellman key exchange, and was the first known way to distribute keys for secure communication that didn’t involve transmitting the key by some private mechanism first.

The exchange method is one of the most elegant algorithms to be discovered in modern times. It relies firstly on a simple mathematical fact:

(x^y)^z = (x^z)^y

And secondly, it relies on the lack of any efficient algorithm to determine the values y and z above, if you only know x and the final result modulo a large prime number. This is known as the discrete logarithm problem, and is one of the few asymmetric problems in mathematics. Being asymmetric in this sense means that there is an efficient algorithm to calculate the result given the inputs, but there’s no efficient way to determine the inputs from the result.

In terms of an equation, the discrete logarithm problem is to find an efficient algorithm for determining x, given g, p and n:

n = g^x mod p

Here’s how Diffie-Hellman key exchange works:

1. Alice and Bob agree on a long prime number, p, and a base g. The base, g, doesn’t need to be large; it is normally 2 or 5.

2. Alice creates a long prime number, a, which is her private key. She calculates A = g^a mod p. She sends A to Bob.

3. Bob creates his own long prime number, b, which is his private key. He calculates B = g^b mod p. He sends B to Alice.

4. Alice gets B from Bob, and calculates the shared key: K = B^a mod p.

5. Bob gets A from Alice, and calculates the same shared key: K = A^b mod p.

6. Now, Alice and Bob have calculated respectively K = (g^a)^b mod p and K = (g^b)^a mod p. From the first formula above, we know these are actually the same value: the shared key which Alice and Bob will use to communicate securely.

Any eavesdropper, Eve, has access to p, g, A, and B. However, she cannot determine the private keys a and b, or the shared key K from these values efficiently. Given sufficiently large private keys and a large value for p, current algorithms cannot determine these values within the life of the universe.

Clearly the Diffie-Hellman key exchange process was only practical once computers were developed. Finding large prime numbers and raising them to large powers would have taken a long time without fast calculating machines.

This algorithm was a landmark discovery in the history of cryptography. Without it, later developments in public key cryptography could not have happened and much of the infrastructure for secure communications today would not exist.

Technical note: I’m using mod in the above equations as the modulo operator which calculates the remainder of a division, not to indicate the congruence relationship of mathematical modular arithmetic (of which the result of the modulo operator is only a subset).