# RSA Is a Trapdoor, Not a Cryptosystem: OAEP, PSS, and the 25-Year Padding-Oracle Lineage

> Textbook RSA is a trapdoor, not a cryptosystem. A field guide to OAEP, PSS, PKCS#1 v1.5, and the Bleichenbacher-ROBOT-Marvin padding-oracle lineage, done right.

*Published: 2026-07-11*
*Canonical: https://paragmali.com/blog/rsa-is-a-trapdoor-not-a-cryptosystem-oaep-pss-and-the-25-yea*
*© Parag Mali. All rights reserved.*

---
<TLDR>
**RSA is a trapdoor permutation, not a cryptosystem** -- and almost every real-world RSA break came from treating the bare trapdoor as if it were already secure. Textbook RSA is deterministic and malleable. PKCS#1 v1.5 *encryption* turns "is this padding valid?" into a decryption oracle that leaked through ever-quieter channels for 25 years, from Bleichenbacher (1998) [@bleichenbacher98] through DROWN [@drown16] and ROBOT [@robot18] to Marvin's pure-timing attack (2023) [@marvin23]. "Done right" is a stack that must all hold at once: the right scheme (**OAEP** for encryption, **PSS** for new signatures), the right parameters (2048-bit floor, `e = 65537`, CSPRNG primes), and a **constant-time, fault-checked implementation** -- because security is a property of the scheme *and* its implementation, not of the math. And keep one split absolute: v1.5 *signatures* are unbroken and still dominant (verify strictly), while v1.5 *encryption* must be retired.
</TLDR>

## 1. The Modulus Was Never Factored

In 2018, three researchers signed a message with the private key behind `facebook.com`'s TLS certificate [@robot18]. They never factored Facebook's 2,048-bit modulus. Nobody has ever publicly factored a 2,048-bit modulus -- the public record stands at 829 bits, and that took roughly 2,700 core-years [@rsa250].

Instead, they asked one of Facebook's front-end servers the same yes-or-no question a few hundred thousand times -- *is this padding valid?* -- and let the pattern of answers spell out the secret [@robot18]. The attack they used was already nineteen years old [@robotsite]. Five years later, a Red Hat engineer reproduced the same break against software that was supposed to be immune, using nothing but a stopwatch, and called it Marvin [@marvin23].

Notice what did not happen. No prime was recovered. No number was factored. The RSA problem -- invert `c = m^e mod N` without the private key -- stood exactly as hard the day after as the day before. What broke was the server's *reaction*: the way it answered a question about a ciphertext it did not create.

That is the whole subject in one sentence. Textbook RSA -- the bare `m^e mod N` you meet in a first course -- is a **trapdoor permutation, not a cryptosystem**. It is a beautiful one-way function with a secret shortcut, and nothing more.

Everything that turns it into secure encryption or a secure signature lives *around* the permutation, in the padding, the parameters, and the code that runs the operation. Almost every famous RSA disaster of the last three decades is a variation on one theme: someone used the bare trapdoor as if it were already a cryptosystem, or let the machinery meant to secure it confess -- through an error message, a network timeout, a microsecond of timing, or an injected fault -- whether a check had passed.

<PullQuote>
The math was never broken. The padding check told the attacker whether it passed.
</PullQuote>

So here is the diagnostic question this article keeps asking, the one that unlocks the entire failure catalog: **when a ciphertext or signature it did not create arrives, what does the receiver reveal about it -- through its answer, its timing, or its faults -- before and after it has checked the padding?** Four names you may know as headlines -- Bleichenbacher, DROWN, ROBOT, Marvin -- are four answers to that question, each leaking the same single bit through a quieter channel than the last. To see why one yes-or-no question about padding is enough to reconstruct a session key, you first have to see what RSA actually *is*, and what it is not.

## 2. A Trapdoor for Diffie-Hellman's Challenge

In 1976, Whitfield Diffie and Martin Hellman wrote down the shape of a future that did not yet have an engine. Their paper *New Directions in Cryptography* described public-key encryption and, remarkably, the idea of a digital signature -- a value only you can produce but anyone can check [@dh76]. What they could not supply was a concrete *trapdoor*: a function easy to compute in one direction, hard to invert, yet effortless to invert if you hold a secret. Their paper is a challenge with a hole in it, and the hole is shaped exactly like RSA.

A year later, Ron Rivest, Adi Shamir, and Leonard Adleman filled it. Pick two large primes $p$ and $q$ and set $N = pq$. Choose a public exponent $e$, and compute a private exponent $d$ with $ed \equiv 1 \pmod{\lambda(N)}$. Publish $(N, e)$; keep $d$, $p$, and $q$ secret. To encrypt a message represented as a number $m < N$, raise it to the public exponent; to decrypt, raise the result to the private one [@rsa78]:

$$c = m^e \bmod N, \qquad m = c^d \bmod N.$$

Why does the second operation undo the first? Because of Euler's theorem (1763): for any $m$ coprime to $N$, $m^{\phi(N)} \equiv 1 \pmod N$, with the totient $\phi(N) = (p-1)(q-1)$. Its Carmichael-function refinement (Carmichael, 1910) gives the same identity for the smaller $\lambda(N) = \mathrm{lcm}(p-1, q-1)$. Since $ed \equiv 1 \pmod{\lambda(N)}$, we have $ed = 1 + k\lambda(N)$ for some integer $k$, so $c^d = m^{ed} = m \cdot (m^{\lambda(N)})^k \equiv m \pmod N$. The exponents cancel, and the plaintext falls out -- but only for someone who could compute $d$, and computing $d$ requires $\lambda(N)$, which requires the factors of $N$. That is the trapdoor: the factorization of $N$ is the secret that inverts the permutation.<Sidenote>The original 1978 paper used $\phi(N) = (p-1)(q-1)$, Euler's totient. Modern standards use the smaller Carmichael function $\lambda(N) = \mathrm{lcm}(p-1, q-1)$, which yields a smaller valid $d$ and the same correctness. Either works; $\lambda(N)$ is now the convention in FIPS 186-5.</Sidenote>

<Definition term="Trapdoor permutation">
A function that is easy to evaluate in the forward direction, computationally hard to invert without a secret, and easy to invert with it. RSA's forward map is x maps to x raised to the e, modulo N; the trapdoor that inverts it is the factorization of N. A trapdoor permutation is a primitive, not a complete encryption scheme -- it says nothing about hiding partial information or resisting tampering.
</Definition>

The elegance that made RSA famous is that the *same* operation both encrypts and signs. Swap the roles of the exponents: to sign a message, raise it to the private exponent, $s = m^d \bmod N$, an act only the key holder can perform; to verify, raise the signature to the public exponent and check that $s^e \equiv m \pmod N$, which anyone can do [@rsa78]. One modular exponentiation, read in two directions, is both a lock only you can open and a seal only you can stamp. Boneh's survey calls this duality the source of both RSA's reach and its long catalogue of misuse [@boneh99].

Two engineering choices from this era matter later, because each returns as an attack surface. The first is the public exponent. Almost every deployed RSA key uses $e = 65537$.<MarginNote>65537 is the Fermat prime $F_4 = 2^{16} + 1$. Written in binary it is `1` followed by fifteen `0`s and a final `1` -- a Hamming weight of just 2 -- so public-key operations cost only sixteen squarings and one multiplication. Small enough to be fast, large enough to dodge the low-exponent traps of $e = 3$.</MarginNote> The second is how the private operation is computed. Rather than one exponentiation modulo $N$, implementations work modulo $p$ and modulo $q$ separately and recombine, using the Chinese Remainder Theorem for roughly a fourfold speedup.

<Definition term="Chinese Remainder Theorem (CRT) in RSA">
A technique for computing the private operation c raised to the d, modulo N, by working separately modulo p and modulo q on half-size numbers and then recombining the two halves. It cuts the cost of decryption and signing by about four times. Because it splits the secret operation across the two prime factors, it also opens a physical-fault attack surface that the single-modulus form does not have.
</Definition>

Hold those two choices in mind: the small public exponent and the CRT shortcut will each come back to bite an implementation that treats them casually. But the deepest seed was planted in the 1978 paper itself, and it was invisible at the time.

Rivest, Shamir, and Adleman demonstrated the trapdoor on *raw* message numbers. That bare application is deterministic, algebraically malleable, and carries structure an attacker can exploit -- three properties that, in 1978, looked like harmless features of a clean mathematical object. One operation, elegant enough to both lock and sign. So why is calling that operation directly -- what cryptographers now dismiss as "textbook RSA" -- treated as a bug in every serious codebase?

## 3. Why Textbook RSA Is Not a Cryptosystem

Encryption has a minimum bar -- lower than most people think -- and textbook RSA fails to clear it. The bar is called [IND-CPA](/blog/secure-against-whom-the-security-definitions-every-protocol-/): an adversary who picks two plaintexts and receives the encryption of one cannot tell which, better than a coin flip. (Part 1 of this series builds that definition carefully; here we only need its consequences.) Bare RSA loses this game three separate ways, each a direct consequence of the naked permutation.

