A safe prime is a prime number of the form 2q + 1, where q is also a prime.

A safe prime is a prime number of the form $p = 2q + 1$, where $q$ is also prime. In this case, the related prime $q$ is sometimes known as a Sophie Germain prime.

Safe primes are useful because the multiplicative group of integers modulo $p$, sometimes written $(\mathbb Z/p\mathbb Z)^\times$, has order $2q$, which is the closest to a prime-order group that can be achieved in modular integer arithmetic. Cryptosystems based on the difficulty of computing discrete logarithms, such as Diffie–Hellman or Schnorr signatures, are often designed under the assumption of a prime-order group, and require extra care when cast in composite-order groups.

Specifically, cryptosystems that allow an attacker to learn $g^x$ for attacker-controlled $g$ and secret $x$ may be vulnerable to Lim–Lee active small-subgroup attacks, which easily reveal $x \bmod n$ for each small factor $n$ of the group order. When the group is $(\mathbb Z/p\mathbb Z)^\times$ for a safe prime $p$, the attacker can only learn $x \bmod 2$ this way, since the only other factor is the large prime $q$.

Cryptosystems that do not expose an oracle giving $g \mapsto g^x$ for secret $x$ do not need to use safe primes, such as Diffie–Hellman with single-use key pairs only, Schnorr signatures, and DSA, and may be satisfied instead with Schnorr groups of the more general form $p = kq + 1$, where $q$ is also prime but may be much smaller than $(p - 1)/2$.

history | excerpt history