How RSA Breaks in Real Life: ROCA, Bleichenbacher's Ghosts, FREAK, and the Keys That Shared a Prime

1. No One Has Ever Factored a Strong RSA Key. Your RSA Keys Broke Anyway.#

The largest RSA key ever factored in public is a 250-digit, 829-bit challenge number, and cracking it in 2020 took the world's best number theorists about 2,700 core-years ^[1]. No strong, correctly generated RSA key protecting real traffic has ever been factored at all. Hold that fact still for a moment, because the next one refuses to sit beside it.

In the same era, Estonian national ID cards were forgeable ^[4], roughly a third of all HTTPS was decryptable ^[6], hundreds of thousands of embedded private keys were recoverable ^[3], and export-grade sessions were silently man-in-the-middled ^[8]. Every one of those was an RSA break. Not one of them was a factored strong modulus. So how does a factoring problem nobody can beat on a strong key keep producing forged signatures, decrypted sessions, and stolen private keys?

The resolution is the whole argument of this article, and it belongs before the evidence: none of these broke strong RSA. RSA is a trapdoor permutation, and its single security promise is narrow -- that factoring a strong $n = p \cdot q$ is hard ^[10]. That promise silently depends on three things the mathematics does not control: where the primes came from, how the decrypting party validates padding, and which key strength a protocol will accept. It was those three deployment-owned layers, never the factoring problem, that gave way.

So carry one diagnostic question through everything that follows. When an RSA key, session, or signature falls, do not ask "did someone factor the modulus?" Ask instead: which layer the math depends on but does not control gave way -- the primes, the padding, or the negotiation? Every break in this article is a non-empty answer to that question, and you will learn to drop ROCA, DROWN, FREAK, and tomorrow's incident into it on sight.

To break RSA in the field, you never factor a strong modulus. You take the weak one the deployment already handed you, or the oracle it left open -- and the factoring problem on a strong key stands untouched.

The paradox even has a face. The researcher Nadia Heninger appears at both poles of this story: she recovered weak keys in the field, and she co-holds the public record for factoring a strong one ^{[3, 1]}. One person, both ends of the argument -- the weak keys that fall in an afternoon and the strong one that costs millennia of compute.

This is Part 3 of How It Breaks in Real Life, a series with one recurring thesis: the primitive's mathematics almost never caused the break; the deployment did. RSA is one of its cleanest cases. It has a companion piece, How RSA Would Break: Why Factoring Is the Slow Path and Coppersmith Is the Fast One, which handles the would-break-in-theory math: the Number Field Sieve, Coppersmith's lattices, and Shor's algorithm. This article is the did-break-in-the-field frame.

If no strong modulus was ever factored and the factoring problem never moved, then everything that broke was built around it. To see how "unfactored modulus" and "recovered key" can both be true at once, we have to go back to what RSA actually promises -- and, more importantly, what it silently assumes.

2. What RSA Actually Assumes#

In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman handed the world its first practical public-key cryptosystem: a public modulus $n = p \cdot q$, a public exponent $e$, a private exponent $d$, and a security argument resting on the hardness of factoring $n$ ^[10]. That assumption is exactly why the core problem has held for five decades. It is also exactly why, when RSA breaks in the field, the fault lies somewhere else. Being a trapdoor permutation made RSA a primitive. It did not make it a safe deployment.

Start with the single most important distinction in this article. RSA-the-primitive is a keyed permutation over the integers modulo $n$, and its security promise is narrow and conditional. Here is the precise version, because the imprecise version is the source of half the confusion in the subject.

Read that twice, because the direction matters. Factoring is sufficient to break RSA: if you can factor $n$, you win. But nobody has proved the reverse, that breaking RSA requires factoring. The RSA problem might, in principle, be easier than factoring; we do not know. What we do know is that the best attack anyone has found on the primitive is still factoring, and factoring a strong modulus is where the wall stands.

Notice the quiet consequence: the field never even needed that unproven shortcut. Every deployed break in this article bypassed both directions entirely. No one factored a strong key, and no one found a clever inversion either. They walked around the math.

Because the guarantee is only about the difficulty of factoring, it says nothing about three other things:

1. Where $p$ and $q$ come from. They must be large, independent, and drawn from real entropy.
2. How the raw permutation is wrapped. Textbook RSA is deterministic and malleable, so it must be padded before it is used.
3. Which key strength a protocol will accept. A 512-bit option nobody wants is still a 512-bit option somebody can force.

Those three silences are the structure of the whole article. Picture them as a map: the factoring-hardness assumption sits at the center, and three deployment-owned dependencies surround it. Each is an independent surface an attacker can reach without ever touching the factoring problem.