**It is deterministic.** The same plaintext always encrypts to the same ciphertext, because $m^e \bmod N$ is a function with no randomness in it. That is fatal whenever the message space is small or guessable. Suppose a server encrypts a one-word trading instruction, either `BUY` or `SELL`, under a known public key. An eavesdropper does not need to decrypt anything: they encrypt both candidate words, compare against the captured ciphertext, and read the plaintext with zero queries. Determinism can never be semantic security -- this is structural, not a missing optimization you can bolt on later.

**It is malleable.** RSA is multiplicatively homomorphic: multiply a ciphertext by $k^e$ and the plaintext is silently multiplied by $k$.

<Definition term="Malleability (homomorphic property)">
A cipher is malleable when an attacker can transform a ciphertext into another valid ciphertext whose plaintext is a predictable function of the original -- without decrypting anything. RSA satisfies the multiplicative relation: the encryption of m times the encryption-form of k decrypts to m times k, modulo N. Useful for some protocols, catastrophic for confidentiality, and the exact algebraic lever Bleichenbacher later pulls.
</Definition>

That relation is not a curiosity; it is the crowbar behind the entire padding-oracle lineage. The demonstration below uses toy primes so the arithmetic is legible in a browser, but the algebra is identical at 2,048 bits.

<RunnableCode lang="js" title="Textbook RSA is deterministic AND malleable (toy, insecure sizes)">{`
// Toy RSA: p=61, q=53, N=3233, e=17, d=2753. NOT secure sizes -- for illustration.
function modpow(base, exp, mod) {
  base = base % mod; let r = 1n;
  while (exp > 0n) {
    if (exp & 1n) r = (r * base) % mod;
    base = (base * base) % mod; exp >>= 1n;
  }
  return r;
}
const N = 3233n, e = 17n, d = 2753n;
const m = 42n;

// 1) Deterministic: encrypting the same message twice gives the same ciphertext.
const c1 = modpow(m, e, N), c2 = modpow(m, e, N);
console.log('encrypt 42 twice ->', c1.toString(), c2.toString(), '| identical?', c1 === c2);

// 2) Malleable: multiply the ciphertext by k^e and the plaintext scales by k.
const k = 2n;
const cForged = (c1 * modpow(k, e, N)) % N;      // attacker never decrypts
const mForged = modpow(cForged, d, N);           // what the victim would recover
console.log('tampered ct decrypts to', mForged.toString(), '= (42*2) mod N =', ((m * k) % N).toString());
`}</RunnableCode>

**It leaks structure for small exponents and short messages.** If a message is short enough that $m^e < N$, no modular reduction ever happens, so recovering $m$ is a plain integer $e$-th root -- no factoring required.

Johan Hastad showed in 1988 that if the same message is broadcast to $e$ recipients under $e = 3$, the plaintext falls out by the Chinese Remainder Theorem [@hastad88]. Don Coppersmith sharpened this in 1996 into a lattice method that recovers a message whenever the unknown part is smaller than $N^{1/e}$, breaking "stereotyped" messages with a small hidden field [@coppersmith97]. Every one of these is an attack on *textbook* RSA, not on the RSA problem itself -- the factoring assumption stays intact while the plaintext walks out the front door [@boneh99].

So a trapdoor permutation is not a cryptosystem. To become one, it needs a transformation applied to the message *before* the permutation -- padding -- and that padding has to do three separable jobs.

> **Key idea:** A trapdoor becomes a cryptosystem only when the padding does three separable jobs: (1) add **randomness**, so equal plaintexts produce different ciphertexts; (2) add **checkable redundancy**, so the receiver can detect a tampered or malformed ciphertext; and (3) -- the job the field kept forgetting -- be **implemented so that no observable behaviour reveals whether that check passed.**

The first two jobs are about the *scheme*. The third is about the *implementation*, and the entire history of RSA breaks is the field learning, over and over, that the third job is not optional. Hold that third clause; it is the trap the next section springs.

> **Note:** If your code invokes a modular-exponentiation "textbook RSA" function directly on a message -- no OAEP, no PSS, no padding layer -- it is broken before it ships. Every serious library hides the bare permutation precisely so that no application accidentally uses it as encryption or a signature.

The first widely deployed answer to those three jobs was PKCS#1 version 1.5, specified by RSA Laboratories in the early 1990s and republished as RFC 2313 in 1998 [@rfc2313]. For encryption, it wraps the message as `0x00 || 0x02 || PS || 0x00 || M`, where `PS` is at least eight nonzero random bytes -- that random padding supplies job one [@rfc8017]. For signatures it uses a different, fixed frame, `0x00 || 0x01 || 0xFF...0xFF || 0x00 || DigestInfo`, whose rigid structure supplies job two [@rfc8017].

On paper it fixed textbook RSA's two headline problems: the random bytes killed determinism, and the fixed structure gave the receiver something to check. For five years, it looked as if PKCS#1 v1.5 had turned the trapdoor into a cryptosystem. The structure was supposed to *add* security. In 1998, Daniel Bleichenbacher showed that the structure was the vulnerability.

## 4. The Atom and Its Echoes: The Encryption Padding-Oracle Lineage

Before the detailed walk, here is the whole story on one timeline -- two intertwined tracks, the schemes on one side and the breaks on the other, with each break forcing the next response.

<Mermaid caption="Fifty years of RSA as two intertwined tracks: schemes and standards on one hand, breaks on the other. Every scheme in the catalog was a forced response to the break above it.">
timeline
    title RSA schemes and their breaks, 1976 to 2026
    1977 : RSA trapdoor answers the Diffie-Hellman challenge
    1990 : Wiener breaks small private exponents
    1993 : PKCS#1 v1.5 padding deployed
    1997 : Bellcore CRT fault factors N from one signature
    1998 : Bleichenbacher padding oracle : OAEP standardized in response
    2001 : Manger reopens the oracle inside OAEP decoders
    2003 : Remote timing attacks proven practical : PSS standardized
    2016 : DROWN revives the oracle through SSLv2
    2017 : ROCA factors structured Infineon keys
    2018 : ROBOT signs with the facebook.com key : TLS 1.3 deletes RSA key exchange
    2023 : Marvin recovers keys by timing alone
    2024 : NIST IR 8547 sets the quantum retirement clock
    2025 : CFRG draft moves to deprecate v1.5 encryption
</Mermaid>

Bleichenbacher's insight was not about RSA the mathematics at all. It was about a server's manners. A TLS server in the 1990s received an RSA-encrypted pre-master secret, decrypted it, and checked whether the result had valid PKCS#1 v1.5 padding -- did it start with the bytes `0x00 0x02`, with a nonzero pad and a delimiter in the right place? If not, it returned an error. That error, however polite, answered a question the attacker was not supposed to be able to ask: *was this the encryption of a well-formed message?* And because RSA is malleable, the attacker could turn that one bit of feedback into a full decryption.

Here is the mechanism. The attacker holds a target ciphertext $c$ that encrypts an unknown $m$ -- say, a captured TLS session key. They pick a value $s$, compute $c \cdot s^e \bmod N$, and send it to the server. By the homomorphic property, the server is really decrypting $m \cdot s \bmod N$. If the server reports valid padding, the attacker learns that $m \cdot s \bmod N$ begins with `0x00 0x02` -- which means it lies in the interval $[2B, 3B)$, where $B = 2^{8(k-2)}$ for a $k$-byte modulus.

Each conforming $s$ is a linear inequality on the secret $m$. Collect enough of them, adaptively choosing each new $s$ to bisect the surviving range, and the interval of possible $m$ collapses to a single value. Bleichenbacher's 1998 paper showed this takes on the order of $2^{20}$ -- about a million -- queries for a 1,024-bit key, and the private key is never touched [@bleichenbacher98].

<Mermaid caption="Bleichenbacher's adaptive padding oracle: each query multiplies the target ciphertext by a chosen value, and the server's valid-or-invalid verdict narrows the interval containing the secret until it collapses to the plaintext.">
sequenceDiagram
    participant A as Attacker
    participant S as Decrypting server
    Note over A: Holds target ciphertext c, wants secret m
    A->>S: Submit c times s to the e, for chosen s
    S->>S: Decrypt and check PKCS#1 v1.5 padding
    alt Decrypted value starts with 00 02
        S-->>A: Conforming, no error or fast reply
        Note over A,S: Attacker learns m times s mod N is in 2B to 3B
    else Padding invalid
        S-->>A: Non-conforming, error, alert, or slow reply
    end
    Note over A: Narrow the possible range of m, choose next s
    A->>S: Repeat, roughly a million queries in total
    Note over A: Range collapses to one value, plaintext m recovered
</Mermaid>

A generation of engineers filed this under "performance" or "obscure edge case." It is neither. It is a correctness and security failure of the *construction*: the receiver's validity check, exposed through any observable side effect, is a decryption oracle for chosen ciphertexts. That is the [symmetric-side padding-oracle attack](/blog/they-read-your-plaintext-without-breaking-your-cipher-a-fiel/) of Part 6, transplanted to public-key land -- the same disease, a different organ.

<Definition term="Padding oracle">
Any observable behaviour -- an error message, a network reset, an injected fault, or a difference in response time -- that reveals whether a decrypted ciphertext had valid padding. Because the attacker chooses the ciphertexts, a padding-validity signal becomes a decryption oracle: enough yes-or-no answers reconstruct the plaintext without ever recovering the private key.
</Definition>

