RSA Fundamentals — the routing hub: which artifact points to which attack

RSA encrypts via c = m^e mod n with public modulus n = p*q and exponent e; decryption uses the private exponent d = e^-1 mod φ(n), where φ(n) = (p-1)(q-1)ᵃ. Recovering any of p, q, d, or φ(n) breaks the scheme — every named RSA attack is really just a different shortcut to one of those four values. This page is not an attack itself: it's the triage hub that reads the challenge's artifacts and routes to the right sub-attack, so start here whenever the challenge only hands you n, e, c (and maybe a hint) with no obvious weakness yet labeled.

The signal that betrays it

The generic RSA signal is just n, e, c (and sometimes a partial leak of p, q, or d) exposed by the challenge. What decides *which* attack applies is a specific artifact sitting in that tuple — look for these, in roughly the order they're cheapest to check:

- `e` is tiny (3, 5, 7 — anything in single digits) → candidate for a small-exponent family attack. - `e` is huge, close to n in size → usually signals the private exponent d is small instead (the two are inversely related in cost to brute-force), which is the Wiener/Boneh-Durfee family. - Multiple ciphertexts or moduli for what looks like the same underlying secret → either the same n reused with different e, or the same e reused across different n. Which one it is changes the whole attack. - `n` itself looks factorable or "special" — small bit length, a comment/flavor-text hint about how the primes were generated, or a modulus that fails a naive gcd sanity check → factoring branch. - You're handed partial bits of `m`, `p`, `q`, or `d` — a truncated printout, a side-channel leak, a "here's the top half of p" hint → partial-information branch. - The server is a decryption/signing black box that leaks something indirect (parity of m, a padding-valid/invalid bit, an error message) rather than handing you c and static values → oracle branch, a different flavor entirely from the static-artifact branches above.

How to exploit — the triage

Read the artifact, then branch. This is the order that actually saves time in practice — check the cheap, obvious artifacts before reaching for anything requiring real computation:

1. `n` looks factorable. If n is small, reused, or otherwise structurally weak, don't reach for a named attack yet — go to Integer Factorization Methodology — which factoring attack to try, in what order, the decision tree that orders factoring sub-attacks (perfect-power check, lookup, trial division, Fermat for close primes, Pollard's rho/p-1, ECM) from free to expensive. If the flavor text or generator hints specifically at "close primes," you can skip straight to Fermat Factorization — recovering p, q when the RSA primes were chosen too close. 2. `e` is small and there are several recipients/ciphertexts of the same message. Same plaintext, same small e, *different* coprime moduli → Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring (CRT-combine, then integer root — no factoring needed). Only one ciphertext with a small e and a message small enough that m^e doesn't wrap around n → Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n (plain integer e-th root, with wraparound handling if it's close). 3. Same `n`, but two different, coprime exponents on the same message → Common Modulus Attack — same n, two coprime exponents on the same message (Bezout-combine the two ciphertexts, no factoring). Do not confuse this with Hastad above: common-modulus is the mirror case — one modulus, two exponents, versus Hastad's many moduli, one exponent. 4. Large `d`/`e` imbalance (huge e, implying d was chosen or ended up small) → Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions first, since it's cheap (continued-fraction expansion of e/n) and covers d < (1/3) * n^0.25. If Wiener's consistency check fails but you still suspect a small-ish d, escalate to Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292, the lattice extension that reaches up to d < n^0.292. 5. Partial `m`, `p`, `q`, or `d` known (a stereotyped message with only a short unknown chunk, or leaked high/low bits of a prime or the private exponent) → Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction, the general small-modular-root lattice tool. Where the leak is specifically bits of p/q/d rather than of the message, the case is also indexed separately as Partial Key Exposure — recovering RSA when part of p or d has leaked. 6. Decryption oracle leaking bits/parity rather than handing you a clean `(n,e,c)` to compute on → RSA LSB / Parity Oracle Attack — recover the plaintext one bit at a time from a decryption oracle (binary search via repeated doubling of the ciphertext). 7. The server signs or decrypts almost anything except one blocklisted value → this isn't a math weakness in RSA itself but a protocol one; see RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism (multiply the forbidden value by a known factor's e-th power before submitting, then divide the blinding factor back out of the result — RSA's multiplicative homomorphism makes the oracle answer the forbidden question without ever asking it directly). 8. You're asked to forge a signature rather than recover a plaintext → RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key, which also leans on the same multiplicative homomorphism, this time against a signing oracle with lax padding checks.

Once any factor p, q (or φ(n), or d directly) is recovered by whichever branch applies, finish here — deriving the rest is mechanical:

```python from sympy import mod_inverse

phi = (p - 1) * (q - 1) d = mod_inverse(e, phi) m = pow(c, d, n) ```

Reference: Rivest-Shamir-Adleman 1977, the original public-key cryptosystem publication.

What does NOT work

- Trying to brute-force or "solve for" `d` directly from `(n, e)` without recovering `p`, `q`, or `φ(n)` first. There is no shortcut here — every attack in this hub is a way of getting at p, q, φ(n), or d through a *specific* structural weakness (a small exponent, a shared modulus, a small d, a partial leak, an oracle). Absent one of those artifacts, RSA's hardness is exactly the classical factoring assumption, and there is no generic move. - Assuming `φ(n) = (p-1)(q-1)` is the only correct modulus for inverting `e`. It's the textbook definition and it's what the field-tested snippet above uses — but some real implementations reduce d mod the smaller Carmichael function λ(n) = lcm(p-1, q-1) instead. If a derived d doesn't decrypt cleanly, that's worth checking before assuming the wrong p, q were recovered — see Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies and Euler's Totient — the RSA key-math backbone, and why it's not the exponent you want to leak. - Reaching for a named "small exponent" or "small `d`" attack just because the numbers involved are unknown, without checking the actual gating condition. Small-exponent attacks need the *message* to stay small enough that m^e < n (no modular wraparound) or need multiple broadcasts to combine via CRT; Wiener/Boneh-Durfee need d to actually be small relative to n, not just "not given directly." Skipping the check wastes time chasing an attack that was never going to terminate. - Treating factoring as the default when nothing about `n` looks weak. A well-formed CTF modulus (large, balanced, ordinarily generated) that resists every branch of Integer Factorization Methodology — which factoring attack to try, in what order is itself a signal: the intended weakness is elsewhere in this hub (exponent size, a second ciphertext/modulus, a partial leak, an oracle) — re-triage against the artifact list above rather than letting a factoring attempt run indefinitely.

Related

Integer Factorization Methodology — which factoring attack to try, in what order Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring Common Modulus Attack — same n, two coprime exponents on the same message Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction Partial Key Exposure — recovering RSA when part of p or d has leaked RSA LSB / Parity Oracle Attack — recover the plaintext one bit at a time from a decryption oracle RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key Fermat Factorization — recovering p, q when the RSA primes were chosen too close Chinese Remainder Theorem — recombining residues across coprime moduli Euler's Totient — the RSA key-math backbone, and why it's not the exponent you want to leak Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies

--- ᵃ φ(n) = (p-1)(q-1) is Euler's totient of n; some real-world implementations instead reduce d modulo the (smaller) Carmichael function λ(n) = lcm(p-1, q-1), which is the tighter group exponent — see Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies.