{"record":{"id":"9beb87f2a8647d2e","repo":"golang/go","slug":"crypto-rsa-too-few-primes-of-given-length-to-gene","errorCode":null,"errorMessage":"crypto/rsa: too few primes of given length to generate an RSA key","messagePattern":"crypto/rsa: too few primes of given length to generate an RSA key","errorType":"validation","errorClass":null,"httpStatus":null,"severity":"error","filePath":"src/crypto/rsa/rsa.go","lineNumber":463,"sourceCode":"\tpriv := new(PrivateKey)\n\tpriv.E = 65537\n\n\tif nprimes < 2 {\n\t\treturn nil, errors.New(\"crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2\")\n\t}\n\n\tif bits < 64 {\n\t\tprimeLimit := float64(uint64(1) << uint(bits/nprimes))\n\t\t// pi approximates the number of primes less than primeLimit\n\t\tpi := primeLimit / (math.Log(primeLimit) - 1)\n\t\t// Generated primes start with 11 (in binary) so we can only\n\t\t// use a quarter of them.\n\t\tpi /= 4\n\t\t// Use a factor of two to ensure that key generation terminates\n\t\t// in a reasonable amount of time.\n\t\tpi /= 2\n\t\tif pi <= float64(nprimes) {\n\t\t\treturn nil, errors.New(\"crypto/rsa: too few primes of given length to generate an RSA key\")\n\t\t}\n\t}\n\n\tprimes := make([]*big.Int, nprimes)\n\nNextSetOfPrimes:\n\tfor {\n\t\ttodo := bits\n\t\t// crypto/rand should set the top two bits in each prime.\n\t\t// Thus each prime has the form\n\t\t//   p_i = 2^bitlen(p_i) × 0.11... (in base 2).\n\t\t// And the product is:\n\t\t//   P = 2^todo × α\n\t\t// where α is the product of nprimes numbers of the form 0.11...\n\t\t//\n\t\t// If α < 1/2 (which can happen for nprimes > 2), we need to\n\t\t// shift todo to compensate for lost bits: the mean value of 0.11...\n\t\t// is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2","sourceCodeStart":445,"sourceCodeEnd":481,"githubUrl":"https://github.com/golang/go/blob/b6b368adc57c96c3151d224d172029f233ead2c3/src/crypto/rsa/rsa.go#L445-L481","documentation":"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.","triggerScenarios":"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.","commonSituations":"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.","solutions":["Increase bits to at least 64 — and realistically ≥1024 per prime for any non-test use.","Reduce nprimes back to 2 and use rsa.GenerateKey.","Bounds-check inputs: if bits < 64 || nprimes > bits/2 { return Err } before calling GenerateMultiPrimeKey."],"exampleFix":"// before\npriv, err := rsa.GenerateMultiPrimeKey(rand.Reader, 5, 32) // err: too few primes of given length\n\n// after\npriv, err := rsa.GenerateKey(rand.Reader, 2048)","handlingStrategy":"validation","validationCode":"if bits < 64 {\n    return errors.New(\"RSA bits too small; require >= 64 (and >= 1024 for production)\")\n}\nreturn rsa.GenerateMultiPrimeKey(rand.Reader, nprimes, bits)","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Reject bits < 1024 at the configuration boundary.","Use rsa.GenerateKey (2 primes) to dodge the multi-prime prime-count math entirely.","In tests, keep toy keys but bounds-check before calling GenerateMultiPrimeKey."],"tags":["rsa","multi-prime","key-generation","validation","crypto"],"analyzedSha":"b6b368adc57c96c3151d224d172029f233ead2c3","analyzedAt":"2026-08-12T00:22:02.250Z","schemaVersion":2},"datasetVersion":"2026-08-12T08:17:17.861Z"}