When you send a message online, it often travels through places you don't control like Wi-Fi hotspots, servers or networks where anyone along the way could see it. That sounds scary, but modern cryptography has a neat solution: the Diffie-Hellman key exchange.
At a high level, it solves a simple but crucial problem:
How can two people agree on a shared secret if everyone can see the conversation?
Imagine Alice and Bob want to communicate over the internet, but Eve is
always listening. The trick is to agree on a secret numerical key
without Eve ever knowing it. This key is like a password that only they share, and once they have it, they can encrypt their messages so that even if Eve intercepts them, she won’t be able to understand anything.
Let's first think about it in colors:
- Mixing two colors is easy: you can combine them to create a third color.
- Undoing the mix is hard: given the resulting color, we cannot figure out the originals.
This is what a one-way function looks like, we can mix any colors we want, but never separate them perfectly once mixed. Bob and Alice will use this to agree on a secret key, here's how it works:
- Alice and Bob agree on a public color that everyone, including Eve, can see.
- Each chooses a private secret color.
- They mix their private color with the public color and send the mixtures to each other.
- When they receive the other's mixture, they add their own private color again.
The result? Both end up with the same secret color, a shared key only they know. Anyone watching can see the public color and the mixtures, but cannot reverse the process to uncover the secret, just like trying to unmix paint.
The math behind the Diffie-Hellman key exchange
The paint analogy is a simple way to visualize the idea, but behind the scenes, Diffie-Hellman uses numbers and a little modular arithmetic:
- Agree on a public number and a base
Alice and Bob first agree on a large prime number \(p\) and a second number \(g\) called the base or generator. These numbers are public, just like the public color in our analogy. Anyone, including Eve, knows them.
- Pick private numbers
Alice and Bob now choose a private number each, let's call them \(a\) for Alice and \(b\) for Bob. These numbers are kept secret and play the role of their private colors.
- Compute public values and share them
Alice computes a value using the public numbers and her private number:\[
A = g^a \bmod p \quad \text{(Alice's public or "mixed" value)}
\]Bob does the same using his own private number:\[
B = g^b \bmod p \quad \text{(Bob's public or "mixed" value)}
\]We usually name these values \(A\) for Alice and \(B\) for Bob. Think of this step as mixing the public color with a secret color and sending the result. It is visible to everyone, but it does not reveal the private numbers and the public values can't be easily reversed.
- Combine the received public value
Now each side uses the value they received and applies the same operation again with their own private number:
\[
\text{Alice received B and computes: } K = B^a \bmod p
\]\[
\text{Bob received A and computes: } K = A^b \bmod p
\] The magic here is that both calculations result in the same value \(K\). This is the shared secret.
Now that we understand the steps, we can write the idea in its most common mathematical form: \[
(g^a \bmod p)^b \bmod p
=
(g^b \bmod p)^a \bmod p
\]This equality is what makes the Diffie-Hellman key exchange work. Even though Alice and Bob never send their private numbers, they still arrive at the same secret key.
A simple implementation in Python
Choosing \(g\) and \(p\) values
Diffie-Hellman Groups
Security considerations