The break violates the strongest standard security goal for encryption, IND-CCA2, in which the adversary may submit chosen ciphertexts to a decryption oracle and still must not learn anything about a challenge plaintext.

<Definition term="IND-CCA2 (chosen-ciphertext security)">
The security goal a padding oracle destroys: an adversary who can submit arbitrary ciphertexts for decryption still cannot distinguish which of two chosen plaintexts a challenge ciphertext encrypts. PKCS#1 v1.5 encryption fails this because its validity check leaks. Part 1 of this series develops the full definition.
</Definition>

The scheme-level fix arrived almost immediately. In direct response to Bleichenbacher, RSA Laboratories standardized a new encryption padding, RSAES-OAEP, in PKCS#1 v2.0 (RFC 2437) later in 1998 [@rfc2437]. OAEP's design goal, spelled out in Section 6, is that any tampered ciphertext decodes to unstructured noise, so there is no "conformant" interval left to test -- the oracle has nothing to grade. It fixed the scheme. What it did not, and could not, fix by itself was the decoder.

James Manger proved that in 2001. OAEP's decoding has two distinct early failure modes: the recovered integer can be too large to fit the byte block, or it can fit but fail the padding check. A decoder that distinguishes those two cases through different errors or different timing hands the attacker a *new* oracle -- and Manger's variant is dramatically cheaper than Bleichenbacher's, needing on the order of $\log_2 N$ queries, roughly 2,048 for a 2,048-bit key, instead of $2^{20}$ [@manger01]. OAEP, the provably secure scheme, re-opened the identical class of attack through an imperfect implementation. The lesson the field wrote down, and then kept having to re-learn, was not "use OAEP." It was "use OAEP *and* decode it in constant time."

If Bleichenbacher's attack is the atom, the next quarter-century is three quieter echoes of it -- the same leaked bit, reached through channels that get progressively harder to see.

**DROWN (2016): a cross-protocol channel.** By 2016, TLS servers had long since patched the obvious padding-error message. But many still supported SSLv2, an obsolete protocol from the 1990s, often on a different service such as a mail server -- and often with the *same* RSA key. DROWN showed that an attacker could use the weak, deliberately export-crippled SSLv2 endpoint as the padding oracle, then use its answers to decrypt a modern TLS session that shared the key.<Sidenote>The DROWN team measured that roughly 33 percent of all HTTPS servers were vulnerable at disclosure in March 2016, because key reuse across a TLS service and a forgotten SSLv2 service was rampant [@drownsite].</Sidenote> The math of the oracle was 1998's; only the delivery was new [@drown16].

**ROBOT (2018): the same oracle, nineteen years on.** Hanno Bock, Juraj Somorovsky, and Craig Young revisited the original attack and found it alive across the modern internet. The padding-error message was gone, but the oracle now leaked through subtler tells: a TCP reset here, a connection timeout there, a duplicated alert message somewhere else -- any behaviour that differed between conforming and non-conforming padding. It affected almost a third of the top 100 domains, including Facebook and PayPal, and traced to products from F5, Citrix, Radware, Palo Alto Networks, IBM, and Cisco [@robot18].<Sidenote>To make the point unmissable, the ROBOT authors used the recovered oracle to sign a message with the private key behind facebook.com's certificate -- a decryption oracle repurposed to forge a signature, without ever touching the factorization [@robotsite].</Sidenote>

**Marvin (2023): pure timing, no error at all.** The quietest channel yet removes the error entirely. Hubert Kario's Marvin attack observes only the *time* the decryption operation takes, since a conforming and a non-conforming padding often run through subtly different code paths. No alert, no reset, no message -- just a stopwatch. Marvin re-found exploitable leaks in implementations that had been declared immune after ROBOT, and it reaches well beyond TLS into S/MIME, JSON Web Tokens, and hardware tokens such as HSMs and smartcards [@marvin23]. The peer-reviewed write-up appeared at ESORICS 2023 under the fitting title *Everlasting ROBOT* [@eprint2023]. Its recommendation was blunt: stop using PKCS#1 v1.5 encryption.

> **Note:** Every member of this lineage leaks the same single bit -- was the padding valid? -- through a different channel. You cannot patch your way to safety one channel at a time, because the next channel is always quieter than the last. The only durable fixes are structural: remove the mode (as TLS 1.3 did) or forbid it (as FIPS did). If a standard forces RSA encryption, use OAEP with constant-time decoding, never v1.5.

Read the four together and the pattern is impossible to miss. The channel gets quieter each time -- an error string in 1998, a cross-protocol zombie in 2016, a TCP quirk in 2018, a bare microsecond in 2023 -- but the leaked bit never changes. This is why "add more padding" was never the answer and constant-time, uniform-failure decoding was. The catalog below is the evidence for this article's whole argument: every row is some party using the bare trapdoor as if it were a scheme, or letting a check confess.

| Attack | Year | Front | Leaked channel | Root cause | The rule it teaches |
|---|---|---|---|---|---|
| Textbook RSA [@rsa78] | 1978 | Encryption | None needed | Deterministic, malleable bare permutation | Never encrypt with the raw primitive |
| Hastad / Coppersmith [@hastad88, @coppersmith97] | 1988 / 96 | Params | Algebraic structure | Small e, short or related messages | Pad first, use e equals 65537 |
| Bleichenbacher [@bleichenbacher98] | 1998 | Encryption | Padding-error message | v1.5 validity check is a decryption oracle | Uniform, unobservable failure |
| Manger [@manger01] | 2001 | Implementation | Error-type or timing split | Non-constant-time OAEP decode | OAEP AND constant-time decoding |
| DROWN [@drown16] | 2016 | Encryption | SSLv2 cross-protocol | Same RSA key on a weak zombie protocol | Never reuse keys, kill SSLv2 |
| ROBOT [@robot18] | 2018 | Encryption | TCP reset, timeout, alert | v1.5 oracle still live behind subtle tells | Remove v1.5 key exchange |
| Marvin [@marvin23] | 2023 | Implementation | Decryption timing only | Non-constant-time v1.5 depadding | Retire v1.5 encryption entirely |
| e equals 3 forgery [@cve2006] | 2006 | Signature | None, forged offline | Lax verifier ignores trailing bytes | Verify strictly, parse it all |
| BERserk [@cve2014] | 2014 | Signature | None, forged offline | NSS mis-parses ASN.1 lengths | Verify strictly, re-encode and compare |
| Bellcore fault [@bdl97] | 1997 | Implementation | One faulty signature | CRT fault reveals a prime by gcd | Verify signature before release |
| Kocher, Brumley-Boneh [@kocher96, @brumleyboneh03] | 1996 / 2003 | Implementation | Exponentiation timing | Secret-dependent modexp time | Base blinding, constant time |
| Wiener [@wiener90] | 1990 | Params | Public key structure | Private exponent d too small | Never shrink d for speed |
| Mining Ps and Qs [@miningpq12] | 2012 | Params | Shared prime factors | Low boot-time entropy at keygen | Seed the CSPRNG properly |
| ROCA [@roca17] | 2017 | Params | Public modulus structure | Infineon's structured primes | Generate primes uniformly |

Fourteen rows, one disease. But the encryption oracle is only one of four ways the bare trapdoor betrays its owner. The other three -- the lazy verifier, the glitched chip, and the badly chosen numbers -- are just as instructive, and one of them factors your modulus from a single fault.

## 5. The Rest of the Catalog: Signatures, Faults, and Bad Primes

If the encryption oracle is the trapdoor leaking through the decryptor's *answer*, the remaining breaks are the trapdoor leaking through the verifier's *laziness*, the hardware's *faults*, and the *numbers* you fed it. Three fronts, and the encryption-versus-signature split stays absolute across all of them.

### Front A: the signature track, and the precision that governs it

Start with a fact that surprises people who lump all of v1.5 together: RFC 8017 records **no known attack against the RSASSA-PKCS1-v1_5 *signature scheme itself*** [@rfc8017]. Unlike v1.5 encryption, the signature padding has never been broken as a construction. It rests on a heuristic argument rather than a tight proof, which is why cryptographers reach for PSS in new designs, but it is legacy-not-broken. Where it *is* fragile is at the verifier -- and that fragility has bitten twice.

**The $e = 3$ forgery (2006, CVE-2006-4339).** Daniel Bleichenbacher -- the same name, a different result eight years later -- described a forgery that needs no private key at all. A v1.5 signature block ends with the ASN.1 `DigestInfo` structure, and a lazy verifier checks that the high-order bytes look right without confirming that the `DigestInfo` sits flush against the end with no trailing data.

With a small public exponent such as $e = 3$, an attacker can construct a number whose cube reproduces the correct prefix and hash in the leading bytes, then pack arbitrary garbage into the trailing bytes the verifier never inspects. Because cubing is cheap and the low bytes are free, the forged "signature" is just a carefully chosen cube root [@cve2006]. OpenSSL's advisory of 5 September 2006 traced it to exactly that omission: "not checking for excess data" after the exponentiation [@openssl2006].

**BERserk (2014, CVE-2014-1568).** Eight years on, the same antipattern returned in a different guise. Mozilla's NSS library mis-parsed ASN.1 length fields during signature verification, letting an attacker smuggle forged content past the check and produce signatures that NSS -- and therefore Firefox and Chrome builds of the era -- accepted as valid, including for TLS certificates [@cve2014]. Once again, no scheme was broken; a verifier was.

The recurring lesson is one line: **verify strictly.** Parse the entire structure, reject any trailing data, re-encode the expected block and compare it byte-for-byte, and never take an $e = 3$ shortcut. The provable alternative, PSS, removes the temptation to hand-roll a lenient check by making the encoding randomized and its verification total; its mechanism is in the next section [@pss96]. These verifier bugs live where v1.5 signatures live -- inside the [X.509 and PKI machinery](/blog/a-perfect-signature-for-a-certificate-that-should-never-have/) that Part 4 of this series covers.

<Aside label="The one split you must never blur">
"Still-deployed PKCS#1 v1.5" hides two opposite truths, and conflating them is the single most common error in RSA writing. v1.5 *encryption* (RSAES-PKCS1-v1_5) is fundamentally dangerous padding: its validity check is a decryption oracle, and it should be retired. v1.5 *signatures* (RSASSA-PKCS1-v1_5) are dominant across Web PKI, FIPS-approved in FIPS 186-5, and unbroken as a scheme -- keep them where mandated and verify strictly [@rfc8017], [@fips1865]. One phrase must never carry both meanings. When you read "RSA v1.5 is broken," ask which one, because the honest answer is "the encryption, not the signatures."
</Aside>

### Front B: the physical layer

Here the secret *is* the factorization, so anything the hardware leaks about the private operation leaks the factors directly.

**The CRT fault (Boneh, DeMillo, and Lipton, 1997).** Recall that fast RSA signing computes the result modulo $p$ and modulo $q$ separately, then recombines. Suppose a single bit flips during the modulo-$p$ half -- from a voltage glitch, a clock fault, cosmic radiation, or a deliberate injection. The faulty signature $s'$ is now correct modulo $q$ but wrong modulo $p$. Then $s'^e - m$ is divisible by $q$ but not by $p$, so a single $\gcd(s'^e - m, N)$ hands you $q$ -- and the modulus is factored from *one* faulty signature [@bdl97]. The demonstration below does exactly that with toy primes.

<RunnableCode lang="js" title="One faulty CRT signature factors N by a single gcd (toy sizes)">{`
// Bellcore fault: a fault in one CRT half leaks a prime of N. Toy primes for clarity.
function modpow(base, exp, mod) {
  base = ((base % mod) + mod) % mod; let r = 1n;
  while (exp > 0n) { if (exp & 1n) r = (r * base) % mod; base = (base * base) % mod; exp >>= 1n; }
  return r;
}
function gcd(a, b) { while (b) { const t = a % b; a = b; b = t; } return a; }
const p = 61n, q = 53n, N = p * q, e = 17n, d = 2753n;
const m = 123n % N;                       // message representative to sign
const dp = d % (p - 1n), dq = d % (q - 1n);
const qInv = modpow(q, p - 2n, p);

// Correct CRT signature (Garner recombination):
const sp = modpow(m, dp, p), sq = modpow(m, dq, q);
const s = (sq + q * (((qInv * (sp - sq)) % p + p) % p)) % N;
console.log('correct signature verifies?', modpow(s, e, N) === m);

// A fault corrupts ONLY the mod-p half:
const spBad = (sp + 1n) % p;
const sBad = (sq + q * (((qInv * (spBad - sq)) % p + p) % p)) % N;
console.log('faulty  signature verifies?', modpow(sBad, e, N) === m);

// One gcd factors the modulus:
const diff = ((modpow(sBad, e, N) - m) % N + N) % N;
console.log('gcd(sBad^e - m, N) =', gcd(diff, N).toString(), '-> a secret prime of N (61 or 53)');
`}</RunnableCode>

The fix is a single line of discipline: **verify before release.** Recompute $s^e \bmod N$ and confirm it equals $m$ before the signature ever leaves the chip. A faulty signature never escapes, and the gcd trick has nothing to work with.

**Timing (Kocher, 1996; Brumley and Boneh, 2003).** Paul Kocher observed in 1996 that the time to compute $c^d \bmod N$ depends on the secret bits of $d$, because square-and-multiply does extra work on `1` bits [@kocher96]. Folklore held that timing attacks needed local access. David Brumley and Dan Boneh demolished that in 2003 by recovering an OpenSSL server's private key *over a network*, measuring only response times [@brumleyboneh03].

The fix is **base blinding**: multiply the input by $r^e$ for a fresh random $r$ before exponentiating, then divide the result by $r$ afterward, so the timing depends on a value the attacker cannot predict. OpenSSL turned blinding on by default in 2003. Marvin, from the previous section, is this front's 2023 revival -- the timing channel never truly closed.

### Front C: the parameters

The trapdoor is only as strong as the numbers behind it.

- **Wiener (1990).** If you shrink the private exponent for speed so that $d < \tfrac{1}{3} N^{1/4}$, a continued-fraction expansion of $e/N$ recovers $d$ outright [@wiener90]. You cannot buy decryption speed by making the secret small.
- **Coppersmith (1996 to 1997).** His lattice method sets the barrier $|x| < N^{1/e}$ that both *enables* low-exponent attacks on short or stereotyped messages and *bounds* them -- the same result that returns, weaponized, as ROCA [@coppersmith97].
- **Mining Your Ps and Qs (2012).** Heninger and colleagues scanned the internet's public keys and computed pairwise gcds. Devices that generated keys at first boot, before they had gathered entropy, sometimes shared a prime -- and a shared prime means a free gcd factors both moduli. They computed private keys for about 0.50 percent of TLS hosts and 0.03 percent of SSH hosts this way [@miningpq12].
- **ROCA (2017, CVE-2017-15361).** Infineon's key-generation library built primes with a special structure to speed things up. That structure let a Coppersmith attack factor the public modulus for a practical cost, and the affected chips were everywhere: TPMs, YubiKey 4 tokens, national electronic ID cards, and BitLocker deployments [@roca17], [@cve2017]. Coppersmith's 1996 barrier, patient for twenty years, collected its debt.

The root cause of the last two is not RSA math at all -- it is the [CSPRNG that generates the primes](/blog/predictable-or-repeated-the-only-two-ways-cryptographic-rand/), the subject of Part 2 of this series. Feed RSA weak randomness and no scheme, no padding, and no proof can save it.

> **Note:** Turn the diagnostic question on each front and it answers itself. The verifier confesses through a check it skipped. The chip confesses through a fault it did not catch. The clock confesses through a branch it did not equalize. The keygen confesses through primes it did not draw uniformly. In every case the attacker reads the private key off the receiver's *behaviour*, not off the mathematics.

Keep the empirical yardstick in view: the largest RSA modulus ever publicly factored is RSA-250, at 829 bits.<Sidenote>RSA-250 was factored on 28 February 2020 using the Number Field Sieve, at a cost of roughly 2,700 core-years of computation [@rsa250]. That is the real, measured cost of breaking RSA by its front door -- which is exactly why nobody attacks that door when a padding check will open the side gate for a million cheap queries.</Sidenote> Four fronts, one disease. The cure is not a cleverer patch on any single front. It is a change in what we mean when we say a scheme is secure.

## 6. Security Is a Property of the Scheme AND the Implementation

There are two famous ideas behind "RSA done right," and a third, deeper one that the first two kept teaching the hard way.

### Idea 1: OAEP, the all-or-nothing randomized transform

Optimal Asymmetric Encryption Padding, designed by Mihir Bellare and Phillip Rogaway in 1994, encodes the message before the RSA permutation so that the encoded block has no gradable structure for an attacker to probe [@oaep94]. Its construction is a two-round Feistel network with a hash-based mask-generation function, MGF1, as the round function -- the [hashing machinery](/blog/the-fingerprint-two-files-shared-a-field-guide-to-cryptograp/) that Part 10 of this series develops. Writing $\Vert$ for concatenation and $\oplus$ for XOR, and starting from a random $\mathrm{seed}$:

$$\mathrm{DB} = \mathrm{lHash} \Vert \mathrm{PS} \Vert \texttt{0x01} \Vert M$$
$$\mathrm{maskedDB} = \mathrm{DB} \oplus \mathrm{MGF1}(\mathrm{seed}), \qquad \mathrm{maskedSeed} = \mathrm{seed} \oplus \mathrm{MGF1}(\mathrm{maskedDB})$$
$$\mathrm{EM} = \texttt{0x00} \Vert \mathrm{maskedSeed} \Vert \mathrm{maskedDB}$$

Then the RSA permutation is applied to $\mathrm{EM}$ [@rfc8017]. The two Feistel rounds make every bit of the encoded block depend on every bit of the message *and* the random seed. That is the property that kills the padding oracle: flip a single bit of an OAEP ciphertext and the decoded block is randomized wholesale, so a tampered ciphertext decodes to noise with overwhelming probability. There is no conformant interval to bisect, no structured remnant to grade.

With the randomness supplying non-determinism and the all-or-nothing mixing supplying tamper-detection, OAEP is not only semantically secure but also non-malleable and secure against chosen-ciphertext attack -- IND-CCA2 in the random-oracle model [@oaep94abs].

<Definition term="RSAES-OAEP">
Optimal Asymmetric Encryption Padding: a randomized, all-or-nothing transform applied to a message before the RSA permutation. It mixes the message with a random seed through two mask-generation passes -- a two-round Feistel network -- so that every bit of the encoded block depends on every bit of the input. Flipping any ciphertext bit randomizes the whole decoded block, which destroys malleability and yields chosen-ciphertext security in the random-oracle model.
</Definition>

<Aside label="A rare, healthy kind of failure">
OAEP's history includes a moment cryptography should be proud of. In 2001, Victor Shoup showed that the celebrated 1994 security proof did not go through for an arbitrary trapdoor permutation -- it quietly assumed more than the definition guarantees [@shoup01]. The scheme was not broken; the *argument* was. Later that year, Fujisaki, Okamoto, Pointcheval, and Stern repaired it, proving RSA-OAEP is chosen-ciphertext secure in the random-oracle model under the RSA assumption, by leaning on a property called partial-domain one-wayness -- though the resulting reduction is non-tight [@fops04]. A public "our proof, not our scheme, was wrong," followed by a public fix, is exactly how a mature field is supposed to work.
</Aside>

### Idea 2: PSS, the salted encoding with a tight proof

For signatures, the Probabilistic Signature Scheme, also from Bellare and Rogaway, plays the analogous role [@pss96]. To sign, it hashes the message to $\mathrm{mHash}$, draws a random $\mathrm{salt}$, and forms $M' = \texttt{padding} \Vert \mathrm{mHash} \Vert \mathrm{salt}$; sets $H = \mathrm{Hash}(M')$; builds $\mathrm{DB} = \mathrm{PS} \Vert \texttt{0x01} \Vert \mathrm{salt}$; masks it as $\mathrm{maskedDB} = \mathrm{DB} \oplus \mathrm{MGF1}(H)$; and assembles $\mathrm{EM} = \mathrm{maskedDB} \Vert H \Vert \texttt{0xbc}$ before applying the RSA private operation [@rfc8017].

