Diffie–Hellman and the Discrete Logarithm: Why Prime-Order Subgroups

The one-sentence version

Two strangers on a public channel each pick a secret exponent $a, b$ , exchange $g^a$ and $g^b$ , and can then compute a shared key $g^{ab}$ only they know. To compute it, an eavesdropper essentially has to solve the discrete logarithm: find $a$ from $g^a$ . But if the group's order has only small prime factors, the Pohlig–Hellman algorithm uses the Chinese Remainder Theorem to split the problem into many small ones and solve them one by one. So the work must happen in a subgroup of large prime order.

This article has three layers:

The intuition: mixing paint
Real-world use: TLS, Signal, VPNs and the Logjam attack
The mathematics: cyclic groups, discrete logarithms, Pohlig–Hellman, baby-step giant-step and worked examples

Layer 1: The Intuition

1.1 Mixing paint

Alice and Bob want to agree on a secret color in a room where everyone can listen in:

They publicly agree on a shared color: yellow;
Alice secretly picks red, Bob secretly picks blue;
Each mixes their secret color into yellow: Alice publishes "yellow + red" (orange), Bob publishes "yellow + blue" (green);
Alice takes the green and mixes in her red: yellow + blue + red; Bob takes the orange and mixes in his blue: yellow + red + blue;
They end up with the same brown.

An eavesdropper saw yellow, orange and green, but mixed paint can't be separated, so the brown stays out of reach.

Analogy	Mathematics
Shared color	The public group and generator $g$
Secret colors	Private keys $a$ , $b$
Mixing paint	Exponentiation $g^a$
Paint can't be separated	The discrete logarithm is hard
The shared brown	The shared key $g^{ab}$

1.2 The 1976 revolution

