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.

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)

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: invalid prime
• crypto/rsa: p * q != n
• crypto/rsa: invalid CRT exponent
• crypto/rsa: invalid CRT coefficient
• crypto/rsa: d does not match dP

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