The randomization and MGF mixing buy something v1.5 signatures never had: a *tight* exact-security reduction. A forger against PSS implies an algorithm that inverts RSA at almost the same cost -- so breaking the signatures is essentially as hard as the RSA problem itself, not merely conjectured to be [@pss96]. That is strictly stronger than v1.5's heuristic argument. PSS entered the standard in PKCS#1 v2.1 (RFC 3447) in 2003 and remains in the current v2.2 [@rfc3447]. Yet the split holds: PSS is the provable *upgrade*, but v1.5 signatures are not superseded in deployment -- they remain the Web PKI default.<Sidenote>Beyond these two deployed schemes, the literature holds academic-only refinements -- SAEP/SAEP+, OAEP+, three-round OAEP, tight RSA-KEM variants, and message-recovery PSS-R -- which tighten proofs or trim assumptions but never displaced OAEP and PSS in practice. A pointer, not a section.</Sidenote>

<Definition term="RSASSA-PSS">
Probabilistic Signature Scheme: a randomized, salted RSA signature encoding. A fresh random salt and MGF1 mixing make every signature of the same message different, and the scheme comes with a tight security reduction -- a forger would yield an almost-equally-efficient algorithm for inverting RSA, the strongest guarantee any RSA scheme offers.
</Definition>

### Idea 3: the one the first two kept teaching

Here is where the whole article turns. OAEP is provably secure, yet Manger re-opened the identical oracle inside a non-constant-time *decoder*. PSS is provably secure, yet a fault or a timing leak in the *signer* factors the key. The scheme was never the whole story.

> **Key idea:** Security is a property of the scheme AND its implementation, not of the math. A perfect scheme run by a decoder that leaks whether padding verified is exactly as broken as no scheme at all. The implementation disciplines below are part of the construction, not optional hygiene layered on top.

Three disciplines close the three channels the catalog exposed:

- **Constant-time depadding with implicit rejection.** On any decryption failure, do not branch or return a distinguishable error; substitute a deterministic pseudo-random value and continue, so whether the padding verified stays unobservable. OpenSSL 3.2 ships this by default and aligned its behaviour with NSS so neither library can be an oracle for the other [@openssl32], [@gorsa].
- **CRT verify-before-release.** Recompute and check the signature before it leaves the device, defeating Bellcore faults [@bdl97].
- **Base blinding.** Randomize the input before exponentiation so timing reveals nothing about the secret [@kocher96], [@brumleyboneh03].

<Definition term="Implicit rejection (constant-time depadding)">
A decryption strategy in which a padding failure does not produce a distinguishable outcome. Instead of branching or returning a specific error, the code substitutes a deterministic pseudo-random value derived from the private key and ciphertext and proceeds. Success and failure become indistinguishable through content, error type, or timing, so there is no oracle left to query.
</Definition>

<Mermaid caption="RSA done right is a conjunction of three layers. A request passes the scheme, implementation, and parameter layers and then must clear one gate: does any behaviour reveal whether the padding verified? Remove any layer and the answer becomes yes, reopening the catalog.">
flowchart TD
    M[Message or ciphertext arrives] --> SCH&#123;"Scheme layer"&#125;
    SCH -->|Encrypt| OAEP[RSAES-OAEP, randomized all-or-nothing]
    SCH -->|Sign| PSS[RSASSA-PSS, salted with tight proof]
    OAEP --> IMPL&#123;"Implementation layer"&#125;
    PSS --> IMPL
    IMPL --> CT[Constant-time depad, implicit rejection]
    IMPL --> VBR[CRT verify-before-release]
    IMPL --> BL[Base blinding]
    CT --> PAR&#123;"Parameter layer"&#125;
    VBR --> PAR
    BL --> PAR
    PAR --> P1[Modulus at least 2048 bits, e equals 65537, CSPRNG primes]
    P1 --> GATE&#123;"Does any behaviour reveal the padding verdict?"&#125;
    GATE -->|No| SAFE[RSA done right]
    GATE -->|Yes| BROKEN[Oracle reopens, the catalog repeats]
</Mermaid>

The libraries now say this in plain language. Go's standard library deprecated its v1.5 decryption function outright, with a warning that doubles as the thesis of this article:

<PullQuote>
"PKCS #1 v1.5 encryption is dangerous and should not be used ... whether this function returns an error or not discloses secret information." -- Go crypto/rsa package documentation [@gorsa]
</PullQuote>

That is the whole discipline in one sentence: done right closes the padding-oracle class Part 6 traces across all of cryptography, and it does so at the implementation layer, not the math. So what does the whole stack look like in 2024 to 2026 -- and which parts are quietly being switched off?

## 7. State of the Art (2024 to 2026): Done Right Is a Stack, Not a Method

Most primitives have a single "best" option you can name. RSA does not. "Done right" in 2026 is a *conjunction* of independent choices that must all hold at once. Remove any one and the 25-year catalog reopens at that layer. Here is the stack, layer by layer.

| Mode | Job | What it adds | Security status | Still requires |
|---|---|---|---|---|
| v1.5 encryption | Encrypt | Randomness only | Broken as a target -- padding oracle | Retire it; no safe deployment |
| RSAES-OAEP | Encrypt | Randomness plus all-or-nothing mixing | IND-CCA2 in the random-oracle model | Constant-time, implicit-rejection decode |
| v1.5 signature | Sign | Fixed checkable structure | Unbroken scheme, heuristic argument | Strict verification, no e equals 3 shortcut |
| RSASSA-PSS | Sign | Salt plus MGF, tight proof | Provably as hard as the RSA problem | CRT verify-before-release, blinding |

**Encryption scheme.** When a standard genuinely mandates RSA encryption of a small payload, the answer is RSAES-OAEP with SHA-256 and MGF1-SHA-256, decoded in constant time [@rfc8017]. But note the capacity ceiling: a 2,048-bit OAEP-SHA-256 ciphertext carries at most about 190 bytes of plaintext [@sp80056b]. "Encrypt a file with RSA-OAEP" is therefore not just risky but physically wrong -- RSA encryption is for keys, never bulk data.

**Signatures.** New designs use RSASSA-PSS, which TLS 1.3 makes mandatory for handshake signatures [@pss96], [@rfc8446]. Yet RSASSA-PKCS1-v1_5 signatures remain dominant and FIPS-approved across X.509 and TLS certificates [@fips1865]. This is not a contradiction: keep v1.5 signatures where they are mandated, and verify them strictly [@rfc8017].

**Implementation hardening.** This is the layer that actually stops the attacks. OpenSSL 3.2 enables constant-time depadding with implicit rejection by default [@openssl32], Go has deprecated its v1.5 decryption entry point [@gorsa], and the CFRG's 2025 implementation-guidance draft folds all of this into formal advice amending RFC 8017 [@cfrgdraft].

