{"record":{"id":"b7466913edf6aa8f","repo":"TheAlgorithms/Rust","slug":"failed-to-compute-modular-inverse","errorCode":null,"errorMessage":"Failed to compute modular inverse","messagePattern":"Failed to compute modular inverse","errorType":"panic","errorClass":null,"httpStatus":null,"severity":"error","filePath":"src/ciphers/rsa_cipher.rs","lineNumber":162,"sourceCode":"///\n/// # Panics\n///\n/// Panics if the modular inverse cannot be computed\npub fn generate_keypair(p: u64, q: u64) -> (PublicKey, PrivateKey) {\n    let n = p * q;\n    let phi = (p - 1) * (q - 1);\n\n    // Choose e such that 1 < e < phi and gcd(e, phi) = 1\n    let mut e = 2;\n    while e < phi {\n        if gcd(e, phi) == 1 {\n            break;\n        }\n        e += 1;\n    }\n\n    // Compute d, the modular multiplicative inverse of e mod phi\n    let d = mod_inverse(e as i64, phi as i64).expect(\"Failed to compute modular inverse\");\n\n    let public_key = PublicKey { n, e };\n    let private_key = PrivateKey { n, d };\n\n    (public_key, private_key)\n}\n\n/// Encrypts a message using the RSA public key\n///\n/// # Arguments\n///\n/// * `message` - The plaintext message (must be less than n)\n/// * `public_key` - The public key to use for encryption\n///\n/// # Returns\n///\n/// The encrypted ciphertext\n///","sourceCodeStart":144,"sourceCodeEnd":180,"githubUrl":"https://github.com/TheAlgorithms/Rust/blob/2c53ddfa4b43da4df34bc2f990c5e806f455cb90/src/ciphers/rsa_cipher.rs#L144-L180","documentation":"generate_keypair(p, q) panics with this .expect() message when mod_inverse(e, phi) returns None (src/ciphers/rsa_cipher.rs:162). The e-selection loop looks for e in [2, phi) with gcd(e, phi) == 1; if none exists the loop exits with e == phi, whose inverse mod phi cannot exist (gcd(phi, phi) = phi > 1), mod_inverse signals None, and expect aborts. In practice this means (p-1)*(q-1) came out as 0 or 2 — e.g. one 'prime' is 1, or the pair is (2,3)/(3,2) — or phi overflowed u64 for huge primes, which also breaks the `phi as i64` cast inside mod_inverse.","triggerScenarios":"generate_keypair(2, 3) or generate_keypair(3, 2): phi = 2, the loop body never runs (2 < 2 is false), e stays 2, gcd(2,2) = 2 → None → panic. generate_keypair(1, q) or any argument equal to 1: phi = 0, mod_inverse(2, 0) sees old_r = 2 > 1 → None → panic. Primes so large that (p-1)*(q-1) wraps u64 (each above ~3.03e9 = sqrt(2^63)): the wrapped phi makes the signed cast in mod_inverse negative-valued and the keypair silently breaks or panics.","commonSituations":"Following RSA walkthroughs with toy primes and picking the smallest ones (2 and 3); degenerate or fuzzed test inputs where a 'prime' is 1; user- or config-supplied primes without validation; porting examples that used 61/53 to randomly generated big primes that overflow the u64 arithmetic; expecting a Result and getting a process-aborting panic instead.","solutions":["Call generate_keypair with two distinct odd primes of reasonable size, e.g. generate_keypair(61, 53) as in the module docs — phi = 3120, e = 7 is found, d = 1783, no panic.","Validate primes before calling: reject 1, non-primes, and p == q; require phi = (p-1)*(q-1) >= 3 so an e below phi exists.","Keep each prime below ~3.03e9 so (p-1)*(q-1) and p*q fit in u64 and phi survives the `as i64` cast in mod_inverse; use checked_mul when computing them.","If you maintain the code, replace .expect with a Result carrying p, q, and phi, and make the e-search loop assert it found e < phi instead of silently exiting at e == phi.","For anything real, switch to a maintained crate (rsa, ring) — this module is explicitly educational."],"exampleFix":"// before\nlet (public_key, private_key) = generate_keypair(2, 3);\n// phi = (2-1)*(3-1) = 2 → no e in [2, 2) is coprime to phi → panic:\n// 'Failed to compute modular inverse'\n\n// after\nlet (public_key, private_key) = generate_keypair(61, 53);\n// phi = 3120, e = 7, d = 1783 — keypair builds fine","handlingStrategy":"validation","validationCode":"fn is_prime(n: u64) -> bool {\n    if n < 2 {\n        return false;\n    }\n    let mut i = 2u64;\n    while i.saturating_mul(i) <= n {\n        if n % i == 0 {\n            return false;\n        }\n        i += 1;\n    }\n    true\n}\n\nfn valid_rsa_primes(p: u64, q: u64) -> bool {\n    if p == q || !is_prime(p) || !is_prime(q) {\n        return false;\n    }\n    // phi must be >= 3 (an e below phi exists) and fit i64; n must not wrap\n    matches!((p - 1).checked_mul(q - 1), Some(phi) if phi >= 3 && phi < (1u64 << 63))\n        && p.checked_mul(q).is_some()\n}\n\nif valid_rsa_primes(p, q) {\n    let keys = generate_keypair(p, q); // cannot hit the expect()\n}","typeGuard":null,"tryCatchPattern":"// generate_keypair panics rather than returning Err; if inputs are untrusted,\n// isolate the panic (validation above is the real fix):\nlet keys = match std::panic::catch_unwind(|| generate_keypair(p, q)) {\n    Ok(keys) => keys,\n    Err(_) => {\n        // p/q unusable (phi = 0 or 2, or overflow): log and pick new primes\n        generate_keypair(61, 53)\n    }\n};","preventionTips":["Never pass 1, the pair (2,3)/(3,2), or equal primes; use distinct odd primes such as 61 and 53.","Compute (p-1)*(q-1) and p*q with checked_mul before generating keys.","Keep each prime below ~3e9 so phi fits the i64 cast inside mod_inverse.","Treat any panic from this module as invalid input, and use a maintained RSA crate for production work."],"tags":["rust","rsa","cryptography","panic","key-generation","modular-arithmetic"],"backgroundTag":"modular-inverse-does-not-exist","analyzedSha":"2c53ddfa4b43da4df34bc2f990c5e806f455cb90","analyzedAt":"2026-08-16T21:59:20.899Z","schemaVersion":2},"datasetVersion":"2026-08-16T23:17:17.608Z"}