flowchart TD
A["The one RSA guarantee: factoring a strong modulus is hard"]
A --> B["Layer 1: Key generation, where the primes come from"]
A --> C["Layer 2: Padding validation, how decryption is checked"]
A --> D["Layer 3: Negotiation, which key strength is accepted"]
B --> E["Each layer is an independent failure surface reached without factoring"]
C --> E
D --> E

Before we watch each dependency fail, three guardrails, because the argument is easy to overstate in exactly three ways.

The series this article belongs to lists a familiar set of culprits: the RNG, the nonce, the padding, the downgrade. RSA answers to most of them, but not the nonce. RSA signing has no secret per-signature nonce whose reuse leaks the key. The nonce-reuse break -- the reused $k$ behind the 2010 PlayStation 3 and 2013 Android SecureRandom key recoveries ^{[12, 13, 14]} -- is an (EC)DSA phenomenon, a different primitive. There is no "RSA nonce-reuse break"; when you see one described, it is really an ECDSA story, and it is told in its own article. Two of the three real culprits are RSA's, and both are downstream of the map above.

One narrow assumption, three silent dependencies, none of them the factoring problem. Before we watch each dependency break in the field, we need to see the contracts up close: what real entropy actually buys, why a padding check is a loaded gun, and why a 512-bit option nobody uses is still a live weapon.

3. Three Contracts the Math Cannot Enforce#

Every field break in this article is the violation of one specific promise -- a promise the RSA math assumes but has no way to enforce. There are exactly three, one per layer of the map, and once you can see the contract, the break becomes obvious. Here they are, side by side.

The key-generation contract: the primes must be unpredictable and never shared. Two "random" primes are only as unpredictable as the generator that produced them. Starve that generator of entropy, cripple it with a bug, or bias its structure, and the primes come out predictable, colliding, or specially formed -- while every later step still looks textbook-correct.

The hidden assumption behind this contract is quiet but total: enough real entropy reached key generation, and no two keys ever drew the same prime.

The padding contract: never reveal whether padding was valid. Textbook RSA is deterministic and malleable, so a real system must wrap the message before exponentiating. For twenty-five years the near-universal wrapper has been PKCS#1 v1.5.

Here is the conceptual pivot the whole subject turns on. In 1998, Daniel Bleichenbacher noticed that the padding check itself is a leak ^[5]. A server that decrypts a ciphertext and then reveals -- by error, timeout, or timing -- whether the result began with the required 00 02 bytes has answered a yes/no question about the plaintext. One bit does not sound like much. But raw RSA is malleable, so the attacker can ask the question about a plaintext of their choosing.

Because raw RSA is malleable, an attacker can multiply a ciphertext $c$ by $s^e$ to form $c' = c \cdot s^e \bmod n$, which decrypts to $m \cdot s \bmod n$. A server that reveals whether each such $c'$ was validly padded answers one yes/no question per query about where $m$ lies. About $10^6$ adaptive queries narrow $m$ to a single value: a session decrypted, with no private key recovered and nothing factored. This one mechanic drives Bleichenbacher, DROWN, and ROBOT.

You can feel the mechanic in miniature. The toy below uses an idealized one-bit oracle -- it reports only whether the decryption falls in the bottom half of the range -- and binary-searches the plaintext out of the server without ever touching the key. The oracle recovers no private key and factors nothing; it turns the server into a one-session decryption (or one-message signing) oracle, and the modulus is untouched afterward. Keep two things distinct: the attack is on PKCS#1 v1.5 encryption, and v1.5 signatures are a separate scheme it does not break.

function modpow(b, e, n){ b %= n; let r = 1n; while (e > 0n){ if (e & 1n) r = (r*b)%n; b = (b*b)%n; e >>= 1n; } return r; }
const p = 61n, q = 53n, n = p*q;          // toy modulus n = 3233
const e = 17n, d = 2753n;                 // public e, private d
const m = 65n;                            // the secret plaintext
const c = modpow(m, e, n);                // the ciphertext the attacker holds

// The ONLY leak: does the decryption land in the bottom half of [0, n)?
// An idealized magnitude / MSB oracle -- one bit per query.
const oracle = (ct) => modpow(ct, d, n) < n / 2n;

const enc2 = modpow(2n, e, n);            // multiplier that doubles the plaintext (malleability)
const K = 14n, SCALE = 1n << K;
let loS = 0n, hiS = n * SCALE, ct = c;
for (let i = 0n; i < K; i++){
const mid = (loS + hiS) / 2n;
if (oracle(ct)) hiS = mid; else loS = mid;   // read one bit, halve the interval
ct = (ct * enc2) % n;                          // next query sees 2*m, 4*m, ... mod n
}
console.log('recovered plaintext ->', (hiS / SCALE).toString());   // -> 65

// The real PKCS#1 v1.5 oracle asks a different one-bit question: do the top bytes
// equal 00 02? That narrows m onto a union of intervals 2B <= m < 3B rather than a
// < n/2 half -- same principle, different bit. This < n/2 magnitude test is the same
// family of magnitude / most-significant-byte leak Manger's 2001 attack exploits
// against OAEP -- but his oracle tests x < B = 2^(8(k-1)) (whether the leading octet
// is zero), not x < n/2.

