I admit that key exchange algorithms aren’t necessarily simple, but Diffie-Hellman is so fundamental to encrypted communication we need to cover it.
Assume you need to communicate with a friend privately, but you have no private medium through which to communicate. If you could be in the same place at the same time, you could share a symmetric encryption key. Being separated by space and untrusted eavesdroppers, this is impossible. You need to devise a way to create a shared, secret key using potentially untrusted communication channels.
This is the core of what Diffie-Hellman empowers.
A trivial example
To illustrate how this key exchange works, let’s walk through the math with small numbers. This example should be easy to follow offline, but it is not intended for use to protect anything critical. I’ll explain why at the end.
Diffie-Hellman builds on top of modulo arithmetic using prime numbers. It uses prime numbers as they have no integer factors, which renders the modulo operation even more secure. It’s difficult for an attacker to “undo” the operation.
Walking through the exchange
Let’s start with our two parties – Alice and Brooke. They need to have a secure way to communicate without Charles, a malicious third actor intercepting their messages, knowing what is said.
Alice and Brooke first agree on two prime numbers – g (a generator) of 5 and p (the prime modulus) of 17. These numbers don’t need to be kept secret.
Alice then picks a secret number (she picks 6 and calls this a) and computes her public key (A) based on that number. She uses the following equation:
Alice sends this number (2) to Brooke using whatever channel is available. It doesn’t matter that Charles can see the number – it’s impractical to reverse the modulo exponentiation here to extract Alice’s secret key.
On the other side
Meanwhile, Brooke picks her own secret key b (for example, 19) and uses the same formula to compute a public key (B):
Then, Brooke uses her secret key and Alice’s public key to compute a shared key. The formula here should be familiar. Note that b is Brooke’s secret key and A is the public key Alice sent earlier:
Alice computes the same thing, but leveraging her own secret key (a) and Brooke’s public key (B):
Now, Alice and Brooke have a shared secret they never communicated directly with one another. Even if Charles saw every message they exchanged, he would be unable to compute this secret number. Alice and Brooke can then leverage a shared symmetric encryption algorithm to communicate securely.
In practice
Diffie-Hellman is used all over the place to create keys for symmetric encryption to empower communication between trusted parties over an untrusted network. In practice, though, it uses keys far larger that those in this example.
A “secure” prime modulus for Diffie-Hellman should be at least 2048 bits in length (this is 617 decimal digits). Our example modulus is only 5 bits in length and is nowhere near being secure. Likewise, the public and private keys in a secure implementation would be similar in length to the modulus, meaning modulo exponentiation becomes much more complicated.
Modern TLS for web communication leverages Diffie-Hellman over elliptic curves, which is a quite a bit faster than modulo arithmetic with prime numbers. We’ll cover some basics in elliptic curve cryptography later on.