What are the three categories of attacks on RSA, and which is not about breaking the math?

Question

Accepted Answer

Protocol attacks (misuse), mathematical attacks (factoring n), and side-channel attacks (leak the key from the hardware). Side-channel attacks don't touch the math at all.
1. Protocol-level attacks — exploit how RSA is used, not the algorithm itself.

Textbook RSA (no padding) is malleable: c · k^e mod n decrypts to m·k. Always use OAEP padding for encryption, PSS for signatures.
Small public exponent + no padding: if Alice sends the same m to 3 recipients using e=3, you can recover m via the Chinese Remainder Theorem (Håstad's attack).
Reusing the same modulus across users (common modulus attack).

2. Mathematical attacks — factor n directly.

General Number Field Sieve (GNFS) is the best-known classical algorithm. The current factoring record is RSA-250 (~829-bit number), factored in 2020.
For each new factoring record, the recommended RSA key size goes up. 1024-bit RSA is considered broken for governments; 2048 is being phased out; 3072+ is current best practice.
Quantum: Shor's algorithm factors any size n in polynomial time on a sufficiently large fault-tolerant quantum computer. Such a computer doesn't yet exist, but post-quantum crypto is being deployed pre-emptively.

3. Side-channel attacks — read the key from physical leakage during decryption.

Power analysis (SPA/DPA) on smart cards: the squaring-vs-multiplying pattern of the exponentiation leaks bits of d. Defense: constant-time exponentiation + blinding.
Timing attacks on networked TLS servers (Kocher 1996): the time to decrypt depends on d, leaking bits over many requests.
Fault injection (e.g. glitching the CPU's voltage): the Bellcore attack uses a single faulty CRT computation to factor n.
Acoustic (Genkin, Shamir, Tromer 2014): extract 4096-bit RSA key from a laptop's coil whine, from across the room, in under an hour.

Tip: "The math is unbroken" ≠ "RSA is safe to deploy." Most real-world RSA failures are protocol or side-channel issues, not factoring. Use a well-vetted library (OpenSSL, libsodium), use OAEP/PSS, never roll your own.