The negotiation contract: never accept a deliberately crippled key or a dead protocol. The math cannot see which key strength a handshake settled on, nor whether the protocol carrying it was retired a decade ago.

The assumption here is that only a party that wants export-grade crypto, or wants SSLv2, will ever get it.

Three contracts, each reasonable, each unenforced by the math. The factoring problem cannot tell whether you fed it a shared prime, a leaky padding check, or a forced 512-bit key. Which raises the only question that matters: on real smartcards and real servers, do these contracts actually hold? They do not. Here is where, when, and how each one broke.

4. Three Deployment Failures, Three Layers, One Pattern#

The comfortable belief is "we use RSA-2048, so our keys, sessions, and signatures are safe." What follows are seven independent refutations of that inference: seven deployed field breaks, grouped into three pillars, one per layer the math depends on but does not control. Each pillar runs in chronological order, but read it as a failure catalog, not a lineage of improving designs. They are three simultaneous layers every real deployment must secure at once, and the chronology is simply the attacker's frontier moving from one unmet obligation to the next as each was patched.

Read the two rightmost data columns as the argument in a grid: every row that ends in a factored modulus is a weak modulus, and every row with a strong modulus recovers no key and factors nothing. The one strong modulus ever factored, RSA-250, is a challenge number that never protected anything.

flowchart LR
Y1998["1998 Bleichenbacher, padding"] --> Y2008["2008 Debian RNG, key generation"]
Y2008 --> Y2012["2012 shared primes, key generation"]
Y2012 --> Y2015["2015 FREAK, negotiation"]
Y2015 --> Y2016["2016 DROWN via SSLv2, padding"]
Y2016 --> Y2017["2017 ROCA structure, and ROBOT padding"]
Y2017 --> Y2020["2020 RSA-250 ceiling, a challenge number"]

Pillar 1: The primes were weak before the math began#

All three key-generation breaks share one shape: generation produced a weak modulus, and then -- only then -- arithmetic finished it off. A strong modulus is on none of these paths.

flowchart TD
R["Crippled RNG, Debian 2008"] --> W["Weak modulus"]
B["Starved boot entropy"] --> SP["Two keys share a prime, 2012"]
SP --> G["One gcd recovers the shared prime"]
G --> W
ST["Structured primes, Infineon RSALib, 2017"] --> CO["Coppersmith lattice factors the key"]
CO --> W
W --> F["The math finishes the job, and a strong modulus is on no path here"]

Debian OpenSSL, defect 2006, disclosed 2008. A well-meaning Debian patch, written to silence a Valgrind warning about uninitialized memory, removed most of the entropy feeding OpenSSL's PRNG. The change shipped in openssl 0.9.8c-1, and for nearly two years the effective seed collapsed to essentially the process ID, about 32,767 possibilities ^{[2, 19]}. Keys stopped being unpredictable and became enumerable: an attacker could precompute the whole set. No factoring, no oracle, just a keyspace small enough to list. The defect was uploaded as openssl 0.9.8c-1 on 17 September 2006 and disclosed on 13 May 2008 by Luciano Bello ^[20]. Field measurement came from Yilek and colleagues at IMC 2009, who watched the fix propagate: 751 vulnerable certificates observed, and a meaningful fraction still vulnerable roughly six months later ^[21].

Mining Your Ps and Qs, 2012. Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman scanned the entire IPv4 Internet's TLS and SSH hosts and found something worse than predictability. They found collision. Headless and embedded devices, generating keys at first boot with almost no entropy, sometimes produced moduli that shared a single prime with an unrelated device. A shared prime is fatal, because $\gcd(n_1, n_2) = p$ factors both moduli in the time of one gcd.

They measured that 5.57% of TLS hosts shared keys, and they remotely recovered the RSA private keys of 0.50% of all TLS hosts through common factors, notifying 54 manufacturers ^[3]. An independent study the same year, titled "Ron was wrong, Whit is right," found the same collisions in a different dataset and ruled out a single-vendor fluke ^[22].

You can watch both keys fall from one gcd:

const gcd = (a, b) => { while (b) { [a, b] = [b, a % b]; } return a; };
// Two RSA moduli from two different devices. Neither looks weak on its own.
// (Shrunk stand-ins; real moduli are hundreds of digits and the gcd costs the same.)
const n1 = 63900000000000000000000000000000000000000000002625100000000000000000000000000000000000000000026931n;
const n2 = 74700000000000000000000000000000000000000000003196300000000000000000000000000000000000000000034189n;
const p = gcd(n1, n2);              // one Euclidean gcd -- the entire attack
const q1 = n1 / p, q2 = n2 / p;
console.log('shared prime p =', p.toString());
console.log('device 1 recovered:', p * q1 === n1);
console.log('device 2 recovered:', p * q2 === n2);
console.log('Both private keys recovered from one gcd. Key size was irrelevant.');

