golang/go · critical

crypto/rsa: invalid prime

Error message

crypto/rsa: invalid prime

What it means

Thrown by the private-key consistency check when p's byte representation cannot be set into a bigmod Nat sized for modulus N (pN.SetBytes fails). SetBytes rejects values >= the modulus, so this fires when p >= N. For a valid RSA key N = p*q with p,q > 1, p is always strictly less than N, so failure means the key's p and N are inconsistent.

Source

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

	if priv.dP == nil {
		// Legacy and deprecated multi-prime keys.
		priv.fipsApproved = false
		return nil
	}

	N := priv.pub.N
	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))

View on GitHub (pinned to b6b368adc5)

Solutions

1. Re-serialize and re-import the key using the standard crypto/x509 or encoding/asn1 parsers instead of manual field assignment.
2. Verify N == p*q with math/big before invoking the fips RSA path.
3. Compare against a known-good export of the same key to locate the field swap.

Example fix

// before
// manual field assignment from parsed ASN.1, p and N possibly swapped

// after
// use standard parser which assigns fields in defined order
key, err := x509.ParsePKCS1PrivateKey(pkcs1DER)

if p.Cmp(n) >= 0 {
    return errors.New("p must be less than N")
}

func primeFitsModulus(p, n *big.Int) bool { return p.Cmp(n) < 0 }

err := validateKey(priv)
if err != nil && strings.Contains(err.Error(), "invalid prime") {
    // re-import or regenerate; do not use the key
    return err
}

When it happens

Trigger: The key-validation routine runs (e.g. during rsa.GenerateKey sanity pass or explicit validation) and p.Nat().Bytes(p) is too large to fit modulus N. Indicates p >= N in the supplied key material.

Common situations: Swapped fields during key import (p loaded where N belongs). A copy/paste or endianness error in serialized key parsing. Tampered or randomly corrupted key bytes.

Related errors

• crypto/rsa: p * q != n
• 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/c86db1d9db11d04e. Report an issue: GitHub.