Why does Diffie-Hellman need to use subgroups with prime order, even though $\mathbb{Z}_p^*$ is always cyclic for prime p?

$\mathbb{Z}_p^*$ has order $p - 1$, which is always even (since $p > 2$) and therefore never prime. For maximum security, DH needs a subgroup whose order is a large prime — to prevent small-subgroup attacks.

The problem:

• For DH, we work in $\mathbb{Z}_p^* = \{1, ..., p-1\}$ under multiplication mod $p$
• Group order = $p - 1$ (always even, so NOT prime)
• If the order has small factors, an attacker can use the Pohlig-Hellman algorithm to break DH into easier sub-problems

The solution: Find a large prime $q$ that divides $p - 1$, then use an element of order $q$ as the generator. This creates a prime-order subgroup.

Example: $\mathbb{Z}_{47}^*$ has order 46. Since $46 = 2 \times 23$, there's a subgroup of prime order 23. Use a generator of that subgroup for DH.

Real-world NIST parameters:

The DL group size (3000 bits) defines the prime $p$, while the DL key size (250 bits) defines the subgroup order $q$.

For ECC: Groups can actually have prime order directly, which is one reason ECC is considered more elegant — no subgroup selection needed.

Go deeper:

• Diffie-Hellman key exchange (Wikipedia) — the protocol and its safe-prime parameter choices.