{"record":{"id":"1a2b1303eb436fdc","repo":"XTLS/Xray-core","slug":"failed-to-compute-mod-inverse","errorCode":null,"errorMessage":"failed to compute mod inverse","messagePattern":"failed to compute mod inverse","errorType":"exception","errorClass":null,"httpStatus":null,"severity":"error","filePath":"transport/internet/finalmask/xmc/derivation.go","lineNumber":89,"sourceCode":"\t\t\t\te := big.NewInt(65537)\n\t\t\t\tgcd := new(big.Int).GCD(nil, nil, qMinus1, e)\n\t\t\t\tif gcd.Cmp(big.NewInt(1)) == 0 {\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t\tq.Add(q, big.NewInt(2))\n\t\t}\n\t}\n\n\tn := new(big.Int).Mul(p, q)\n\tpMinus1 := new(big.Int).Sub(p, big.NewInt(1))\n\tqMinus1 := new(big.Int).Sub(q, big.NewInt(1))\n\ttotient := new(big.Int).Mul(pMinus1, qMinus1)\n\n\te := big.NewInt(65537)\n\td := new(big.Int).ModInverse(e, totient)\n\tif d == nil {\n\t\treturn nil, fmt.Errorf(\"failed to compute mod inverse\")\n\t}\n\n\tpriv := &rsa.PrivateKey{\n\t\tPublicKey: rsa.PublicKey{\n\t\t\tN: n,\n\t\t\tE: 65537,\n\t\t},\n\t\tD:      d,\n\t\tPrimes: []*big.Int{p, q},\n\t}\n\tpriv.Precompute()\n\n\treturn priv, nil\n}\n","sourceCodeStart":71,"sourceCodeEnd":104,"githubUrl":"https://github.com/XTLS/Xray-core/blob/7d214f8b094f75322fa3990f8aadad1c912f24f5/transport/internet/finalmask/xmc/derivation.go#L71-L104","documentation":"DeriveRSAKey could not compute d = e^-1 mod totient(p-1)(q-1) with e = 65537. ModInverse returns nil only when e and the totient are not coprime. Because derivePrime explicitly searches for primes p, q with gcd(p-1, 65537) == 1, this branch is a near-unreachable internal invariant failure: in practice it signals a logic regression in the prime-derivation code rather than a bad password.","triggerScenarios":"Calling DeriveRSAKey(password) after modifying derivePrime or the p != q adjustment loop so that the gcd(p-1, e) == 1 guarantee is lost; any password triggers it once the invariant is broken.","commonSituations":"Forks of the transport that change the exponent, prime search step (Add 2), or the q-dedup loop; unit tests that stub out the SHA-256 stream with degenerate seeds; essentially never seen on unmodified code.","solutions":["If you maintain a fork, re-add the gcd(p-1, 65537) == 1 check to every loop that advances a prime candidate (derivePrime and the p==q adjustment in DeriveRSAKey)","If using stock code, report it upstream with the exact binary/version: stock derivation cannot produce non-coprime primes","Do not retry with a different password; the failure is deterministic in the derivation logic, not the input"],"exampleFix":"// before\nq.Add(q, big.NewInt(2)) // step without gcd check\n\n// after\nq.Add(q, big.NewInt(2))\nqMinus1 := new(big.Int).Sub(q, big.NewInt(1))\nif new(big.Int).GCD(nil, nil, qMinus1, big.NewInt(65537)).Cmp(big.NewInt(1)) != 0 {\n    continue\n}","handlingStrategy":"try-catch","validationCode":null,"typeGuard":null,"tryCatchPattern":"key, err := xmc.DeriveRSAKey(password)\nif err != nil {\n    // deterministic derivation failure: do not retry, surface immediately\n    return nil, fmt.Errorf(\"rsa derivation broken: %w\", err)\n}","preventionTips":["Keep derivePrime and the q-dedup loop's gcd(p-1, 65537) == 1 checks intact in forks","Add a unit test deriving keys for several passwords to catch regressions early","Treat this error as a code defect, not an input problem"],"tags":["go","crypto","rsa","math","invariant"],"backgroundTag":null,"analyzedSha":"7d214f8b094f75322fa3990f8aadad1c912f24f5","analyzedAt":"2026-08-15T14:26:24.325Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}