RSA attacks

When it applies

RSA is used somewhere you can reach on an authorized target — a session token/cookie, a licence check, a custom API request signature, a JWT (RS256), or an exposed keypair — and you can read the public key (n, e) and a ciphertext/signature. Real systems get RSA wrong in a handful of repeatable ways; each has a direct recovery.

Why it works

RSA is only as strong as its parameters and padding. "Textbook" RSA (no OAEP/PSS) is malleable and deterministic, small or shared parameters are mathematically reversible, and a factorable modulus hands you the private key outright. You don't break RSA — you exploit the specific weakness in this key.

Method

1. Extract parameters. From a PEM: openssl rsa -pubin -in key.pem -text -noout (gives n, e). From a JWT: decode the header/key. Note e and the bit-length of n.
2. Match the weakness → attack:
   • Factorable n — look it up on factordb; small/known n factors instantly → derive d.
   • Close primes (p≈q) — Fermat factorisation recovers p,q in milliseconds.
   • Small e (e=3) + small message — plaintext may be < n^(1/e); take the integer cube root of c (no modular reduction happened). Also Håstad broadcast if the same msg is sent to several keys.
   • Shared prime across two keys — gcd(n1, n2) yields a common factor → both keys fall.
   • Common modulus (same n, two e with gcd 1 on the same message) — combine with Bézout.
   • Small private exponent d — Wiener's attack (continued fractions).
   • Textbook (no padding) — malleable: forge/blind via c' = c·r^e mod n; deterministic encryption enables chosen-ciphertext games.
3. Automate the triage with RsaCtfTool (rsactftool --publickey key.pem --uncipher c runs the above battery), then finish by hand once you know which weakness hit.
4. Recover and use — with p,q: d = e^-1 mod (p-1)(q-1), decrypt c, or re-sign to forge a token/signature.

Gotchas

• Proper padding (OAEP/PSS) with strong random primes ≈ unbreakable — don't burn time; the win is a misconfiguration, not the algorithm. Confirm it's textbook/weak first.
• e and d are inverses mod φ(n) — a wrong φ (using n instead of (p-1)(q-1)) gives a key that "looks" right but fails; verify by decrypting a known value.
• JWT RS256 → key confusion is a different bug (alg swap to HS256) — see web-auth-jwt; this skill is for weak RSA keys themselves.
• Endianness / block size when converting the integer back to bytes trips people up (long_to_bytes).

Verify success

Recovered plaintext that is meaningful (or a forged signature/token the target accepts), and — when you factored n — a private key that correctly decrypts a value you can check.

References

RsaCtfTool; factordb; Boneh "Twenty Years of Attacks on RSA"; Wiener's attack; pycryptodome. Related: web-auth-jwt, crypto-oracle-attacks.