**Parameters.** A 2,048-bit modulus is the floor for 112-bit security; use 3,072 or 4,096 bits for long-term secrets; keep $e = 65537$; and draw primes from a properly seeded CSPRNG [@sp80057], [@fips1865].

**Deployment and policy.** The most durable fixes were structural, not cryptographic. TLS 1.3 *deleted* RSA key exchange entirely, which killed the Bleichenbacher-on-TLS class at the protocol level rather than patching each oracle [@rfc8446]. FIPS policy disallows RSA v1.5 key transport after 31 December 2023 [@sp800131a], [@sp80056b]. And NIST IR 8547 puts a clock on RSA itself, deprecating 112-bit strength after 2030 and disallowing it after 2035 [@ir8547].

<Aside label="Why this matters for compliance">
If you operate under FIPS 140-3, the encryption side of this is not advisory. NIST SP 800-131A Rev. 2 and SP 800-56B Rev. 2 together disallow RSAES-PKCS1-v1_5 key transport after 31 December 2023; approved RSA key establishment must use OAEP [@sp800131a], [@sp80056b]. The signature side is the opposite: RSASSA-PKCS1-v1_5 signatures remain FIPS-approved under FIPS 186-5 [@fips1865]. Same version number, opposite compliance verdicts -- which is exactly why the encryption-signature split is not pedantry.
</Aside>

> **Note:** Right scheme (OAEP to encrypt, PSS for new signatures), right implementation (constant-time depad with implicit rejection, CRT verify-before-release, base blinding), right parameters (2,048-bit floor, e equals 65537, CSPRNG primes), inside the right protocol (TLS 1.3, no RSA key exchange). Every deployed disaster in the catalog removed exactly one of these. None of it is new in 2026; the interesting movement is not toward a better RSA but away from RSA entirely.

RSA done right is *stable*. The genuinely current story is mostly about what to switch off and what is migrating away -- because for both of RSA's jobs, something smaller and faster is already taking over.

## 8. What RSA Is Losing To: ECDH, KEM-DEM, and the Post-Quantum Elephant

RSA is not being fixed into the future; it is being replaced out of it -- and the reasons have nothing to do with padding.

The cleanest of those reasons is a design pattern that removes the attacker's target entirely. Never RSA-encrypt data. Instead, encapsulate a fresh random *symmetric* key with the public key, and let an authenticated cipher carry the bulk. The public-key operation then transports only a uniform random key -- there is no attacker-chosen, structured plaintext for any oracle to grade. The entire Bleichenbacher-to-Marvin family loses its object, because the thing being decrypted is indistinguishable from random by construction [@rfc8446].

<Definition term="KEM-DEM">
A two-part construction for hybrid encryption. A Key Encapsulation Mechanism (KEM) uses the public key to transport a freshly generated random symmetric key; a Data Encapsulation Mechanism (DEM) then encrypts the actual data with that key under an authenticated cipher. Because the public-key step only ever carries a uniform random key -- never a chosen, structured message -- there is no padding structure for an oracle to probe, so the padding-oracle class simply does not apply.
</Definition>

<Mermaid caption="KEM-DEM: the public-key operation transports only a uniform random key, which a KDF stretches and an AEAD uses to encrypt the bulk. There is no attacker-chosen structured plaintext for a padding oracle to grade.">
sequenceDiagram
    participant S as Sender
    participant R as Recipient
    Note over R: Publishes a public key
    S->>S: Encapsulate, generate a random key K for the recipient
    S->>S: Stretch K with a KDF, AEAD-encrypt the data
    S->>R: Send the encapsulation and the AEAD ciphertext
    R->>R: Decapsulate to recover K, run the same KDF
    R->>R: AEAD-decrypt and verify the data
    Note over R,S: The public-key part carried only a random K, nothing to grade
</Mermaid>

This is why elliptic-curve key agreement (ECDH, with Ed25519 and ECDSA for signatures) displaced RSA key transport: it does the same jobs with far smaller keys, faster operations, and forward secrecy -- a property RSA key transport never had, and the direct reason TLS 1.3 could *delete* RSA key exchange rather than merely patch it [@rfc8446]. The [KEM-DEM composition](/blog/the-tag-verified-the-cipher-held-the-forgery-went-through-a-/) is developed in Part 11 of this series, the KDF step in Part 13, and the [AEAD that carries the payload](/blog/the-aead-decision-matrix-seven-ciphers-three-edges-one-choic/) in Part 7.

Then there is the elephant. Peter Shor's algorithm factors integers in polynomial time on a large fault-tolerant quantum computer, which makes *all* factoring-based cryptography -- every RSA key length, done right or not -- eventually breakable. NIST has already named the destination: ML-KEM (FIPS 203) for key encapsulation, and ML-DSA and SLH-DSA (FIPS 204 and 205) for signatures [@fips203], [@fips204], [@fips205].

The migration is lopsided. Key encapsulation is moving fast -- hybrid X25519 plus ML-KEM-768 already carries a double-digit percentage of Cloudflare's TLS 1.3 traffic -- while post-quantum *signatures* lag badly, because they run 10 to 200 times larger than an RSA signature and no public post-quantum certificate infrastructure existed before roughly 2026 [@cloudflare24], [@ir8547]. The lattice and hash-based internals belong to a later part of this series; here they matter only as RSA's replacement, not its repair.

<Aside label="Harvest now, decrypt later">
Quantum risk is not only a future problem. An adversary can record RSA-encrypted traffic today and decrypt it once a capable quantum computer exists. For any secret that must stay confidential past roughly 2030, the exposure is *present tense* -- which is why NIST IR 8547 frames the transition as urgent rather than eventual, and why hybrid key exchange is being deployed now rather than when the machine arrives [@ir8547], [@cloudflare24].
</Aside>

Laid side by side, the trade-offs explain why key transport migrated first and signatures are dragging. For moving a key:

| Key transport | Forward secrecy | Padding-oracle exposure | Relative cost | Quantum status |
|---|---|---|---|---|
| RSAES-OAEP [@rfc8017] | No | Yes, if decode is not constant-time | Large ciphertext, slow keygen | Broken by Shor |
| ECDH (X25519) [@rfc8446] | Yes | None, no RSA decryption | Small and fast | Broken by Shor |
| ML-KEM-768 [@fips203] | Yes (ephemeral) | None | Kilobyte-scale, fast | Resistant |
| Hybrid X25519 + ML-KEM-768 [@cloudflare24] | Yes | None | Sum of both, still practical | Resistant if either holds |

And for signing:

| Signature | Provable security | Approx. signature size | Main failure mode | Quantum status |
|---|---|---|---|---|
| RSASSA-PSS [@pss96] | Yes, tight in ROM | 256 bytes at 2048-bit | Fault or timing in the signer | Broken by Shor |
| RSASSA-PKCS1-v1_5 [@rfc8017] | No, heuristic only | 256 bytes at 2048-bit | Lax-verifier forgery | Broken by Shor |
| ECDSA / Ed25519 [@rfc8446] | Yes | 64 bytes | Nonce reuse (ECDSA) | Broken by Shor |
| ML-DSA-65 [@fips204] | Yes, lattice | About 3.3 kilobytes | Implementation bugs | Resistant |
| SLH-DSA [@fips205] | Yes, hash-based | Many kilobytes | Large and slow | Resistant |

The signature column is the migration's hard problem, which is why post-quantum certificates lag key exchange by years [@ir8547]. If RSA is on the clock, it is worth asking where its security actually came from in the first place -- and why nobody has ever proved it was there.

## 9. Theoretical Limits: Where the Security Comes From, and Its Ceiling

Here is the uncomfortable truth a first course skips: there is no proof that RSA is secure.

Start with the assumption itself. The RSA problem is to compute $e$-th roots modulo $N$ without the factorization. We know this is *no harder* than factoring -- if you can factor $N$, you can compute $d$ and invert everything, so RSA $\le$ factoring. What nobody has shown is the reverse. It is an open question whether breaking RSA is *equivalent* to factoring, and Boneh and Venkatesan gave evidence that a broad class of algebraic reductions from factoring to low-exponent RSA is unlikely to exist -- suggesting the two problems may not be equivalent at all [@bv98].

Worse, factoring itself is not known to be hard in any proven sense: it sits in NP intersect co-NP, which is evidence it is probably *not* NP-complete, and no one has proved a super-polynomial lower bound for it. RSA's security is heuristic and empirical -- it has survived decades of attack, and that is the entire argument [@boneh99].

The empirical ceiling is concrete. The best classical algorithm, the General Number Field Sieve, runs in sub-exponential time, and the public record is RSA-250 at 829 bits, factored in February 2020 for roughly 2,700 core-years [@rsa250]. RSA-250 was one of the RSA Factoring Challenge moduli that RSA Laboratories first published in 1991 as public benchmarks for exactly this kind of progress [@rsanumbers]. That record sets the practical floors:

| RSA modulus | Symmetric-equivalent strength | Status |
|---|---|---|
| 1024-bit | About 80 bits | Broken within reach, disallowed |
| 2048-bit | 112 bits | Current minimum, deprecated after 2030 |
| 3072-bit | 128 bits | Long-term use |
| 4096-bit | About 140 bits (interpolated) | High assurance |
| 7680-bit | 192 bits | Next tabulated SP 800-57 step |
| 15360-bit | 256 bits | Shows how badly RSA scales |

