Sarah Laskow has a nice article in The Atlantic about the Diffie-Hellman key exchange. That’s an unlikely topic for the Atlantic, of course, but the article is more about Diffie and Hellman and how they changed everything with their protocol. My only complaint is that it doesn’t mention Ralph Merkle who was, and is recognized as, a co-inventor of the method.
For those who don’t know about it or are hazy on the details, the Diffie-Hellman key exchange method solves a seemingly impossible problem: how to publicly agree on a secret key for further communication. That means that even if every part of the negotiation is observed by a third party, the key still remains hidden.
The solution is surprisingly simple. Here’s a simple, but incorrect, version that illustrates the idea.
- Both sides, say Alice and Bob, first agree on a public integer \(g\)1.
- Alice chooses a large random integer \(r_{a}\).
- Alice sends \(g^{r_{a}}\) to Bob.
- Bob choose his own random integer, \(r_{b}\).
- Bob sends \(g^{r_{b}}\) to Alice.
- Alice computes \(g^{r_{b}r_{a}}\) by simply exponentiating the \(g^{r_{b}}\) that she got from Bob by \(r_{a}\).
- Bob calculates \(g^{r_{a}r_{b}}\).
But \(g^{r_{b}r_{a}} = g^{r_{a}r_{b}}\) so Alice and Bob have calculated the same number and agree to use it as their key.
The idea is that since an attacker can’t recover \(r_{a}\) from \(g^{r_{a}}\) or \(r_{b}\) from \(g^{r_{b}}\) he can’t compute \(g^{r_{a}r_{b}}\) to discover the key. Of course, an attacker can recover the exponent \(r\) from \(g^{r}\) by simply taking the logarithm so this method obviously isn’t secure. The Diffie-Hellman method solves this problem by making all the calculations in a multiplicative group \(G\) with \(g \in G\) a generating element of \(G\).
That’s a bit abstract so let’s look at a group, \(G\), that you’re probably familiar with. One way of making the calculations is to use the finite field \(\mathbb{Z}_{p}\) for some prime \(p\) and \(g\) a primitive root of \(\mathbb{Z}_{p}\). Everything I described above still holds except the multiplications and exponentiations are performed modulo \(p\). But now recovering the exponents is no longer simple. It’s called the discrete logarithm problem and is believed to be of the same order of difficulty as the factoring of large numbers, rendering the Diffie-Hellman method about as secure as, say, RSA encryption2.
Footnotes:
In practice, \(g\) is known in advance and is one of several published numbers used for the method.
There has been some recent progress on the discrete logarithm problem, but not with the type of groups used for Diffie-Hellman. Experts believe Diffie-Hellman is still secure and will be for the foreseeable future.