The problem of the discrete logarithm

The security of Diffie-Hellman hinges on a specific problem which mathematicians have not yet been able to solve effectively.

The problem

Given g, p and A, find the exponent a such that:

g^a mod p = A

This is the discrete logarithm problem. On the real numbers, the logarithm can be calculated without difficulty. Modulo p, the function loses all regularity: the successive powers of g jump haphazardly within the interval, and there is no indication as to whether one is approaching the target.

5^1=5   5^2=2   5^3=10   5^4=4   5^5=20   5^6=8   ...     (mod 23)

There is no monotonicity, so no binary search is possible.

What we know how to do

The best-known algorithms, such as the number field sieve, remain sub-exponential: much faster than brute-force enumeration, but far from being feasible on a 2048-bit p.

Be careful, however: this problem is not proven to be hard. We only know that, after decades of effort, no one has found a better solution. The whole of public-key cryptography rests on this sort of gamble.

The pitfalls of implementation

The theory holds up; the details are the devil. Three classic mistakes:

• a p that is too small: below 1024 bits, the Logjam attack (2015) showed that a well-resourced attacker could pre-compute most of the work for a given p, then break each exchange quickly;
• a p shared across millions of servers, which makes this pre-computation worthwhile;
• a poorly chosen g, resulting in a subgroup that is too small and correspondingly reducing the possible values.

And the future

A sufficiently large quantum computer would solve the discrete logarithm problem in polynomial time, using Shor’s algorithm. The same threat looms over RSA. This is why post-quantum standards are currently being rolled out.