Why must DH implementations use generators of prime-order subgroups rather than generators of the full group $\mathbb{Z}_p^*$?
If the group order has small prime factors, the Pohlig-Hellman algorithm can decompose the discrete log into easier sub-problems. Using a subgroup with large prime order $q$ prevents this attack.
* Small factors in the group order hand Pohlig-Hellman easy sub-problems; a prime-order subgroup removes them. *
The intuition is that a discrete log is only as hard as its hardest unavoidable step. Pohlig–Hellman splits the problem into one sub-problem per prime factor of the group order, so a group whose order is divisible by many small primes is soft — you solve a string of easy pieces and stitch them together. Forcing all the work into a single large prime-order subgroup leaves no cheap piece to peel off.
The vulnerability:
- $\mathbb{Z}_p^*$ has order $p - 1$ (always even, never prime)
- If $p - 1$ has small prime factors (e.g., $p - 1 = 2 \cdot 3 \cdot 5 \cdot ...$), the Pohlig-Hellman algorithm breaks the discrete log into sub-problems for each prime factor
- Each sub-problem is much easier than the full discrete log
The solution:
- Choose $p$ such that $p - 1$ has a large prime factor $q$ (at least 250 bits)
- Use $g$ as a generator of the subgroup of order $q$, not of the full group
- Since $q$ is prime, this subgroup has prime order → every non-identity element is a generator → Pohlig-Hellman cannot decompose the problem
Practical parameters (BSI 2023+):
- $p \approx 3072$ bits (the prime modulus)
- $q \approx 250$ bits (the prime subgroup order)
- $g$ = generator of the subgroup of order $q$
- Security equivalent to 128-bit symmetric key
Example: $\mathbb{Z}_{47}^*$ has order 46 = 2 × 23. The subgroup of order 23 (a prime) is the right choice. Use $g = 2$ (which has order 23 in $\mathbb{Z}_{47}^*$, not order 46).
Go deeper:
Pohlig-Hellman algorithm — Wikipedia — the attack a prime-order subgroup shuts down.