RSA Security and the Factoring Problem

The RSA problem is: given a modulus $n = pq$ (product of two large primes), a public exponent $e$, and a ciphertext $c = m^e \bmod n$, recover $m$ without knowing the factorization of $n$. The factoring assumption states that no probabilistic polynomial-time algorithm can, with non-negligible probability, recover $p$ and $q$ from $n$ alone, when $p$ and $q$ are randomly chosen primes of sufficient bit-length. RSA's private key $d$ satisfies $ed \equiv 1 \pmod{\varphi(n)}$, and computing $d$ from $(n, e)$ is provably as hard as factoring $n$ — so if factoring is hard, recovering the private key is hard. Crucially, the RSA problem (invert $m \mapsto m^e \bmod n$) is only believed to be as hard as factoring; no proof of equivalence in general is known, though for special cases (e.g. recovering $d$) the equivalence does hold. This distinction matters: an attacker does not need to factor $n$ to break RSA in practice. They only need to invert the specific ciphertext they intercepted, exploit algebraic structure in how RSA is used, or exploit implementation side channels. This is the source of the gap between "factoring is hard" and "RSA as I coded it is secure."

Textbook RSA denotes the bare operation $c = m^e \bmod n$ with no additional processing. It has three properties that make it unsuitable for direct use: it is deterministic (the same plaintext always produces the same ciphertext, leaking equality information), it is multiplicatively homomorphic ($(m_1 m_2)^e \equiv m_1^e m_2^e \pmod n$, letting an attacker manipulate ciphertexts algebraically), and for small messages or small exponents, $m^e$ may not even "wrap around" modulo $n$, making the modular reduction meaningless. Secure deployments instead use padding schemes — most notably OAEP (Optimal Asymmetric Encryption Padding) for encryption and PSS (Probabilistic Signature Scheme) for signatures — that inject randomness and structural checks before the modular exponentiation, breaking determinism and homomorphism while remaining provably secure under the RSA assumption in the random oracle model.

The factoring assumption, precisely

Given $n = pq$ with $p, q$ random $k$-bit primes, the assumption is that any algorithm $\mathcal{A}$ running in time polynomial in $k$ satisfies

The best known classical algorithm, the General Number Field Sieve (GNFS), factors an $n$-bit integer in expected time

which is subexponential — faster than exponential in $n$'s bit-length, but slower than any polynomial. This subexponential runtime is precisely why RSA key sizes must be large (2048–3072 bits today) and must grow over time as computing power increases, unlike symmetric ciphers whose key length scales linearly with security level.

Why textbook RSA fails: attack catalogue

The following is a step-by-step walk through the classic attacks, each exploiting a specific structural weakness rather than factoring $n$ directly.

1. Small public exponent, no padding (Coppersmith / cube-root attack). If $e = 3$ and the message $m$ is small enough that $m^3 < n$, then $c = m^3$ over the integers (no modular wraparound occurs), so the attacker simply computes an integer cube root.

2. Håstad's broadcast attack. If the same message $m$ is sent to $e=3$ recipients with distinct moduli $n_1, n_2, n_3$, an attacker who intercepts $c_1, c_2, c_3$ combines them via the Chinese Remainder Theorem to recover $m^3 \bmod (n_1 n_2 n_3)$, and since $m^3 < n_1n_2n_3$, an integer cube root recovers $m$ — again with no factoring involved.

3. Common modulus attack. If two parties share the same $n$ but use different exponents $e_1, e_2$ with $\gcd(e_1, e_2) = 1$, and the same message $m$ is encrypted under both, an attacker who has $c_1 = m^{e_1}, c_2 = m^{e_2}$ can use the extended Euclidean algorithm to find integers $a, b$ with $a e_1 + b e_2 = 1$, then compute

4. Related-message / Franklin-Reiter attack. If two messages are related by a known linear function ($m_2 = f(m_1)$) and encrypted under the same small exponent, polynomial GCD techniques recover both messages.