ROCA, 2017. The first two breaks needed bad randomness. ROCA needed none. Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, and Vashek Matyas showed that Infineon's RSALib built its primes in a speed-optimizing but constrained form, $p = k \cdot M + (65537^a \bmod M)$, detectable from the public key alone and factorable by a Coppersmith-style lattice far faster than general factoring ^{[23, 4, 24]}. The randomness was fine; the structure was the flaw, so every key the chip ever generated was affected. The first author is Matus Nemec (not "Miroslav"), and the fifth is Vashek, or Vaclav, Matyas (not "Vladimir"). The affected products were the YubiKey 4 (not the YubiKey 5), Estonian national eID cards, and Infineon-based TPMs. Because the attack keys off structure rather than entropy, it is RNG-independent ^[4].

The cost, from the authors themselves: a 1024-bit key fell in under three CPU-months, about $76 on AWS; a 2048-bit key in under 100 CPU-years, about $40,000; and roughly 760,000 confirmed-vulnerable keys were in the field ^[4]. Notice what "2048-bit" bought here: nothing. The number that mattered was not the key size but the structure of the primes.

Pillar 2: The padding check was an oracle#

Now the padding pivot from Section 3, shown surviving twenty-five years of patches. Three incidents, one bug, reappearing at a new layer each time an inner defense hardened.

sequenceDiagram
participant A as Attacker
participant S as Server
Note over S: Holds the private key, reveals only whether padding was valid
A->>S: Submit c times s^e mod n
S->>A: One bit, padding valid or invalid
Note over A,S: Each bit narrows the interval that must contain m
A->>S: Submit the next adaptively chosen ciphertext
S->>A: One more bit
Note over A,S: After about a million queries m is pinned, key never touched

Bleichenbacher, 1998. The origin. A PKCS#1 v1.5 encryption endpoint that reveals whether a decryption was well-padded becomes an adaptive chosen-ciphertext decryption oracle, and about $10^6$ queries decrypt a captured session. The private key is never recovered and nothing is factored; the attacker simply borrows the server's decryption ability for one message ^[5].

DROWN, 2016. Nimrod Aviram and fourteen coauthors, Heninger and Halderman among them, showed the 1998 oracle had a door nobody had closed: a forgotten SSLv2 endpoint. If a modern TLS server shared its RSA key with an old SSLv2 server -- common, because operators reused certificates -- an attacker could run a cross-protocol Bleichenbacher attack through the SSLv2 side, whose export ciphers and an OpenSSL bug made a "special" variant cheap.

At disclosure in March 2016, 33% of all HTTPS servers, 25% of the top million, and 22% of browser-trusted sites were vulnerable; it fell to about 1.2% by 2019 ^[6]. DROWN is not ROBOT. DROWN (2016) reached modern TLS cross-protocol, through a shared-key SSLv2 endpoint. ROBOT (disclosed December 2017, published at USENIX Security 2018) found the same oracle still answering directly on modern TLS stacks. Different years, different vector, the same 1998 bug ^{[6, 7]}.

ROBOT, 2017. Hanno Bock, Juraj Somorovsky, and Craig Young gave the bug its name, Return Of Bleichenbacher's Oracle Threat, and showed the nineteen-year-old oracle still live across nine vendors, including F5, Citrix, Radware, Palo Alto Networks, IBM, and Cisco, with vulnerable subdomains on 27 of the top 100 domains, Facebook and PayPal among them ^{[26, 27, 7]}. To prove the point without crossing a line, the team used the oracle to sign a message with Facebook's private key, and still never recovered that key.

ROBOT "allows performing RSA decryption and signing operations with the private key of a TLS server" -- and yet recovers no private key at all. Its own recommendation is the entire fix thesis in one line: disable RSA encryption cipher suites entirely.

All three padding incidents carry the sharpest version of the thesis: the attacker uses the private key without ever holding it, and the modulus is untouched at the end. The remedy was never a bigger key. It was uniform, constant-time error handling and, ultimately, retiring RSA encryption in favor of OAEP or forward-secret key exchange, exactly as ROBOT advised.

Pillar 3: The negotiation forced a crippled key#

FREAK, 2015. Benjamin Beurdouche and seven coauthors found a TLS state-machine flaw with a nasty consequence. A man-in-the-middle could force a handshake down to 512-bit RSA_EXPORT even when neither the client nor the server wanted export-grade crypto. And 512-bit RSA has been factorable since RSA-155 fell in 1999, so the attacker factors the downgraded modulus in hours for about $100 on cloud compute, then impersonates or decrypts the session. At disclosure, 36.7% of browser-trusted HTTPS servers still accepted export RSA ^{[18, 28, 8, 29, 15]}.

