golang/go · error

crypto/rsa: too few primes of given length to generate an RS

Error message

crypto/rsa: too few primes of given length to generate an RSA key

What it means

Returned by GenerateMultiPrimeKey when bits < 64 and the estimated count of available primes per prime-slot (pi) is not greater than nprimes. The function uses the prime-counting approximation pi ≈ primeLimit / (ln(primeLimit) - 1), then quarters and halves it for top-bit-form and termination safety; if even that adjusted pi is at most nprimes, there are not enough distinct primes to populate the key. This guard exists only for toy-sized multi-prime keys.

Source

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

	priv := new(PrivateKey)
	priv.E = 65537

	if nprimes < 2 {
		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	if bits < 64 {
		primeLimit := float64(uint64(1) << uint(bits/nprimes))
		// pi approximates the number of primes less than primeLimit
		pi := primeLimit / (math.Log(primeLimit) - 1)
		// Generated primes start with 11 (in binary) so we can only
		// use a quarter of them.
		pi /= 4
		// Use a factor of two to ensure that key generation terminates
		// in a reasonable amount of time.
		pi /= 2
		if pi <= float64(nprimes) {
			return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
		}
	}

	primes := make([]*big.Int, nprimes)

NextSetOfPrimes:
	for {
		todo := bits
		// crypto/rand should set the top two bits in each prime.
		// Thus each prime has the form
		//   p_i = 2^bitlen(p_i) × 0.11... (in base 2).
		// And the product is:
		//   P = 2^todo × α
		// where α is the product of nprimes numbers of the form 0.11...
		//
		// If α < 1/2 (which can happen for nprimes > 2), we need to
		// shift todo to compensate for lost bits: the mean value of 0.11...
		// is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2

View on GitHub (pinned to b6b368adc5)

Solutions

1. Increase bits to at least 64 — and realistically ≥1024 per prime for any non-test use.
2. Reduce nprimes back to 2 and use rsa.GenerateKey.
3. Bounds-check inputs: if bits < 64 || nprimes > bits/2 { return Err } before calling GenerateMultiPrimeKey.

Example fix

// before
priv, err := rsa.GenerateMultiPrimeKey(rand.Reader, 5, 32) // err: too few primes of given length

// after
priv, err := rsa.GenerateKey(rand.Reader, 2048)

if bits < 64 {
    return errors.New("RSA bits too small; require >= 64 (and >= 1024 for production)")
}
return rsa.GenerateMultiPrimeKey(rand.Reader, nprimes, bits)

When it happens

Trigger: Call rsa.GenerateMultiPrimeKey(rand.Reader, nprimes, 32) or any bits<64 with a moderate nprimes; fuzz tests that sweep bits down while keeping nprimes fixed.

Common situations: Property-based tests generating tiny RSA keys to exercise edge cases; downstream tooling that derives bits from a ratio (e.g. bits = 256 / nprimes) and lands below 64.

Related errors

• crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2
• crypto/rsa: use of keys with odd size is not allowed in FIPS
• crypto/rsa: multi-prime RSA is not allowed in FIPS 140-only
• crypto/rsa: invalid PSS salt length
• rsa: key too small

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