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, b \in \mathbb{Z}/p\mathbb{Z} \wedge P$ a prime, compute $\log_b a$

In other words, $b$ is defined to be a primitive root of the finite group $( \mathbb{Z}/p\mathbb{Z} ) ^ {*}, a \in ( \mathbb{Z}/p\mathbb{Z} ) ^ {*}$ of order $p$ and we need to calculate the exponential $n$ such as $0< n<=p-1$ resolving $a=b^{n}$.

The logarithm is then calculated modulo the order of $b$ in the finite group such that $\log_b a \equiv x$ if $n = \left | b \right |$.

Because the discrete logarithm is not NP-complete, it is not possible to compute our $\log_ba$ 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 $p$ and a generator $g$ such as there exist an exponent $x$ so that $0 < g ^{x} \mod {p} <= p - 1$.

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

The public key equation is:  $g ^{k} \mod {p}$, let’s call it $l$

After both users compute  $l$ ( $l_1$ for User1 and  $l_2$ 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: $l ^{k} \mod{p}$

1. User1: $l_2 ^{k_1} \mod{p} \Rightarrow g ^{k_2*k_1} \mod{p}$
2. User2: $g ^{k_1*k_2} \mod{p}$

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  $k_1$ and  $k_2$ from  $l_1$ and $l_2$, since it is not possible to directly compute $g ^{k_1*k_2} \mod{p}$; after all $g ^{k_1} * g ^{k_2} = g ^{k_1+k_2}$ and not $g ^{k_1*k_2} \mod{p}$.

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.