What is a safe prime, and why is it important for Diffie-Hellman parameter selection?

A safe prime $p$ is a prime where $\frac{p-1}{2}$ is also prime. Safe primes guarantee that $\mathbb{Z}_p^*$ has a large prime-order subgroup of order $\frac{p-1}{2}$, which is ideal for DH security.

* With p - 1 = 2q and q prime, the group order has only factors 2 and q — nothing for Pohlig-Hellman. *

A safe prime is attractive because it hands you the best possible subgroup for free. Since $p-1 = 2q$ with $q$ prime, the group order has no small factors for Pohlig–Hellman to exploit (bar the trivial 2), and you never have to go hunting for a large prime factor of $p-1$ — it is guaranteed to be exactly half of it. That removes the main pitfall of choosing DH parameters by hand.

Definition: A prime $p$ is a safe prime if $q = \frac{p-1}{2}$ is also prime.

Examples:

• $p = 23$: $\frac{23-1}{2} = 11$ → 11 is prime ✓ → 23 is a safe prime
• $p = 47$: $\frac{47-1}{2} = 23$ → 23 is prime ✓ → 47 is a safe prime
• $p = 19$: $\frac{19-1}{2} = 9$ → 9 is NOT prime ✗ → 19 is NOT a safe prime

Why safe primes matter for DH:

• $\mathbb{Z}_p^*$ has order $p - 1 = 2q$ (only two prime factors: 2 and $q$)
• The subgroup of order $q$ has the longest possible cycle relative to the prime's bit count
• Pohlig-Hellman attack has no small factors to exploit (except the trivial factor 2)
• No need to search for a suitable large prime factor of $p-1$ — it's automatically half of $p-1$

Discrete logarithm records (mod prime):

For comparison, ECC discrete log records: Only 114 bits (2020) — far behind DH, confirming ECC's strength with smaller keys.

Go deeper:

• Safe and Sophie Germain primes — Wikipedia — the number theory behind safe-prime DH groups.