sequenceDiagram
participant C as Client
participant M as MITM
participant S as Server
C->>M: ClientHello, wants strong RSA
M->>S: Forward it but ask for RSA_EXPORT
S->>M: ServerKeyExchange with a 512-bit export key
M->>C: Inject the 512-bit key as if it were normal
Note over M: Factor the 512-bit modulus in hours for about 100 dollars
M->>C: Impersonate or decrypt the session

The factoring step is feasible here only because a downgrade plus 1990s export policy forced a deliberately weak key. The math finished a job the deployment set up, and it could not have touched a 2048-bit key the same way. The academic paper, "A Messy State of the Union," has eight authors; never attribute FREAK to a single name ^[18]. The freakattack.com credit to Karthikeyan Bhargavan and the miTLS team, with tracking by the University of Michigan, is a separate and separately-true fact ^[8]. The fix was, again, a deployment change, not a cryptographic one: remove export ciphers, disable SSLv2, add downgrade protection, and ultimately TLS 1.3 dropping RSA key exchange entirely.

Three layers, seven field breaks, one shape. Every time, a contract the RSA math depends on but does not control was violated, real keys or sessions or signatures fell, and the factoring problem on a strong modulus did not move. Seen one at a time, each looks like a smartcard bug, a TLS bug, a legacy-protocol bug. Seen together, they are a single pattern, and the pattern is the whole point.

5. Every Fix Changed How RSA Is Generated, Used, or Negotiated -- Never RSA#

Stop treating the seven incidents as separate. Line them up and one realization collapses the subject: every field break attacked a layer the math depends on but does not control -- entropy, then the padding check, then negotiated strength -- and every fix changed how RSA is generated, used, or negotiated, never the factoring problem.

The breakthrough here is not a eureka discovery. It is an engineering discipline, visible only because the same shape repeats across a twenty-year drumbeat from 1998 to 2020. Map each fix to its layer and watch none of them touch the primitive:

• Key generation was answered with validated high-entropy generation plus post-hoc structure and shared-factor testing: FIPS 186-5, batch-GCD scanners, and the ROCA detector ^{[30, 3, 4]}.
• Padding was answered with OAEP, uniform constant-time error handling, and, most durably, structurally retiring RSA encryption ^{[31, 7]}.
• Negotiation was answered by removing export and SSLv2, adding downgrade protection, and TLS 1.3 deleting static RSA key exchange outright ^[9].

It is worth dwelling on the padding fix that failed, because its failure is the most instructive event in the whole story. The canonical countermeasure was not hand-waving. TLS 1.2 specified it precisely: on any decryption or padding failure, the server does not signal an error at all. It substitutes a randomly generated premaster secret and proceeds as if nothing were wrong, so the handshake fails uniformly and only later, at the Finished-message MAC, with no observable difference between valid and invalid padding ^[32]. The RFC even cites Bleichenbacher and the Klima-Pokorny-Rosa version oracle by name.

It removed exactly one channel, the explicit error message. And the same one bit resurfaced through three more: a forgotten SSLv2 sibling (DROWN), implementation quirks like TCP resets and alert timing (ROBOT), and decryption timing (Marvin) ^{[6, 7, 33]}.

That is the deep lesson. A scheme whose validity is observable cannot be patched uniformly safe; it can only be structurally replaced. The field kept relearning Bleichenbacher's single lesson at a new layer each time an inner defense hardened.

Every field break attacked a layer the math depends on but does not control, and every remedy -- validated entropy and structure tests, OAEP and PSS with uniform errors, dead export and SSLv2, TLS 1.3 -- hardened a deployment obligation. The factoring problem is the fixed point around which everything else evolved. Soundness requires the weakest of three deployment layers to hold, and hardening any one of them is an exercise in usage, not cryptanalysis.

If every fix is "generate, use, or negotiate RSA correctly," then the state of the art is simply the catalog of what "correctly" means at each layer in 2026 -- and where, even now, correct-by-the-book still is not enough.

6. What Correct RSA Deployment Looks Like in 2026#

The modern answer is unglamorous, and that is the point: be sound at all three layers at once, because validated key generation does nothing for a leaky padding check, and a perfect padding scheme does nothing for a forced 512-bit downgrade.

Key generation. Use validated, high-entropy, structure-checked generation per FIPS 186-5, published February 2023 ^[30]. Guarantee real entropy before the first key is generated, use 2048-bit or larger moduli, and run continuous fleet hygiene: batch-GCD across your own keys and the ROCA detector against certified black boxes ^{[3, 4]}. Generation and measurement are complementary -- measurement catches what generation missed.

Padding and encryption. Use RSA-OAEP for encryption and RSA-PSS for signatures, both from RFC 8017, with constant-time, uniform-error decryption; better still, avoid RSA key transport altogether ^[31].

