golang/go · critical

crypto/rsa: invalid CRT coefficient

Error message

crypto/rsa: invalid CRT coefficient

What it means

Thrown when qInv * q mod p != 1, i.e. qInv is not the modular inverse of q modulo p. qInv is the CRT coefficient used to recombine the p-side and q-side results; if it does not satisfy q*qInv ≡ 1 mod p, CRT decryption/signing would produce wrong outputs. The check computes qP = q mod p then tests qP.Mul(qInv, p).IsOne().

Source

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

	}
	dQ, err := bigmod.NewNat().SetBytes(priv.dQ, qMinus1)
	if err != nil {
		return errors.New("crypto/rsa: invalid CRT exponent")
	}
	de.SetUint(uint(priv.pub.E)).ExpandFor(qMinus1)
	de.Mul(dQ, qMinus1)
	if de.IsOne() != 1 {
		return errors.New("crypto/rsa: invalid CRT exponent")
	}

	// Check that qInv * q ≡ 1 mod p.
	qP, err := bigmod.NewNat().SetOverflowingBytes(q.Nat().Bytes(q), p)
	if err != nil {
		// q >= 2^⌈log2(p)⌉
		qP = bigmod.NewNat().Mod(q.Nat(), p)
	}
	if qP.Mul(priv.qInv, p).IsOne() != 1 {
		return errors.New("crypto/rsa: invalid CRT coefficient")
	}

	// Check d against dP and dQ, even though we never actually use d,
	// to make sure the key is consistent.
	dP1 := bigmod.NewNat().Mod(priv.d, pMinus1)
	if dP1.Equal(dP) != 1 {
		return errors.New("crypto/rsa: d does not match dP")
	}
	dQ1 := bigmod.NewNat().Mod(priv.d, qMinus1)
	if dQ1.Equal(dQ) != 1 {
		return errors.New("crypto/rsa: d does not match dQ")
	}

	// Check that |p - q| > 2^(nlen/2 - 100).
	//
	// If p and q are very close to each other, then N=pq can be trivially
	// factored using Fermat's factorization method. Broken RSA implementations
	// do generate such keys. See Hanno Böck, Fermat Factorization in the Wild,

View on GitHub (pinned to b6b368adc5)

Solutions

1. Recompute qInv = q^{-1} mod p (via q^(p-2) mod p for odd prime p) from consistent p and q.
2. Ensure p and q are in the same order used during qInv derivation.
3. Regenerate the key to guarantee a consistent CRT coefficient.

Example fix

// before
// qInv from a key where p and q were later swapped

// after
qInv := new(big.Int).ModInverse(q, p) // requires Go 1.20+ math/big

check := new(big.Int).Mul(q, qInv)
check.Mod(check, p)
if check.Cmp(big.NewInt(1)) != 0 {
    return errors.New("q*qInv != 1 mod p")
}

func qInvCorrect(qInv, q, p *big.Int) bool {
    return new(big.Int).Mod(new(big.Int).Mul(q, qInv), p).Cmp(big.NewInt(1)) == 0
}

err := validateKey(priv)
if err != nil && strings.Contains(err.Error(), "invalid CRT coefficient") {
    return err // recompute qInv = q^{-1} mod p
}

When it happens

Trigger: Key validation's CRT coefficient check fails: qP * qInv mod p is not 1. Reached after both CRT exponent checks passed.

Common situations: qInv computed against a different p (e.g. p and q swapped after qInv was derived). qInv byte-corrupted. Key assembled from mismatched sources.

Related errors

• crypto/rsa: invalid CRT exponent
• crypto/rsa: d does not match dP
• crypto/rsa: d does not match dQ
• crypto/rsa: p is even
• crypto/rsa: invalid prime

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