Those equivalences come from NIST SP 800-57, except the 4,096-bit figure -- a common interpolation, since the standard steps directly from 3,072 bits (128) to 7,680 bits (192). The last row is the quiet punchline: matching a 256-bit symmetric key needs a 15,360-bit RSA modulus, because RSA strength grows only sub-exponentially in key length while the cost of using it grows with the cube [@sp80057]. RSA scales badly, and that alone pushes new systems toward elliptic curves.

Then the cliff. On a large fault-tolerant quantum computer, Shor's algorithm factors in polynomial time -- not faster, but *categorically* faster, collapsing the whole assumption. The only question is engineering, and the estimates are falling fast. In 2019, Gidney and Ekera estimated 20 million noisy qubits and 8 hours to factor a 2,048-bit modulus [@gidney19]; by 2025, Gidney had cut the qubit estimate to under a million [@gidney25].<Sidenote>A 20-fold reduction in the resource estimate in six years, with no fundamental barrier in sight, is precisely the trend that drove NIST to put firm dates -- 2030 and 2035 -- on RSA's retirement in IR 8547. The deadline is set by the slope, not by any single machine.</Sidenote>

Three impossibility results frame the whole subject, each already seen in this article. First, determinism can never be IND-CPA -- that is structural, not fixable, which is why padding must randomize. Second, there is no known standard-model proof of IND-CCA2 for RSA-OAEP under the plain RSA assumption; the guarantee is random-oracle-model only, and even there non-tight [@shoup01], [@fops04]. Third, Coppersmith's barrier $|x| < N^{1/e}$ both enables low-exponent attacks and bounds them, a hard mathematical edge that no parameter choice moves [@coppersmith97].

> **Key idea:** RSA's safety lives in an unproven gap -- breaking it is no harder than factoring, but maybe strictly easier, and factoring is not even proven hard -- and that gap sits on the near side of a quantum cliff with a falling date on it. "Done right" buys you security against every known classical attack. It does not buy you a proof, and it cannot buy you time past Shor.

If the ground under RSA is this uncertain, what exactly is still unsettled -- and which of those open problems can bite you today?

## 10. Open Problems: What Remains Genuinely Unsettled

Some of these are for theorists. Others are live in your dependency tree right now.

- **Is the RSA problem equivalent to factoring?** We have only one direction, RSA $\le$ factoring; the reverse is open, with evidence it may fail [@bv98]. It matters because RSA's whole security story rests on a hardness we have never actually pinned down.
- **A deployed, standard-model IND-CCA2 RSA scheme.** Constructions that avoid the random-oracle model exist on paper, but none is a shipping default; practice sidesteps the gap entirely by using KEM-DEM instead of RSA encryption [@fops04].
- **Constant-time RSA is a perpetually moving target.** Marvin re-found timing leaks in implementations previously believed immune, and only a handful -- such as BearSSL and BoringSSL -- passed its tests; leaks hide in general-purpose bignum code and even in error-logging paths, which is why the CFRG draft concludes the only safe path is to deprecate v1.5 encryption outright rather than keep hardening it [@marvin23], [@cfrgdraft].
- **The long tail of v1.5 encryption.** HSMs, PKCS#11 tokens, S/MIME, and JWE still use it in places that cannot simply be switched off -- exactly where Marvin keeps finding live oracles [@marvin23], [@gorsa].
- **Generation-time entropy and structured primes.** Mining Your Ps and Qs and ROCA are operational failures with no clean universal fix: you cannot prove every device in the world seeded its CSPRNG correctly [@miningpq12], [@roca17].
- **The [post-quantum migration timeline](/blog/the-thirty-year-migration-ships-in-a-pip-install-how-post-qu/).** Key exchange is migrating; signatures are years behind, and harvest-now-decrypt-later keeps the pressure on [@cloudflare24], [@ir8547].

> **Note:** Most of this list is someone else's research agenda. Two entries are not: the v1.5 *encryption* long tail and weak key-generation entropy are the ones most likely to be sitting in your own stack right now, in an HSM integration or an embedded device you inherited. Audit those two first.

Enough theory. Here is the whole argument compressed into rules you can apply on Monday.

## 11. The Practical Guide and the Misuse Catalog

Every rule below is one named break from the catalog, turned inside out. If you remember nothing else, remember the decision tree.

<Mermaid caption="The operational decision tree: what to reach for by task, with the parameters that matter and the migration question at the end. Each leaf is a rule that closes a specific break from the catalog.">
flowchart TD
    START&#123;"What do you need?"&#125; -->|Confidentiality| ENC&#123;"Can you avoid RSA encryption?"&#125;
    START -->|Authenticity| SIG&#123;"New design or legacy mandate?"&#125;
    ENC -->|Yes| KEM[Use ECDH or hybrid X25519 plus ML-KEM-768]
    ENC -->|No, a standard forces RSA| OAEP[RSAES-OAEP, SHA-256, constant-time decode, at least 2048-bit]
    SIG -->|New design| PSS[RSASSA-PSS with SHA-256]
    SIG -->|Legacy mandate| V15[v1.5 signature, verify strictly, no e equals 3 shortcut]
    KEM --> KEYS[Keys: e equals 65537, CSPRNG primes, verify-before-release, blinding]
    OAEP --> KEYS
    PSS --> KEYS
    V15 --> KEYS
    KEYS --> PQ&#123;"Secret must survive past 2030?"&#125;
    PQ -->|Yes| HY[Deploy hybrid post-quantum now]
    PQ -->|No| DONE[Ship it]
</Mermaid>

Spelled out as decision rules:

- **Encryption and key transport.** Prefer ECDH or a KEM, migrating to hybrid X25519 plus ML-KEM-768. If a standard forces RSA encryption, use RSAES-OAEP with SHA-256 and MGF1-SHA-256, a modulus of at least 2,048 bits, and a constant-time decoder with implicit rejection -- never v1.5 encryption [@rfc8017], [@sp80056b]. Never RSA-encrypt a payload; encapsulate a symmetric key and let an AEAD carry the data.
- **Signatures.** Use RSASSA-PSS for new designs [@pss96], [@fips1865]. Use v1.5 signatures only where mandated, and then verify strictly: full parse, re-encode and compare, reject trailing data, no $e = 3$ shortcut [@rfc8017].
- **Keys and parameters.** A 2,048-bit floor, 3,072 or 4,096 bits for long-term secrets; $e = 65537$; independent CSPRNG-drawn primes per key; CRT with verify-before-release; base blinding [@sp80057], [@fips1865].
- **Migration.** Deploy hybrid post-quantum key agreement now, and inventory every RSA usage against the IR 8547 2030 and 2035 clock [@ir8547].

The same rules as a lookup table:

| Task | Use | Key parameters | Because (which break) |
|---|---|---|---|
| Key transport, preferred | ECDH or hybrid X25519 + ML-KEM-768 | Ephemeral keys | Forward secrecy, no oracle, quantum hedge |
| Key transport, if RSA forced | RSAES-OAEP, constant-time decode | SHA-256, MGF1-SHA-256, at least 2048-bit | Bleichenbacher, Manger, Marvin |
| Signature, new design | RSASSA-PSS | SHA-256, random salt | v1.5 hand-wave, e equals 3 forgery |
| Signature, legacy mandate | v1.5, verified strictly | Full parse, reject trailing bytes | e equals 3 forgery, BERserk |
| Key generation | e equals 65537, CSPRNG primes | 2048 floor, 3072+ long-term | Wiener, ROCA, Mining Ps and Qs |
| Private operation | CRT verify-before-release, base blinding | Recompute before output | Bellcore fault, Kocher timing |
| Long-term secrets | Hybrid post-quantum now | Inventory to IR 8547 clock | Shor, harvest-now-decrypt-later |

Now the misuse catalog. Each antipattern maps to exactly one rule it violates -- the findings that recur in real code review:

- **v1.5 encryption "kept for compatibility."** The single most dangerous line in an RSA integration. Violates: retire v1.5 encryption.
- **Non-constant-time OAEP or v1.5 decode.** A decoder that branches or times differently on padding failure. Violates: constant-time, implicit-rejection decoding (Manger, Marvin).
- **Distinct decryption error messages, or branch timing.** Any observable difference between "bad padding" and "other error." Violates: uniform, unobservable failure (Bleichenbacher).
- **Missing CRT verify-before-release.** Signing without recomputing the result first. Violates: verify before release (Bellcore fault).
- **Unblinded exponentiation.** A modexp whose time depends on the secret. Violates: base blinding (Kocher, Brumley-Boneh).
- **An $e = 3$ shortcut in a verifier.** Checking the prefix without rejecting trailing data. Violates: verify strictly (e-equals-3 forgery, BERserk).
- **Textbook RSA copied from a tutorial.** The raw permutation on a message. Violates: never call the raw primitive.
- **RSA-encrypting a large payload.** Treating RSA as a bulk cipher. Violates: encapsulate a key, never encrypt data.
- **Weak, shared, or reused-modulus keys.** Primes drawn from a cold CSPRNG or a structured library. Violates: seed the CSPRNG, draw primes uniformly (Mining Ps and Qs, ROCA).
- **OAEP hash or label mismatch, or MGF1 silently defaulting to SHA-1.** A quiet interoperability and downgrade trap. Violates: pin the hash and MGF explicitly.
- **Treating a "small" side channel as unexploitable.** Marvin demolished that folklore -- a few microseconds recovered keys [@marvin23]. Violates: assume every observable leaks.