The one-line takeaway is worth memorizing: OAEP done wrong is Bleichenbacher wearing different padding. Even the fix is a deployment obligation. Marvin (2023, Hubert Kario at Red Hat) is a modern timing revival of the v1.5 oracle across many libraries. Its existence and authorship are verified, but keep it at mention weight pending venue and peer-review confirmation, rather than leaning on it as a load-bearing result ^{[33, 35]}.

Negotiation. Use TLS 1.3, which removes static RSA key exchange entirely: all key exchange is forward-secret (EC)DHE, and RSA survives only as a signature algorithm, with the rationale spelled out in the RFC's Appendix E.8, "Attacks on Static RSA" ^[9]. SSLv2, export ciphers, and RSA_EXPORT are dead. Forward secrecy is the structural win here: with no RSA key transport on the wire, there is no v1.5 decryption for an oracle to be about. The deployed stacks already reflect this -- mainstream TLS libraries now default to TLS 1.3, and some, like rustls, never implemented the TLS_RSA_* transport suites at all ^[36].

"Validate generation, use OAEP and PSS, drop RSA key transport" is the whole answer for greenfield code. But engineers inherit constraints -- a device that must self-generate keys, a peer that only speaks v1.5, a fleet already in the field -- so the real question is not "what is best" but "what are my options at each layer, ranked, and exactly when does each apply?"

7. Competing Approaches: How the Field Closes Each Gap#

For each of the three loci, the honest picture is competing options with real trade-offs, not a single winner.

Key generation. Three approaches coexist. A hardware RNG with guaranteed entropy at boot prevents the Debian and shared-prime failures at the source. Derandomized key generation -- deriving the primes from a single strong seed -- removes the runtime-entropy dependency entirely, at the cost of trusting that seed. And post-hoc structure and shared-factor testing (batch-GCD scanners, the ROCA detector) catches what generation missed ^{[3, 4, 30]}. Measurement is the backstop for generation: ROCA and Mining Your Ps and Qs were both discovered by scanning the field, not by auditing source.

Padding. Three options, chosen by how much legacy you must carry. Fix the scheme with OAEP -- but recall Manger, that it is only misuse-safe with one constant-time generic error ^[34]. Or keep v1.5 for compatibility and harden the implementation toward a uniform error, the RFC 5246 random-premaster substitution -- a twenty-five-year losing battle across error text, protocol siblings, implementation quirks, and timing ^[32]. Or abandon RSA encryption for forward-secret (EC)DHE. Different deployments sit under different compatibility constraints, so all three survive in the field ^{[31, 7]}.

Downgrade. Two options. TLS 1.3, with built-in downgrade protection and outright protocol and algorithm retirement, is the durable answer. For stacks that cannot move yet, configuration hardening -- TLS_FALLBACK_SCSV, disabling export ciphers and SSLv2 -- is the interim one ^{[9, 6]}.

Notice the convergence. The durable answer to both Pillar 2 and Pillar 3 is the same move: do not do RSA key transport. The clean surviving split is that RSA-for-signatures (PSS) stays first-class while RSA-for-encryption is retired.

Every one of these options changes how RSA is generated, used, or negotiated, or drops RSA key transport entirely, and each buys its safety with a specific cost -- a scan, a migration, a compatibility break, a forward-secret handshake. Which means the honest way to close the technical arc is to ask what is provably true on both sides: how little the attacker needs, and how much the defender can actually guarantee.

8. What Is Provably True on Both Sides#

The thesis has two sides, and each has its own frontier. The surprise is the asymmetry: the math side is a slow, honest, well-mapped concession, and all the operationally relevant limits live in the deployment.

The math side, the honest concession. Factoring is real but slow. The Number Field Sieve runs in heuristic sub-exponential time $L_N[1/3, (64/9)^{1/3}]$, with $(64/9)^{1/3} \approx 1.923$ ^[37], and the public record has crept forward for two decades.

Every row is a challenge number from the old RSA Factoring Challenge, a public target list RSA Laboratories once published ^[38], and none was ever a deployed key ^{[15, 16, 39, 37, 1]}. 512-bit is hours, which is exactly why FREAK works; 2048-bit is out of classical reach; and Shor's algorithm collapses all of it on a quantum computer -- a story the companion How RSA Would Break owns. Read the rightmost column top to bottom: it says Never at every row, because no strong, correctly generated, deployed modulus has ever been factored in the field. RSA-250's roughly 2700 core-years split into about 2450 for sieving and 250 for the matrix step, run on Intel Xeon Gold 6130 cores with CADO-NFS. It is a 250-digit, 829-bit challenge number, and it never protected a deployed system ^[1].