5. Bleichenbacher's padding-oracle attack (1998). This is the most consequential attack in practice. Even with padding (PKCS#1 v1.5), if the decryption oracle leaks whether a ciphertext's padding is well-formed (e.g., via a distinguishable error message or timing difference), an attacker can adaptively query millions of ciphertexts to narrow down the plaintext, eventually decrypting any target ciphertext without the private key. This underlies "ROBOT" and similar attacks against TLS servers even decades after the original discovery.

The fix: OAEP and PSS

OAEP (encryption) transforms message $m$ using two random oracles $G, H$ and a random seed $r$ before RSA is applied: ``` OAEP-Encode(m, k0, k1):

# m is the message, padded with k1 zero bits, total length n - k0 r <- random k0-bit string dbMask <- G(r) # G expands r to length (n - k0) maskedDB <- (m || 0^k1) XOR dbMask seedMask <- H(maskedDB) # H compresses to length k0 maskedSeed <- r XOR seedMask return maskedSeed || maskedDB # this is the OAEP-encoded message, then RSA-exponentiated ``` Decryption reverses the masks and checks that the trailing $k_1$ zero bits are present; if not, decryption fails without revealing which check failed (a well-implemented OAEP decryption returns a single generic error). The random seed $r$ ensures encryption is probabilistic (defeating the determinism weakness), and the two-round Feistel-like structure destroys the multiplicative homomorphism (defeating common-modulus and related-message attacks), because the ciphertext no longer corresponds to a simple algebraic function of $m$.

PSS (signatures) similarly randomizes signing: a random salt is hashed together with the message digest, embedded in a padded block, and only then RSA-exponentiated with the private key. This prevents existential forgery attacks that exploit RSA's multiplicative structure (e.g., an attacker computing a valid signature on $m_1 m_2$ from valid signatures on $m_1$ and $m_2$). ``` RSA-Encrypt-Secure(m, pk = (n, e)): EM <- OAEP-Encode(m) # randomized, structured encoding c <- EM^e mod n return c RSA-Decrypt-Secure(c, sk = (n, d)): EM <- c^d mod n m, valid <- OAEP-Decode(EM) if not valid: return GENERIC_ERROR # never distinguish error types or leak timing return m ``` The critical implementation discipline is that `OAEP-Decode` must run in constant time and must return exactly one error code regardless of which internal check failed — this is precisely what Bleichenbacher-style attacks exploit when violated.

Factoring runtime. The GNFS complexity, $L_n[1/3, 1.923]$, is neither polynomial nor exponential in the bit-length $\log n$; it lies strictly between the two, which is why key sizes for RSA (2048–4096 bits) are far larger than for comparable symmetric ciphers (128–256 bits) at the same security level. Trial division and Pollard's rho give exponential-time baselines; GNFS is the asymptotically best known classical algorithm and is what drove the deprecation of 512-bit and 1024-bit RSA.

Correctness of RSA decryption. The scheme's correctness (that decryption recovers the original plaintext) follows from Euler's theorem: since $ed \equiv 1 \pmod{\varphi(n)}$, write $ed = 1 + k\varphi(n)$; then for $m$ coprime to $n$,

For $m$ sharing a factor with $n$ (a negligible-probability event for random $m$ over a large modulus), correctness still holds via the Chinese Remainder Theorem applied separately mod $p$ and mod $q$. This is a correctness argument, entirely separate from security — the algebra guarantees the ciphertext decrypts to the right value, but says nothing about whether an eavesdropper can also recover $m$.

Security reduction (why we trust RSA-OAEP). OAEP's security proof shows that, in the random oracle model, if an adversary can break the semantic security (IND-CCA2) of RSA-OAEP, then that adversary can be used as a subroutine to invert the RSA trapdoor permutation itself. Symbolically: security of RSA-OAEP $\Rightarrow$ solving the RSA problem (invert $m \mapsto m^e \bmod n$) is easy $\Rightarrow$ (conjecturally) factoring $n$ is easy. The contrapositive gives the guarantee developers rely on: if factoring stays hard and $G, H$ behave like random oracles, RSA-OAEP resists chosen-ciphertext attacks — closing exactly the gap that Bleichenbacher's attack exploited in the unpadded/naively-padded case.