Before this, two people who wanted to communicate securely had to meet in advance to exchange keys (diplomatic couriers, codebooks). In their 1976 paper "New Directions in Cryptography", Diffie and Hellman first showed publicly that strangers can agree on a key over a public channel, out of nothing. This was the start of public-key cryptography, and it earned them the 2015 Turing Award. (Declassified files later showed that Malcolm Williamson at Britain's GCHQ had secretly discovered the same method a few years earlier.)

Layer 2: Real-World Use

HTTPS (TLS 1.3): every handshake uses ECDHE (DH on an elliptic curve) to generate temporary keys.
Forward secrecy: each session uses one-time values of $a, b$ , discarded afterwards. Even if the server's long-term private key leaks later, past conversations can't be decrypted. TLS 1.3 requires this.
The Signal protocol: an X3DH handshake plus the "double ratchet" performs fresh DH on nearly every message, constantly updating keys.
VPNs (IPsec, WireGuard) and SSH: all use DH or ECDH to negotiate session keys.

The Logjam attack (2015)

Two problems came together:

Many servers still supported 512-bit "export-grade" DH, left over from 1990s US export controls, and attackers could trick connections into downgrading to it;
Huge numbers of servers shared the same prime $p$ . In the number field sieve for discrete logarithms, the most expensive precomputation depends only on $p$ . After a week of precomputation on one 512-bit $p$ , breaking each connection takes just a minute or two.

The researchers also estimated that a nation-state could do the same precomputation for a few of the most common 1024-bit primes. After that, 1024-bit DH was retired, and the mainstream moved to 2048 bits or more, or to elliptic curves.

Man-in-the-middle attacks

Plain DH doesn't verify who the other party is. An attacker can run DH separately with Alice and with Bob, relaying and reading everything in between. So real protocols always add signatures or certificates (RSA, ECDSA, Ed25519) to confirm "the one I'm shaking hands with really is them".

Layer 3: The Mathematics

3.1 The protocol

Public parameters: a prime $p$ and an element $g$ of $\mathbb{Z}_p^\times$ .

Alice	Public channel	Bob
Pick secret $a$		Pick secret $b$
Compute $A = g^a$	$A \to$ $\leftarrow B$	Compute $B = g^b$
Compute $B^a = g^{ab}$		Compute $A^b = g^{ab}$

Correctness only needs the exponent law $(g^b)^a = (g^a)^b$ .

3.2 Why the discrete logarithm is hard

$\mathbb{Z}_p^\times$ is a cyclic group of order $p-1$ (a general theorem about the multiplicative group of a finite field). Taking a generator $g$ , the map

$\mathbb{Z}_{p-1} \to \mathbb{Z}_p^\times,\qquad x \mapsto g^x$

is a group isomorphism: addition on the left corresponds to multiplication on the right. The forward direction takes only $O(\log p)$ multiplications with fast exponentiation; the reverse direction is the discrete logarithm, with no known polynomial-time classical algorithm.

Algorithm	Applies to	Rough cost
Brute force	Any group	$O(n)$
Baby-step giant-step, Pollard rho	Any group ("generic algorithms")	$O(\sqrt{n})$
Pohlig–Hellman	Group order $n$ has small prime factors	$O(\sqrt{q})$ , where $q$ is the largest prime factor of $n$
Index calculus, number field sieve	$\mathbb{Z}_p^\times$ (exploiting integer factorization)	Subexponential

Elliptic curve groups have no useful notion of "factoring", so index-calculus methods don't apply, leaving only the $O(\sqrt{n})$ generic algorithms. This is why ECC keys can be so much shorter.

3.3 Pohlig–Hellman: why prime order

Suppose the group order is $n = q_1 q_2 \cdots$ . To solve $g^x = h$ :

For each prime factor $q_i$ , raise both sides to the power $n/q_i$ : $(g^{n/q_i})^x = h^{n/q_i}$ . The base on the left has order only $q_i$ , so this is a small discrete logarithm of order $q_i$ ; solve it for $x \bmod q_i$ ;
Use the Chinese Remainder Theorem to combine all the $x \bmod q_i$ into $x \bmod n$ .

The cost is set by the largest prime factor. So if $p - 1$ is a product of many small primes, the discrete logarithm is easy. The countermeasure is to pick a safe prime $p = 2q + 1$ (with $q$ also prime) and work in the subgroup of order $q$ .

In the language of abstract algebra, this is a direct application of the isomorphism $\mathbb{Z}_n \cong \mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots$ (when the $q_i$ are pairwise coprime): a large cyclic group splits into a direct product of small cyclic groups, and the hard problem splits with it.

3.4 Worked examples

One DH handshake

$p = 23$ , $g = 5$ (a generator of $\mathbb{Z}_{23}^\times$ ).

Alice picks $a = 6$ : $A = 5^6 \bmod 23 = 8$
Bob picks $b = 15$ : $B = 5^{15} \bmod 23 = 19$
Alice computes $19^6 \bmod 23 = 2$ ; Bob computes $8^{15} \bmod 23 = 2$

The shared key is $2$ . (Checked with Python.)

Pohlig–Hellman recovers Alice's private key

The eavesdropper knows $g = 5$ and $A = 8$ , and wants to solve $5^x \equiv 8 \pmod{23}$ . The group order is $22 = 2 \times 11$ .

Find $x \bmod 2$ : raise both sides to the power $11$ . $5^{11} \equiv 22 \equiv -1$ and $8^{11} \equiv 1$ . So $(-1)^x = 1$ , $x$ is even, and $x \equiv 0 \pmod 2$ .

Find $x \bmod 11$ : raise both sides to the power $2$ . $5^2 = 25 \equiv 2$ and $8^2 = 64 \equiv 18$ . We need $2^y \equiv 18$ , trying only $11$ values: $2^6 = 64 \equiv 18$ , so $x \equiv 6 \pmod{11}$ .

Combine with the CRT: $x \equiv 0 \pmod 2$ and $x \equiv 6 \pmod{11}$ give $x = 6$ .

Instead of trying $22$ values, we tried only $2 + 11$ . At scale, the difference is exponential. (Checked with Python.)

3.5 Baby-step giant-step

Even with a large prime order $n$ , trading space for time gets you to $O(\sqrt{n})$ : let $m = \lceil \sqrt{n} \rceil$ and write $x = im + j$ .

Baby steps: store the table $g^0, g^1, \dots, g^{m-1}$ ;
Giant steps: compute $h \cdot g^{-m}, h \cdot g^{-2m}, \dots$ in turn, checking the table each time. On a hit, $h g^{-im} = g^j$ , which gives $x = im + j$ .

This is why a 256-bit group provides only 128-bit security: $\sqrt{2^{256}} = 2^{128}$ .

Summary

Layer	Key points
Intuition	Paint is easy to mix and hard to separate
Algebra	$x \mapsto g^x$ is a cyclic group isomorphism; its reverse is the discrete logarithm
Security	Small prime factors of the order are split off by Pohlig–Hellman + CRT; generic algorithms also achieve $\sqrt{n}$
Engineering	Use safe primes or elliptic curves; add signatures against man-in-the-middle attacks; ephemeral keys provide forward secrecy