golang/go · critical

crypto/rsa: |p - q| too small

Error message

crypto/rsa: |p - q| too small

What it means

Thrown when |p - q| is too small in bit length (<= N.BitLen()/2 - 100), making N vulnerable to Fermat factorization. When p and q are close, N = p*q can be factored in polynomial time by searching near sqrt(N); this check rejects such weak keys proactively. The bit-length comparison leaks only magnitude, which is non-adaptive and acceptable.

Source

Thrown at src/crypto/internal/fips140/rsa/rsa.go:310

	// https://eprint.iacr.org/2023/026.pdf.
	diff := bigmod.NewNat()
	if qP, err := bigmod.NewNat().SetBytes(q.Nat().Bytes(q), p); err != nil {
		// q > p
		pQ, err := bigmod.NewNat().SetBytes(p.Nat().Bytes(p), q)
		if err != nil {
			return errors.New("crypto/rsa: p == q")
		}
		// diff = 0 - p mod q = q - p
		diff.ExpandFor(q).Sub(pQ, q)
	} else {
		// p > q
		// diff = 0 - q mod p = p - q
		diff.ExpandFor(p).Sub(qP, p)
	}
	// A tiny bit of leakage is acceptable because it's not adaptive, an
	// attacker only learns the magnitude of p - q.
	if diff.BitLenVarTime() <= N.BitLen()/2-100 {
		return errors.New("crypto/rsa: |p - q| too small")
	}

	// Check that d > 2^(nlen/2).
	//
	// See section 3 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
	// for more details about attacks on small d values.
	//
	// Likewise, the leakage of the magnitude of d is not adaptive.
	if priv.d.BitLenVarTime() <= N.BitLen()/2 {
		return errors.New("crypto/rsa: d too small")
	}

	return nil
}

func checkPublicKey(pub *PublicKey) (fipsApproved bool, err error) {
	fipsApproved = true
	if pub.N == nil {

View on GitHub (pinned to b6b368adc5)

Solutions

1. Regenerate the key with rsa.GenerateKey, which enforces the separation bound.
2. If importing, reject keys failing this bound and request a fresh key from the origin.
3. For custom generators, re-draw q when |p - q| <= 2^(nlen/2 - 100).

Example fix

// before
// custom generator returns q close to p

// after
// use the standard generator which enforces the separation
key, err := rsa.GenerateKey(rand.Reader, 2048)

diff := new(big.Int).Abs(new(big.Int).Sub(p, q))
if diff.BitLen() <= n.BitLen()/2-100 {
    return errors.New("|p-q| too small; vulnerable to Fermat factorization")
}

func primeSeparationOK(p, q, n *big.Int) bool {
    diff := new(big.Int).Abs(new(big.Int).Sub(p, q))
    return diff.BitLen() > n.BitLen()/2-100
}

err := validateKey(priv)
if err != nil && strings.Contains(err.Error(), "|p - q| too small") {
    return err // regenerate; key is factorable
}

When it happens

Trigger: Key validation computes diff = |p - q| and finds diff.BitLenVarTime() <= N.BitLen()/2 - 100. Reached for generated or imported keys that pass all prior checks.

Common situations: A non-conformant or custom key generator that picks q near p. Keys from a broken/old RNG with low entropy. Imported keys from a library that does not enforce prime separation.

Related errors

• crypto/rsa: d too small
• crypto/rsa: invalid prime
• crypto/rsa: p * q != n
• crypto/rsa: invalid CRT exponent
• crypto/rsa: invalid CRT coefficient

AI-assisted analysis of golang/go@b6b368adc5 (2026-08-12). Data as JSON: /api/errors/4cd482280330bb34. Report an issue: GitHub.