Tradeoffs to be honest about. The random oracle model is an idealization; real hash functions are not literally random oracles, so OAEP's proof is a heuristic guarantee, not an unconditional one. Padding also adds overhead: OAEP consumes bits for the seed and redundancy, shrinking the maximum plaintext size relative to raw RSA (roughly $n$'s bit-length minus $2k_0$ minus $k_1$ bits). And no amount of padding fixes RSA against a large-scale quantum computer, since Shor's algorithm factors $n$ in polynomial time on such hardware — a limitation that padding cannot address at all, motivating Post-Quantum Cryptography.

Consider the common modulus attack traced through concrete (small, illustrative) numbers. Let $p = 61$, $q = 53$, so $n = pq = 3233$ and $\varphi(n) = 60 \times 52 = 3120$. Suppose (insecurely) two different services share this modulus $n = 3233$ but use different public exponents:

• Service A: $e_1 = 17$
• Service B: $e_2 = 7$

Both are coprime to $\varphi(n) = 3120$ and to each other: $\gcd(17, 7) = 1$. A user sends the same message $m = 65$ to both services.

Let's redo the extended Euclidean step carefully since $\gcd(17,7)=1$ must be verified properly:

Back-substitute: $1 = 7 - 2\cdot 3 = 7 - 2(17 - 2\cdot7) = 5\cdot 7 - 2\cdot 17.$ So $a = -2$, $b = 5$, giving $17(-2) + 7(5) = -34 + 35 = 1$. ✓ Now the attacker, who intercepted $c_1 = 2790$ and $c_2 = 2668$ but knows neither private key, computes:

Since $a = -2$ is negative, the attacker first computes the modular inverse of $2790$ modulo $3233$, call it $2790^{-1} \bmod 3233$, then squares it, then multiplies by $2668^5 \bmod 3233$. Carrying this out (using modular exponentiation and the extended Euclidean algorithm for the inverse) yields:

recovering the plaintext without ever factoring $n$ and without knowing either private exponent $d_1$ or $d_2$ — purely from algebraic manipulation of two ciphertexts of the same message under coprime exponents sharing a modulus. This demonstrates precisely why "textbook RSA is insecure" is not a vague slogan: the attack above runs in time dominated by a handful of modular exponentiations and one Euclidean algorithm call, all polynomial-time operations, entirely bypassing the (hard) factoring problem.

RSA's story is inseparable from the broader arc of public-key cryptography inaugurated by Whitfield Diffie and Martin Hellman's 1976 key-exchange paper, and it echoes Claude Shannon's earlier insight that a cryptosystem's strength must be measured against a well-defined adversarial model rather than intuition. The repeated pattern in RSA's history — a clean mathematical primitive, followed by a subtle protocol-level attack, followed by a provably secure padding fix — is a template that recurs throughout applied cryptography, and it foreshadows the current transition toward lattice-based schemes as factoring's classical hardness comes under threat from quantum algorithms.

RSA with OAEP and PSS padding underlies the TLS handshake used to secure HTTPS connections, code-signing systems that verify software authenticity (from operating system updates to mobile app stores), and secure email standards like S/MIME. Hardware security modules (HSMs) in banking infrastructure implement constant-time RSA operations specifically to prevent the timing side-channels discussed above. Certificate authorities issuing X.509 certificates rely on RSA-PSS or RSA-PKCS#1 signatures to bind public keys to identities, making correct padding a foundational trust anchor for the entire web PKI. Understanding textbook RSA's weaknesses is also a prerequisite for Key Management practice, since key reuse across protocols (a real-world instance of the common-modulus pattern) remains a recurring audit finding in production systems, and for grasping why Post-Quantum Cryptography migration is treated as urgent despite RSA's continued classical-security margin.

Ask the tutor: Can you walk through why OAEP's security proof breaks down if the random oracles G and H are replaced with a real hash function that has a subtle correlation?