The Heninger through-line closes here. The researcher who recovered weak keys by the thousand in Pillar 1 co-holds this record -- the slow, honest way a strong key falls ^[1]. That is the entire weak-versus-strong distinction compressed into one career. And note the theory is not even settled in the defender's favor: there is no proof that factoring requires super-polynomial time, and the RSA-problem-versus-factoring equivalence is itself open ^[11]. Two-plus decades of open cryptanalysis is an empirical floor, not a theorem -- and it never once mattered in the field.

The deployment side, where the real limits live. Here the limits are provable-in-practice, and none is about a strong modulus's strength.

Three boundaries, stated outright. First, a padding oracle needs no factoring: its query count is bounded below only by the roughly one-bit-per-conforming-reply information rate, so decryption is many queries but always polynomial, and you cannot make an observable-validity scheme require exponentially many queries ^{[5, 34]}. Second, a shared prime is a single gcd away and a structured prime a Coppersmith lattice away -- quasi-linear or polynomial, regardless of key size ^{[3, 4]}. Third, certification is not structural testing -- the ROCA lesson from Pillar 1, where FIPS 140-2 and CC EAL5+ chips shipped structurally factorable keys for years ^[4].

The math side is a slow, mapped concession -- an 829-bit public ceiling, and no strong deployed key ever factored. The deployment side holds the real limits: a padding oracle needs no factoring, a shared prime is one gcd, a structured prime one lattice, a downgrade one forced 512-bit key -- all independent of key size. "Strong-modulus-secure" and "system-secure" are different claims, and the gap between them is inherent, not accidental.

If the math side is a slow, mapped concession and the deployment side has hard, polynomial-cost limits, the practical frontier is obvious: it is wherever those deployment limits are still being hit in the wild. That is not a solved problem. It is an active one.

9. Where RSA Still Breaks in the Field#

The math side is a slow, honest concession. The deployment side is not closed. Here are the places the same three-pillar pattern is still live, each an operational frontier, each consistent with the thesis that the weak link is a layer the math depends on, never the factoring problem.

Entropy on embedded, first-boot, and cloned systems (Pillar 1). The exact Debian and shared-prime gap, revived by cloud VM cloning and container images that reproduce identical state at key-generation time ^[40]. The best partial answer is FIPS 186-5 generation plus fleet batch-GCD, but coverage of cloned and containerized keys is incomplete ^{[3, 30]}.

The PKCS#1 v1.5 long tail and timing oracles (Pillar 2). v1.5 is still specified and everywhere. Marvin (2023) showed the timing axis is still open across many libraries, tied to the working impossibility result that an observable-validity scheme cannot be patched uniformly safe, only structurally replaced ^{[33, 35, 7]}.

Protocol and algorithm-retirement lag (Pillar 3). How does a dead algorithm -- SSLv2, export RSA, v1.5 -- stay live for a decade or more? DROWN fell from 33% in 2016 to about 1.2% by 2019, and FREAK from 36.7% toward the low single digits: large but incomplete progress ^{[6, 8]}. This is a socio-technical problem, not a cryptanalytic one.

The next ROCA-class library (Pillar 1). Detecting a structurally biased generator inside certified closed hardware, before it ships millions of keys. The ROCA detector is signature-based, so a genuinely new structure would evade it ^[4].

Post-quantum signature migration ahead of Shor. This is the one future break that is the math. Key exchange is already forward-secret, but signatures need proactive migration; the mechanics belong to the post-quantum and would-break siblings.

One boundary is worth fencing so it is never miscounted as a field incident. ※ Wiener's small-$d$ attack recovers a too-small private exponent $d < \tfrac{1}{3} n^{1/4}$ from the public key by continued fractions (1990) ^[41], and Hastad's low-exponent broadcast recovers the same unpadded low-$e$ message sent to $e$ recipients via CRT and an integer $e$-th root (1988) ^[42]. Both are real, but they are parameter-choice, theoretical breaks -- the canonical argument for randomized padding -- not documented field incidents. They belong to How RSA Would Break. Parameter-choice attacks on deliberately bad exponents are a different genre from the deployment failures cataloged here.

Every open problem here is the same sentence in new clothes: a contract the RSA math depends on is hard to keep in the real world. Which means the practical guide writes itself. It is the thesis made operational, each rule routed to the incident it prevents.

10. What to Do on Monday#

Everything above collapses into a short decision procedure and a shorter list of nevers, each rule tied to the incident it prevents.

flowchart TD
E{"Real entropy before keygen?"} -->|No| E1["Stop. Seed first. Never generate at unseeded boot."]
E -->|Yes| K["FIPS 186-5 generation, 2048-bit or larger"]
K --> SCAN{"Batch-GCD and ROCA detector"}
SCAN -->|Flagged| REV["Regenerate and revoke"]
SCAN -->|Clean| ENC{"Need RSA encryption?"}
ENC -->|Yes| OAEP["OAEP, one constant-time generic error"]
ENC -->|No| DHE["Prefer (EC)DHE, TLS 1.3"]
OAEP --> SIG["Signatures: RSA-PSS, plan PQC"]
DHE --> SIG
SIG --> NEG["Disable SSLv2, export, and RSA_EXPORT, add downgrade protection"]

