golang/go · error

crypto/rsa: prime factors are not relatively prime

Error message

crypto/rsa: prime factors are not relatively prime

What it means

Thrown when big.Int.ModInverse(priv.Primes[1], priv.Primes[0]) (Q mod P) returns nil, meaning P and Q are not coprime. A valid RSA key requires gcd(P,Q)==1 so that Qinv exists; non-coprime primes make CRT decryption ambiguous. This indicates an invalid or corrupted key.

Solutions

1. Regenerate the key with rsa.GenerateKey, which guarantees distinct random primes.
2. Call priv.Validate() to catch mathematical inconsistency (it checks the P*Q==N relationship).
3. If importing keys, verify P != Q and gcd(P,Q)==1 before trusting them.
4. Treat any key failing this check as untrusted and discard it.

Example fix

// before
priv.Primes = []*big.Int{p, p} // P == Q, not coprime
err := priv.Validate()

// after
priv, err := rsa.GenerateKey(rand.Reader, 2048) // distinct random primes
if err != nil { return err }

import "math/big"

func checkCoprimePQ(priv *rsa.PrivateKey) error {
    if len(priv.Primes) < 2 { return priv.Validate() }
    p, q := priv.Primes[0], priv.Primes[1]
    if new(big.Int).GCD(nil, nil, p, q).Cmp(big.NewInt(1)) != 0 {
        return errors.New("rsa: P and Q not coprime")
    }
    return priv.Validate()
}

When it happens

Trigger: Sign/Decrypt/Validate on a 2-prime key where P and Q share a common factor (e.g., P==Q, or P divides Q). Reached after the prime nil/<=1 guards pass.

Common situations: Key generated by a broken/non-conformant generator; P and Q accidentally set equal; adversarial key injection; a test key reused for both primes.

Related errors

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

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

Appendix: source

Thrown at src/crypto/rsa/rsa.go:660

	// Ensure the Mod and ModInverse calls below don't panic.
	for _, prime := range priv.Primes {
		if prime == nil {
			return precomputed, errors.New("crypto/rsa: prime factor is nil")
		}
		if prime.Cmp(bigOne) <= 0 {
			return precomputed, errors.New("crypto/rsa: prime factor is <= 1")
		}
	}

	precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
	precomputed.Dp.Mod(priv.D, precomputed.Dp)

	precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
	precomputed.Dq.Mod(priv.D, precomputed.Dq)

	precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
	if precomputed.Qinv == nil {
		return precomputed, errors.New("crypto/rsa: prime factors are not relatively prime")
	}

	r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
	precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
	for i := 2; i < len(priv.Primes); i++ {
		prime := priv.Primes[i]
		values := &precomputed.CRTValues[i-2]

		values.Exp = new(big.Int).Sub(prime, bigOne)
		values.Exp.Mod(priv.D, values.Exp)

		values.R = new(big.Int).Set(r)
		values.Coeff = new(big.Int).ModInverse(r, prime)
		if values.Coeff == nil {
			return precomputed, errors.New("crypto/rsa: prime factors are not relatively prime")
		}

		r.Mul(r, prime)

View on GitHub (pinned to b6b368adc5)