Safe prime

As explained in Real-World Cryptography

A safe prime is a prime number p such that p = 2q + 1 for another prime number q.

A safe prime is a prime p shaped as p = 2q + 1, where q is also prime. In Diffie-Hellman, this structure limits the multiplicative group modulo p to two subgroups: one of size 2 and one of size q. section 5.4

Safe primes matter because they reduce the attack surface in Diffie-Hellman:

• The group order is p − 1 = 2q, so its subgroup orders can only be 2 or q. section 5.4
• Having few small subgroups prevents small subgroup attacks, where invalid public keys gradually leak bits of a private key. section 5.4
• When Diffie-Hellman is unavoidable, prefer standardized groups instead of relaxed protocols or custom groups. section 5.4

The −1 subgroup

An attacker can send −1, the generator of the subgroup of size 2, as a public key. The resulting shared secret is then −1 or 1, creating the small-subgroup behavior exploited by the attack. section 5.4

Figure 5.15 A small subgroup attack impacts DH groups that have many subgroups. By choosing generators of small subgroups as public keys, an attacker can leak bits of someone’s private key little by little.

Visualizes how malicious public keys from small subgroups can leak private-key bits during Diffie-Hellman. section 5.4

How Real-World Cryptography covers it

How deep it goes

Derives subgroup sizes from p − 1 = 2q and gives a −1 attack example, but stops short of implementation details.

Examples

Uses p = 2q + 1 symbolically and −1 or 1 as the resulting small-subgroup shared secret.

What it assumes

Assumes Diffie-Hellman key exchanges and introduces subgroup-order reasoning through Lagrange theorem.

What you can do after

Evaluate Diffie-Hellman group choices and recognize why standardized safe-prime groups resist small-subgroup attacks.

How it connects

Connects safe primes with Diffie-Hellman, multiplicative groups, Lagrange theorem, and small subgroup attacks.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

• small subgroup attackaddresses · A small subgroup attack sends public keys from small subgroups to expose information about a victim's private key through the resulting shared secrets.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.