Key generation. Guarantee real entropy before the first key is generated; follow FIPS 186-5; never generate keys at unseeded first boot; use a 2048-bit minimum with validated generation; and run batch-GCD and the ROCA detector across your keys and CT logs, regenerating or revoking anything flagged. This prevents Debian enumeration, shared primes, and ROCA ^{[30, 3, 4]}.

Padding and encryption. Never use raw PKCS#1 v1.5. If you must do RSA encryption, use OAEP with constant-time, uniform-error handling -- one generic error, per Manger; better still, prefer (EC)DHE forward secrecy and drop RSA key transport, which TLS 1.3 does for you. This prevents Bleichenbacher, DROWN, ROBOT, and Marvin ^{[31, 34, 9]}.

Signatures. Use RSA-PSS, which is not what the oracles break, and plan the post-quantum signature migration ahead of Shor ^[31].

Negotiation. Disable SSLv2, export ciphers, and RSA_EXPORT; enable downgrade protection; prefer TLS 1.3 over 1.2. This prevents FREAK and DROWN's SSLv2 channel ^{[9, 6]}.

The batch-GCD check is not just an attacker's tool; it is your fleet audit. Run it against your own moduli:

const gcd = (a, b) => { while (b) { [a, b] = [b, a % b]; } return a; };
// Public moduli scraped from your own devices or CT logs.
const fleet = {
'host-a': 63900000000000000000000000000000000000000000002625100000000000000000000000000000000000000000026931n,
'host-b': 74700000000000000000000000000000000000000000003196300000000000000000000000000000000000000000034189n,
'host-c': 35510000000000000000000000000000000000000000001968800000000000000000000000000000000000000000010257n,
'host-d': 18130000000000000000000000000000000000000000001447800000000000000000000000000000000000000000026649n,
};
const names = Object.keys(fleet);
let flagged = 0;
for (let i = 0; i < names.length; i++) {
for (let j = i + 1; j < names.length; j++) {
  const g = gcd(fleet[names[i]], fleet[names[j]]);
  if (g > 1n) {
    flagged++;
    console.log('WEAK PAIR:', names[i], '&', names[j], '-> shared factor', g.toString());
  }
}
}
console.log(flagged ? ('Regenerate and revoke ' + flagged + ' compromised pair(s).') : 'No shared factors found.');

The checklist is short because the lesson is one sentence. Before restating it, let us clear the handful of confident, wrong sentences that keep these bugs alive in design meetings.

11. Misconceptions, Precisely Corrected#

The paradox survives mostly because a few plausible, wrong statements keep getting repeated. Here they are, corrected, each answer tied back to a catalog entry and the three-pillar thesis.

Every correction points at the same root: the factoring problem was never the weak link. Time to say the sentence the whole article was built to earn.

To Break RSA in the Field, You Never Factor a Strong Modulus#

Return to the opening paradox, now resolved. The public factoring ceiling is an 829-bit challenge number that cost about 2,700 core-years, and no strong deployed key has ever fallen to it ^[1]. And yet national ID cards were forgeable, a third of HTTPS was decryptable, embedded keys were recoverable, and sessions were man-in-the-middled -- because every one of those breaks happened at a layer the factoring problem knows nothing about.

The primes were weak before the math began: Debian, shared primes, ROCA. The padding check was an oracle: Bleichenbacher, DROWN, ROBOT. The negotiation forced a crippled key: FREAK. Three layers, seven deployed field breaks, and the factoring problem on a strong modulus untouched in all of them. RSA-250, the eighth row of the catalog, is the ceiling -- a strong-but-undeployed challenge number, not a field break.

Every fix changed how RSA is generated, used, or negotiated -- validated entropy and structure tests, OAEP and PSS and uniform errors, dead export and SSLv2 and TLS 1.3 -- never RSA. And where three incidents did end in a factorization, the deployment had already produced a weak modulus, so the math merely finished a job it had been handed.

When your RSA keys fall, don't ask whether someone factored the modulus. Ask which layer the math depends on but does not control gave way: the primes, the padding, or the negotiation.

One last time, keep the hedge honest: almost never, not never. Factoring is real and fell RSA-512, RSA-768, and RSA-250 as challenge numbers, and Shor's algorithm is coming for strong keys on a quantum computer -- but that is the story How RSA Would Break tells, and the constructive OAEP and PSS depth belongs to RSA Done Right.

The factoring problem was never the weak link in the field, and no bigger key would have saved a single one of these deployments. That is why this is Part 3 of a series about how things break in real life, not a chapter on the Number Field Sieve.