<Spoiler kind="solution" label="How to audit your own stack for v1.5 encryption">
Grep for the dangerous entry points and confirm every RSA decryption path uses OAEP with a constant-time decoder:

- Go: search for `DecryptPKCS1v15` and `EncryptPKCS1v15`; move to `DecryptOAEP` and `EncryptOAEP`. The v1.5 decryptor is deprecated for the reason quoted earlier [@gorsa].
- Java: flag `Cipher.getInstance("RSA/ECB/PKCS1Padding")`; require `RSA/ECB/OAEPWithSHA-256AndMGF1Padding`.
- OpenSSL CLI: `openssl pkeyutl -encrypt -pubin -inkey pub.pem -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256`.

If a dependency genuinely still needs v1.5 decryption, confirm it runs a constant-time, implicit-rejection decoder -- OpenSSL 3.2 does so by default [@openssl32].
</Spoiler>

> **Note:** In practice, three violations dominate real audits: RSA v1.5 *encryption* still enabled "for a legacy client," a decryption path that is not verifiably constant-time, and RSA being used to encrypt bulk data instead of a symmetric key. Fix those three and you have closed most of the catalog [@marvin23], [@gorsa], [@openssl32].

Read the whole failure catalog again as this checklist, and one pattern remains.

## 12. Trapdoor, Not Cryptosystem

Return to where we began. The researchers who signed with facebook.com's key never factored its modulus, and neither did anyone in the twenty-five years of breaks between Bleichenbacher and Marvin. The factoring problem stood untouched the whole time. What fell, every single time, was something else: the decryptor's error handling, the signer's fault behaviour, the implementation's clock, or the generator's entropy. The attacker's real move is never to solve the hard math -- it is to turn the receiver's own reaction into the private-key operation.

<PullQuote>
The attacker does not factor the modulus. They turn the decryptor's reaction into the private-key operation -- and "done right" is the discipline of leaving that reaction with nothing to say.
</PullQuote>

That is why "RSA done right" is a stack and not a setting. The right scheme, OAEP to encrypt and PSS for new signatures, does two of the three jobs. The right parameters -- a 2,048-bit floor, $e = 65537$, primes from a real CSPRNG -- keep the trapdoor strong. And the constant-time, fault-checked, blinded implementation does the third job, the one the field kept forgetting: it leaves no observable behaviour that answers the attacker's one question.

Every deployed disaster in this article is a stack with exactly one layer missing. Textbook RSA is broken not because the math is weak but because it is *only* the trapdoor, with none of the layers that make a trapdoor into a cryptosystem.

The forward horizon makes the discipline sharper, not softer. RSA done right is stable against every known classical attack, and it still has an expiration date, because the one gap RSA can never close is the quantum one. The destination is not a better RSA. It is KEM-DEM composition and post-quantum algorithms -- constructions where the public-key operation carries only a uniform random key, and where Shor has no polynomial-time shortcut to wait for.

So ask the diagnostic question one final time, now that it is answerable. When a ciphertext or signature it did not create arrives, what does the receiver reveal about it -- through its answer, its timing, or its faults? Done right, the answer is nothing at all.

<FAQ title="Frequently asked questions">
<FAQItem question="Is RSA broken?">
No, but the word "RSA" hides three different answers. Textbook RSA is broken. PKCS#1 v1.5 *encryption* is dangerous and should be retired [@marvin23]. Done-right RSA -- OAEP or PSS, constant-time, at least 2,048 bits, public exponent 65537 -- is fine against every known classical attack, right up until a large quantum computer exists, which is why you should be planning migration in parallel [@ir8547].
</FAQItem>
<FAQItem question="Can I encrypt a file with RSA?">
No. Encapsulate a fresh random symmetric key with the public key and let an authenticated cipher encrypt the file. RSA-OAEP at 2,048 bits carries only about 190 bytes of plaintext anyway, so it was never meant for bulk data -- it moves keys, not files [@sp80056b].
</FAQItem>
<FAQItem question="OAEP fixed everything, right?">
No. OAEP fixes the *scheme*, not the decoder. James Manger showed that a non-constant-time OAEP decoder re-opens the very same padding oracle, and more cheaply than the original Bleichenbacher attack [@manger01]. The rule is "OAEP AND constant-time decoding," never OAEP alone.
</FAQItem>
<FAQItem question="Are v1.5 signatures broken?">
Not as a scheme -- there is no known attack against the RSASSA-PKCS1-v1_5 signature construction itself [@rfc8017]. What breaks is lax *verifiers*: the 2006 e-equals-3 forgery and the 2014 BERserk bug both forged signatures past sloppy verification, not by breaking the scheme [@cve2006], [@cve2014]. Verify strictly -- parse the entire structure and reject any trailing data.
</FAQItem>
<FAQItem question="Is a small public exponent like 3 safe?">
Only with correct padding and a strict verifier, and it is not worth the risk. A small exponent has repeatedly enabled Hastad's broadcast attack, Coppersmith's low-exponent attacks, and signature forgeries [@hastad88], [@coppersmith97]. Use 65537: it is fast and dodges every low-exponent trap.
</FAQItem>
<FAQItem question="Is 2048 bits enough?">
Yes for today -- a 2,048-bit modulus gives about 112 bits of security [@sp80057]. Use 3,072 bits or more for anything that must stay secret long-term, and start post-quantum planning: NIST deprecates 112-bit RSA after 2030 and disallows it after 2035 [@ir8547].
</FAQItem>
<FAQItem question="Should I move to elliptic curve or post-quantum crypto?">
For most new work, yes. ECDH and Ed25519 give smaller, faster keys with the forward secrecy RSA key transport never had [@rfc8446], and hybrid X25519 plus ML-KEM-768 is already carrying real TLS traffic for the quantum transition [@cloudflare24]. RSA's destination is retirement, not repair.
</FAQItem>
</FAQ>

<StudyGuide slug="rsa-done-right-oaep-pss-bleichenbacher" keyTerms={[
  { term: "Trapdoor permutation", definition: "A one-way function with a secret shortcut. RSA maps x to x-to-the-e modulo N, invertible only by whoever knows the factorization of N. It is a primitive, not a complete cryptosystem." },
  { term: "Malleability", definition: "RSA's multiplicative homomorphism: multiplying a ciphertext by a chosen factor predictably scales the plaintext, letting an attacker transform messages without decrypting. It is the lever behind the padding-oracle attacks." },
  { term: "Padding oracle", definition: "Any observable behaviour (an error, a timing difference, or a fault) that reveals whether a decrypted ciphertext had valid padding, turning a validity check into a decryption oracle." },
  { term: "RSAES-OAEP", definition: "A randomized, all-or-nothing encryption padding applied before the RSA permutation, giving chosen-ciphertext security in the random-oracle model, provided the decoder runs in constant time." },
  { term: "RSASSA-PSS", definition: "A randomized, salted RSA signature encoding with a tight security reduction to the RSA problem, the provable choice for new signature designs." },
  { term: "Implicit rejection", definition: "Returning a deterministic pseudo-random value on a padding failure instead of a distinguishable error, so success and failure are unobservable through content, error type, or timing." },
  { term: "CRT in RSA", definition: "Computing the private operation modulo p and modulo q separately for a roughly fourfold speedup, at the cost of a fault-attack surface unless the result is verified before release." },
  { term: "KEM-DEM", definition: "Transporting a random symmetric key with the public key, then encrypting the data with that key under an authenticated cipher, so no chosen structured plaintext exists for an oracle to grade." },
  { term: "IND-CCA2", definition: "The strongest standard security goal for encryption: even with access to a decryption oracle, an attacker cannot tell which plaintext a ciphertext hides. Padding oracles violate it." }
]} questions={[
  { q: "Why is textbook RSA not a cryptosystem?", a: "It is deterministic, malleable, and structurally leaky for small exponents. It needs padding that adds randomness, adds checkable redundancy, and leaks nothing about whether the check passed." },
  { q: "What single bit did every attack from Bleichenbacher to Marvin leak?", a: "Whether the padding was valid. Only the channel changed, from an error message to a cross-protocol zombie to a TCP quirk to pure timing." },
  { q: "Why is OAEP necessary but not sufficient?", a: "OAEP secures the scheme, but Manger showed that a non-constant-time decoder re-opens the same oracle. Security is a property of the scheme and its implementation together." },
  { q: "What is the one split you must never blur?", a: "v1.5 encryption is dangerous and should be retired, while v1.5 signatures are unbroken as a scheme and still dominant. Verify the signatures strictly." },
  { q: "Why does done-right RSA still have an expiration date?", a: "There is no proof RSA is secure, and Shor's algorithm factors in polynomial time on a quantum computer, so the destination is KEM-DEM plus post-quantum cryptography." }
]} />