golang/go · critical

crypto/rsa: p * q != n

Error message

crypto/rsa: p * q != n

What it means

Thrown when p*q mod N is zero, i.e. the product of the two stored primes is not equal to N. The check computes pN*qN mod N and expects a non-zero result (which for correctly-formed keys equals p*q, and since p*q = N < N^2 the residue is N itself, non-zero). A zero result proves N != p*q, so the modulus does not match its factors.

Source

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

	p := priv.p
	q := priv.q

	// FIPS 186-5, Section 5.1 requires "that p and q be of the same bit length."
	if p.BitLen() != q.BitLen() {
		priv.fipsApproved = false
	}

	// Check that pq ≡ 1 mod N (and that p < N and q < N).
	pN := bigmod.NewNat().ExpandFor(N)
	if _, err := pN.SetBytes(p.Nat().Bytes(p), N); err != nil {
		return errors.New("crypto/rsa: invalid prime")
	}
	qN := bigmod.NewNat().ExpandFor(N)
	if _, err := qN.SetBytes(q.Nat().Bytes(q), N); err != nil {
		return errors.New("crypto/rsa: invalid prime")
	}
	if pN.Mul(qN, N).IsZero() != 1 {
		return errors.New("crypto/rsa: p * q != n")
	}

	// Check that de ≡ 1 mod p-1, and de ≡ 1 mod q-1.
	//
	// This implies that e is coprime to each p-1 as e has a multiplicative
	// inverse. Therefore e is coprime to lcm(p-1,q-1) = λ(N).
	// It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1 mod p. Thus a^de ≡ a
	// mod n for all a coprime to n, as required.
	//
	// This checks dP, dQ, and e.
	pMinus1, err := bigmod.NewModulus(p.Nat().SubOne(p).Bytes(p))
	if err != nil {
		return errors.New("crypto/rsa: invalid prime")
	}
	dP, err := bigmod.NewNat().SetBytes(priv.dP, pMinus1)
	if err != nil {
		return errors.New("crypto/rsa: invalid CRT exponent")
	}

View on GitHub (pinned to b6b368adc5)

Solutions

1. Recompute N = p*q from the true primes and replace the stored N, or re-import the key wholesale.
2. Regenerate the key pair from scratch with rsa.GenerateKey.
3. Verify the key's integrity against its original source (HSM, keystore, PEM).

Example fix

// before
// N loaded separately from p, q and they disagree

// after
expectedN := new(big.Int).Mul(p, q)
if expectedN.Cmp(n) != 0 {
    return errors.New("N does not equal p*q")
}

expected := new(big.Int).Mul(p, q)
if expected.Cmp(n) != 0 {
    return errors.New("N must equal p*q")
}

func modulusMatchesFactors(n, p, q *big.Int) bool {
    return new(big.Int).Mul(p, q).Cmp(n) == 0
}

err := validateKey(priv)
if err != nil && strings.Contains(err.Error(), "p * q != n") {
    // recompute N or regenerate; key is inconsistent
    return err
}

When it happens

Trigger: Private-key consistency check where p and q are both < N (passed earlier guards) but their product is not N. Reached during GenerateKey self-check or explicit key validation.

Common situations: N was recomputed/edited independently of p,q. A key was assembled from mismatched p,q and N taken from different keys. Bit-flip corruption in N.

Related errors

• crypto/rsa: invalid prime
• crypto/rsa: invalid CRT exponent
• crypto/rsa: invalid CRT coefficient
• crypto/rsa: d does not match dP
• crypto/rsa: d does not match dQ

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