Diffie-Hellman and discrete logs

The security of the Diffie-Hellman key exchange is related to the difficulty of calculating discrete logarithms, but a closer look at the problems shows that it's actually a bit more subtle than you might first think.

We can describe the Diffie-Hellman key exchange roughly like this:

1. Alice picks a value for g and uses her private key a to calculate g^a, which she sends to Bob along with g
2. Bob uses his private key b to calculate g^b, which he sends to Alice
3. Alice calculates the shared secret g^ab as (g^b)^a
4. Bob calculates the shared secret g^ab as (g^a)^b

So an adversary who sees Alice and Bob carry out these steps sees g, g^a and g^b. From this information, the adversary wants to find the shared secret g^ab. We can summarize this in what's called the computational Diffie-Hellman problem (CDHP):

CDHP: Given g, g^a, g^b, find g^ab

We assume that the only way that an adversary can do this is by calculating discrete logarithms. In particular, we assume that they either need to find the value of a from g^a and then use it to calculate g^ab, or to find the value of b from g^b and then use it to calculate g^ab. There's no proof that this is actually the case, although it’s probably true. This means that there may be ways to defeat the security of the Diffie-Hellman key exchange that don't require calculating discrete logarithms. But if you can calculate discrete logarithms then you can clearly solve the CDHP.

So the security of the Diffie-Hellman key exchange is really based on two assumptions. The first is that the only way to solve the CDHP is by calculating discrete logarithms. The second is that calculating discrete logarithms is hard. So although people often talk about the security of the Diffie-Hellman key exchange as being based on the difficulty of calculating discrete logarithms, it's actually a bit more complicated than that. It's really based on the difficulty of solving the CDHP.