When it comes to the Diffie-Hellman algorithm, there seem to be many confusions from newbies in Cryptography as to whether an attacker could easily recompute the shared key by intercepting the prime numbers + public keys. While the answer is “no”, understanding why, requires an understanding the discrete logarithm problem. So here we go.

### Discrete Logarithm Problem

The discrete logarithm problem can be summarized as follow:

Given a prime, compute

In other words, is defined to be a primitive root of the finite group of order and we need to calculate the exponential such as resolving .

The logarithm is then calculated modulo the order of in the finite group such that if .

Because the discrete logarithm is not NP-complete, it is not possible to compute our in polynomial time and therefore generating a big prime number to be used in generating a cryptographic key renders exhaustive search attack completely useless.

### DH Overview

Before we dive further, here is a very short reminder of the DH algorithm:

User1 and User2 agree on a prime number and a generator such as there exist an exponent so that .

Both users secretly generate a random key, let’s call it ( for User1 and for User2); from there on, and are used by both users to generate their public keys.

The public key equation is: , let’s call it

After both users compute ( for User1 and for User2), they exchange their public keys. The shared secret key can then be generated from the opposite user’s public key.

The secret key equation is:

- User1:
- User2:

As you can see, to recompute the shared key, the attacker would need to resolve the discrete logarithm problem as discussed earlier, that is, detect and from and , since it is not possible to directly compute ; after all and not .

There are of course many algorithms that attempt to resolve the discrete logarithm, such as the “squarre root attack”, but this is the subject for another post.

I hope this clarifies to new comers why DH is secure enough to be used in key exchange.