{"record":{"id":"4cd482280330bb34","repo":"golang/go","slug":"crypto-rsa-p-q-too-small","errorCode":null,"errorMessage":"crypto/rsa: |p - q| too small","messagePattern":"crypto/rsa: \\|p - q\\| too small","errorType":"validation","errorClass":null,"httpStatus":null,"severity":"critical","filePath":"src/crypto/internal/fips140/rsa/rsa.go","lineNumber":310,"sourceCode":"\t// https://eprint.iacr.org/2023/026.pdf.\n\tdiff := bigmod.NewNat()\n\tif qP, err := bigmod.NewNat().SetBytes(q.Nat().Bytes(q), p); err != nil {\n\t\t// q > p\n\t\tpQ, err := bigmod.NewNat().SetBytes(p.Nat().Bytes(p), q)\n\t\tif err != nil {\n\t\t\treturn errors.New(\"crypto/rsa: p == q\")\n\t\t}\n\t\t// diff = 0 - p mod q = q - p\n\t\tdiff.ExpandFor(q).Sub(pQ, q)\n\t} else {\n\t\t// p > q\n\t\t// diff = 0 - q mod p = p - q\n\t\tdiff.ExpandFor(p).Sub(qP, p)\n\t}\n\t// A tiny bit of leakage is acceptable because it's not adaptive, an\n\t// attacker only learns the magnitude of p - q.\n\tif diff.BitLenVarTime() <= N.BitLen()/2-100 {\n\t\treturn errors.New(\"crypto/rsa: |p - q| too small\")\n\t}\n\n\t// Check that d > 2^(nlen/2).\n\t//\n\t// See section 3 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf\n\t// for more details about attacks on small d values.\n\t//\n\t// Likewise, the leakage of the magnitude of d is not adaptive.\n\tif priv.d.BitLenVarTime() <= N.BitLen()/2 {\n\t\treturn errors.New(\"crypto/rsa: d too small\")\n\t}\n\n\treturn nil\n}\n\nfunc checkPublicKey(pub *PublicKey) (fipsApproved bool, err error) {\n\tfipsApproved = true\n\tif pub.N == nil {","sourceCodeStart":292,"sourceCodeEnd":328,"githubUrl":"https://github.com/golang/go/blob/b6b368adc57c96c3151d224d172029f233ead2c3/src/crypto/internal/fips140/rsa/rsa.go#L292-L328","documentation":"Thrown when |p - q| is too small in bit length (<= N.BitLen()/2 - 100), making N vulnerable to Fermat factorization. When p and q are close, N = p*q can be factored in polynomial time by searching near sqrt(N); this check rejects such weak keys proactively. The bit-length comparison leaks only magnitude, which is non-adaptive and acceptable.","triggerScenarios":"Key validation computes diff = |p - q| and finds diff.BitLenVarTime() <= N.BitLen()/2 - 100. Reached for generated or imported keys that pass all prior checks.","commonSituations":"A non-conformant or custom key generator that picks q near p. Keys from a broken/old RNG with low entropy. Imported keys from a library that does not enforce prime separation.","solutions":["Regenerate the key with rsa.GenerateKey, which enforces the separation bound.","If importing, reject keys failing this bound and request a fresh key from the origin.","For custom generators, re-draw q when |p - q| <= 2^(nlen/2 - 100)."],"exampleFix":"// before\n// custom generator returns q close to p\n\n// after\n// use the standard generator which enforces the separation\nkey, err := rsa.GenerateKey(rand.Reader, 2048)","handlingStrategy":"validation","validationCode":"diff := new(big.Int).Abs(new(big.Int).Sub(p, q))\nif diff.BitLen() <= n.BitLen()/2-100 {\n    return errors.New(\"|p-q| too small; vulnerable to Fermat factorization\")\n}","typeGuard":"func primeSeparationOK(p, q, n *big.Int) bool {\n    diff := new(big.Int).Abs(new(big.Int).Sub(p, q))\n    return diff.BitLen() > n.BitLen()/2-100\n}","tryCatchPattern":"err := validateKey(priv)\nif err != nil && strings.Contains(err.Error(), \"|p - q| too small\") {\n    return err // regenerate; key is factorable\n}","preventionTips":["Prefer rsa.GenerateKey, which enforces the separation bound.","For custom generators, redraw q when it is too close to p.","Reject imported keys failing the bound and request a replacement."],"tags":["crypto","rsa","key-validation","security","go"],"backgroundTag":null,"analyzedSha":"b6b368adc57c96c3151d224d172029f233ead2c3","analyzedAt":"2026-08-12T00:22:02.250Z","schemaVersion":2},"datasetVersion":"2026-08-12T12:31:55.035Z"}