# How RSA Would Break: Why Factoring Is the Slow Path and Coppersmith Is the Fast One
> Everyone says you break RSA by factoring the modulus. That is the slowest path. A structural tour of the fast lane, the slow lane, and the quantum one.
*Published: 2026-07-17*
*Canonical: https://paragmali.com/blog/how-rsa-would-break-why-factoring-is-the-slow-path-and-coppe*
*© Parag Mali. All rights reserved.*
---
Most people picture an RSA break as someone factoring the modulus. That is the slowest, least-likely path there is: the best classical sieve methods (the quadratic sieve, then the General Number Field Sieve) are sub-exponential, and the record has crawled from 426-bit RSA-129 in 1994 to 829-bit RSA-250 in 2020, still a universe short of a 2048-bit key [@boudot-rsa250-2020]. The fast cracks never factor `N` at all. Coppersmith's lattice method, Wiener's small-`d` attack, and their relatives run in polynomial time, but only when a parameter or key-generation choice deviates from the ideal [@boneh-survey-1999]. Against a correctly generated RSA-2048 key with `e = 65537`, a full-size random `d`, and OAEP padding, every one of those preconditions is absent, so the fast lane has no applicable attack. The only structural attack that breaks a well-formed key is Shor's quantum algorithm, which as of 2026 waits on hardware that does not yet exist [@shor-siam-1997; @gidney-2025].
## 1. The break never comes through the front door
Ask a room of engineers how RSA breaks, and almost everyone reaches for the same answer: someone factors the modulus. They are describing the slowest, least-likely path there is. The attacks that actually work never touch `N` at all, and the one attack that could break a flawlessly generated key has not been built yet, because it needs a computer that does not exist.
That is the whole argument of this article, and it runs against the common intuition hard enough to be worth stating plainly. RSA's security is usually explained as "factoring is hard, and your key is a big number nobody can factor." Both halves are true, and together they still point you at the wrong threat. Factoring your modulus is the one attack a bigger key genuinely slows down, which is exactly why it is the attack that will almost certainly never be the way your key falls.
Here is the organizing lens for everything that follows: a **two-speed map** with a third road. The *slow lane* attacks the hardness assumption directly by factoring `N`. It works on any key, needs no mistake on your part, and is asymptotically glacial.
The *fast lane* ignores `N` entirely and attacks the *instantiation*, the specific way this key and this message were built. It runs in polynomial time and is genuinely fast, but only when the parameters or the key generation leaked structure they should not have. And the *third road*, Shor's quantum algorithm, reopens the front door itself by changing the machine you compute on, breaking even a perfect key, if and only if someone builds the hardware.
> **Key idea:** The front door of RSA is bolted, and it opens only at a crawl: factoring is the slow path, not the likely one. The fast cracks come through side windows that a well-generated key never leaves open. And the single attack that opens the front door itself is quantum, on a machine that has not been built.
flowchart TD
A["Break RSA-2048"] --> B["Slow lane: factor N directly"]
A --> C["Fast lane: attack the instantiation"]
A --> D["Third road: change the machine"]
B --> B1["GNFS, sub-exponential, glacial"]
C --> C1["Coppersmith, Wiener, polynomial"]
D --> D1["Shor, polynomial, needs a quantum computer"]
B1 --> E{"Beats a correct key?"}
C1 --> E
D1 --> E
E -->|"slow lane, not in practice"| F["Correct key survives classically"]
E -->|"fast lane, only with a defect"| F
E -->|"third road, yes, on hardware that does not exist"| G["The one real structural threat"]
One boundary before we begin, because it decides what counts as an answer. This is a *structural* story about the mathematics of the algorithm itself. The attacks that steal real data most often never touch RSA's math at all; they break the implementation or the protocol around it. Here we stay inside the equations, where the only question is whether the numbers themselves give way.
> **Note:** This article analyzes cryptanalysis of RSA's own mathematics. Side channels, fault and power attacks, implementation bugs, weak random-number generators, key-generation library defects such as ROCA, padding oracles such as Bleichenbacher's, and protocol downgrades such as FREAK are all out of scope. They are how RSA breaks *in practice*, and they are covered by the companion article. One exception that belongs to the math: Shor's quantum algorithm counts as a structural break and is in scope. Grover's algorithm, a generic search speedup, is only mentioned to mark the edge of the map.
So if factoring is the slow path, what makes the fast one fast, and why does it never touch `N`? To see that, start where RSA started: with a bet nobody could prove they would win.
## 2. A wager on a problem no one has proven hard
In 1977, three researchers at MIT, Ron Rivest, Adi Shamir, and Leonard Adleman, answered an open call. A year earlier, Whitfield Diffie and Martin Hellman had described what public-key cryptography should do without giving a concrete way to do it: a lock anyone can snap shut but only the keyholder can open [@diffie-hellman-1976]. Rivest, Shamir, and Adleman supplied the lock [@rivest-shamir-adleman-1978].
That August, Martin Gardner's Mathematical Games column in *Scientific American* handed it to the public as a dare: a 129-digit number to factor, a modest cash prize, and the confident promise that reading the encrypted message would take far longer than any reader would live to see [@gardner-1977; @atkins-rsa129-1995].
The question worth holding onto is whether that confidence was *earned* or merely *borrowed*.
RSA itself is almost aggressively simple. Pick two large primes and multiply them into a public modulus $N = pq$. Publish `N` and a public exponent `e`. To encrypt a message `m`, compute $c = m^e \bmod N$; to decrypt, compute $m = c^d \bmod N$, where the private exponent `d` is chosen so that $ed \equiv 1 \pmod{\varphi(N)}$ and $\varphi(N) = (p-1)(q-1)$ is Euler's totient [@rivest-shamir-adleman-1978]. Encryption is a modular exponentiation anyone can perform. Decryption is the same operation with a secret exponent that only the keyholder knows.
Everything rests on one hinge. To recover `d`, the obvious route is to compute $\varphi(N)$, and to compute $\varphi(N)$ you need `p` and `q`, which means factoring `N`. So RSA is *believed* to be as hard to break as factoring is hard to do. Read that sentence twice, because the load-bearing word is "believed." Rivest, Shamir, and Adleman did not prove that breaking RSA requires factoring, and no one has proven it since. RSA is a wager that a specific problem is hard, staked on decades of failed attempts to make it easy rather than on a theorem.
A function that is easy to compute in the forward direction but hard to invert, unless you hold a secret piece of information (the trapdoor) that makes inversion easy. RSA's forward direction is modular exponentiation, its trapdoor is the factorization of `N`, and its entire security is the conjecture that without the trapdoor, inversion stays hard.
What makes the RSA story unusually honest is that the field turned this belief into a *dated, public experiment*. In March 1991, RSA Security launched the RSA Factoring Challenge: a published list of moduli, cash bounties, and an open invitation to factor them [@wiki-rsa-factoring-challenge]. Every time a challenge number fell, the community learned precisely how far the sharpest available methods and machines could reach in a given year. The result is something most security assumptions never get: a fifty-year measured record of exactly how hard factoring has proven to be in practice.
timeline
title Fifty years of RSA cryptanalysis
1977 : RSA published : Gardner challenge
1985 : Hastad low-exponent broadcast
1990 : Wiener small-d attack : Number Field Sieve
1994 : Shor quantum factoring : RSA-129 factored
1996 : Coppersmith small-root method
1999 : Boneh-Durfee small-d lattice : Boneh survey
2009 : RSA-768 factored
2020 : RSA-250 factored
2025 : Shor estimate under one million qubits
That timeline is also a map of everything this article covers, and it splits cleanly into the two speeds. Some entries, the Number Field Sieve, RSA-129, RSA-768, RSA-250, are the slow lane: brute assaults on the factoring problem itself, dated by when a bigger number finally fell. Others, Hastad, Wiener, Coppersmith, Boneh-Durfee, are the fast lane: polynomial-time attacks that never factor anything, dated by when someone noticed a new way for a careless instantiation to give itself away. Only one entry, Shor, belongs to neither lane, because it changes the machine.
If the whole system rests on one unproven assumption, the obvious move is to attack that assumption head-on and just factor `N`. Fifty years of the sharpest minds in computational number theory tried exactly that. Here is how far they got.
## 3. The slow lane: attacking factoring head-on
The direct attack writes itself: break RSA by factoring the modulus. The punchline is not triumph but frustration. Even the reigning champion algorithm is, at cryptographic sizes, glacial.
The ladder is a genealogy, and each rung earned its place by beating the one below it. At the bottom sits **trial division** and Fermat's method, fully exponential in the size of `N` and useless past a few dozen digits. Then come the special-purpose methods: John Pollard's **`p-1`** method (1974), fast whenever `p-1` happens to have only small prime factors [@pollard-pm1-1974], and his **rho** method (1975), which finds a small factor `p` in about $O(p^{1/2})$ steps using almost no memory [@pollard-rho-1975]. These are lethal against unlucky primes but hopeless against a balanced modulus whose factors are both enormous.
The real lineage of general-purpose factoring begins with a single idea: instead of searching for a factor directly, manufacture a congruence of squares $x^2 \equiv y^2 \pmod{N}$ with $x \not\equiv \pm y$, and read a factor off $\gcd(x-y, N)$. Morrison and Brillhart's continued-fraction method, **CFRAC** (1975), was the first to collect many small relations and combine them into that square with linear algebra, and the first general method to run in sub-exponential time [@morrison-brillhart-1975]. Carl Pomerance's **Quadratic Sieve** (1985) replaced slow per-number testing with a fast sieve and dominated the 1980s and early 1990s at heuristic cost $L_N[1/2, 1]$ [@pomerance-qs-1985]. Then, in 1990, the **Number Field Sieve** dropped the exponent from one half to one third, the single largest asymptotic improvement in the history of factoring, and the last one to date [@lenstra-nfs-1990].
Factoring costs are written with $L_N[\alpha, c] = \exp\big((c + o(1))(\ln N)^{\alpha}(\ln\ln N)^{1-\alpha}\big)$. The exponent $\alpha$ interpolates between two worlds: $\alpha = 1$ is fully exponential in the bit-length, $\alpha = 0$ is polynomial, and $\alpha = 1/3$ sits in between, "sub-exponential." Sub-exponential is genuinely faster than exponential, which is why big numbers can be factored at all, and genuinely slower than polynomial, which is why they cannot be factored at cryptographic sizes.
The fastest known classical algorithm for factoring a general large integer, with heuristic running time $L_N[1/3, (64/9)^{1/3}] \approx L_N[1/3, 1.923]$ [@lenstra-nfs-1990]. It builds a congruence of squares by collecting relations that are simultaneously smooth on a rational side and an algebraic side, then solves a very large linear system. Every RSA factoring record since the late 1990s has used a GNFS implementation [@zimmermann-records].
An integer is B-smooth if every one of its prime factors is at most `B`. Smoothness is the lever every modern factoring algorithm pulls: the sieve hunts for values that are B-smooth, because only those factor completely over a fixed, small "factor base" of primes and can be fed into the linear algebra. The art of the Number Field Sieve is arranging for enough smooth relations to appear.
Definitions establish that GNFS is sub-exponential. The record trajectory shows what sub-exponential *feels* like against real keys, and it is the heart of this section's argument. Do not take "glacial" on faith. Watch the dates.
| Challenge | Modulus size | Year factored | Method and reported effort |
|-----------|--------------|---------------|----------------------------|
| RSA-129 | 426 bits (129 digits) | 1994 | Quadratic sieve, worldwide volunteer effort [@atkins-rsa129-1995] |
| RSA-155 | 512 bits | 1999 | Number Field Sieve [@cavallar-rsa155-2000] |
| RSA-768 | 768 bits | 2009 | GNFS, nearly 2000 core-years [@kleinjung-rsa768-2010] |
| RSA-250 | 829 bits | 2020 | GNFS, roughly 2700 core-years [@boudot-rsa250-2020] |
Read the first and last rows together. From RSA-129 in 1994 to RSA-250 in 2020 is roughly 400 bits of progress in 26 years [@zimmermann-records; @wiki-rsa-numbers]. A deployed RSA key is 2048 bits. The record is still more than 1,200 bits short of it, and RSA-250 alone burned about 2,700 core-years of computation on the open-source CADO-NFS software [@boudot-rsa250-2020; @cado-nfs].A core-year is one processor core running flat out for a year, so 2,700 core-years is a large cluster running for months. The same team's peer-reviewed 240-digit experiment documents the sieving-and-linear-algebra methodology behind these records [@boudot-dlp240-2020]. The gap is not a matter of waiting a few more years for a faster cluster, because the cost curve is sub-exponential, so each additional bit is more expensive than the last. You can compute just how much more expensive.
{`
from math import log, exp
# Heuristic GNFS cost L_N[1/3, (64/9)^(1/3)] as a function of bit-length.
def L(bits, alpha=1/3, c=(64/9)**(1/3)):
lnN = bits * log(2) # ln N for a 'bits'-bit modulus
return exp(c * lnN**alpha * (log(lnN))**(1 - alpha))
cost_829 = L(829) # RSA-250, the current classical record
cost_2048 = L(2048) # a deployed key
print("GNFS constant (64/9)^(1/3) =", round((64/9)**(1/3), 4))
print("Relative L-cost at 829 bits: %.3e" % cost_829)
print("Relative L-cost at 2048 bits: %.3e" % cost_2048)
print("RSA-2048 is harder than RSA-250 by a factor of about: %.3e" % (cost_2048 / cost_829))
print()
print("RSA-250 already cost ~2700 core-years; scaling by that factor gives")
print("about %.1e core-years for RSA-2048 -- far beyond any foreseeable cluster."
% (2700 * cost_2048 / cost_829))
`}
The numbers that fall out are not "a thousand times harder" or "a million times harder." They are astronomical: the same sober `L[1/3]` curve that predicted RSA-250 puts a 2048-bit modulus permanently outside the reach of any classical machine anyone can foresee. This is the slow lane in one image. It works on every key, it needs no mistake by the defender, and it will almost certainly never reach a modern modulus.
flowchart TD
A["Trial division and Fermat: fully exponential"] --> B["Pollard p-1 (1974) and rho (1975): special-purpose"]
B --> C["CFRAC (1975): first sub-exponential"]
C --> D["Quadratic Sieve (1985): exponent one half"]
D --> E["Number Field Sieve (1990): exponent one third"]
E --> F["No asymptotic gain since 1990"]
A --> G["ECM (1987): niche, cost set by the smallest factor"]
The ladder has texture worth pausing on. When RSA-129 fell in 1994, the recovered plaintext was a puzzle phrase the designers had hidden inside the challenge.The RSA-129 plaintext was "THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE" [@atkins-rsa129-1995]. A widely repeated web summary claims it read "SEND MORE MONEY"; that is simply wrong. Pollard's `p-1` method left a lasting mark on how primes were chosen: for years, key-generation guidance called for "strong primes," primes `p` where `p-1` has a large prime factor, precisely so the `p-1` attack could not bite.The strong-prime design rule is a direct descendant of Pollard's 1974 `p-1` method [@pollard-pm1-1974]. Modern guidance mostly dropped the requirement once GNFS made the specific structure of `p-1` irrelevant to the dominant attack, but the historical lineage is exact. And one rung of the ladder never went away, it just found a different job.Hendrik Lenstra's Elliptic Curve Method (1987) has a running time that depends on the size of the *smallest* factor, not the whole modulus [@lenstra-ecm-1987]. That makes it superb at peeling small primes off a number and useless against a balanced RSA modulus whose two factors are each half the bits. It is a living tool, in the wrong weight class for this fight.
The slow lane also has a recurring failure mode that is not technical but sociological, and it is worth immunizing against before the fast lane tempts you.
"No, RSA Is Not Broken." -- Bruce Schneier, on the 2021 claim that short-vector lattice algorithms had destroyed the RSA cryptosystem [@schneier-2021].
So the front door is bolted, and it opens only at a crawl. Fifty years of the best available mathematics moved the record about 400 bits, and the cost curve guarantees the next 1,200 bits are not coming on any classical machine. A defender who only worries about factoring has been watching the wrong door. Because a locksmith's insight changes the whole game: what if you never had to open the front door at all? What if you never factored `N`?
## 4. The fast lane opens: Hastad and Wiener
The insight that reroutes the entire story is deceptively small: you do not have to factor `N` at all. Factoring is the *hardest* way to break RSA, not the easiest. If the way this particular key or this particular message was built leaks structure, the key can fall in polynomial time, and `N` stays untouched the whole time. Two attacks from the late 1980s and early 1990s proved the fast lane exists, and each one falls out of a single leaked parameter.
The first is **Johan Hastad's low-exponent broadcast attack** (introduced at CRYPTO '85 and generalized in his 1988 SIAM paper). Suppose a sender uses a tiny public exponent, say $e = 3$, and sends the *same* message `m` to several recipients, each with their own modulus $N_i$, without randomized padding. Each recipient sees $c_i = m^3 \bmod N_i$. An eavesdropper who collects three of these ciphertexts applies the Chinese Remainder Theorem to combine them into a single value congruent to $m^3$ modulo $N_1 N_2 N_3$ [@hastad-1988].
Since `m` is smaller than every $N_i$, the true $m^3$ is smaller than the product $N_1 N_2 N_3$, so the combined congruence is an *equation over the integers*: the combined value simply equals $m^3$, with no modular wraparound. Take an ordinary integer cube root and you have the message. No factoring, no lattice, just arithmetic [@hastad-1988].
The precondition is loud, and it is the reason a good key is immune. Hastad needs a tiny exponent *and* the same message broadcast unpadded to several recipients. Use $e = 65537$ instead of 3, or pad each message with fresh randomness so no two ciphertexts encrypt the same integer, and the broadcast structure that made $m^3$ recoverable is gone. The attack does not get slower; it stops applying.
The second attack targets the other exponent. **Michael Wiener's small private-exponent attack** (1990) shows that shrinking `d` to speed up decryption is fatal. When the private exponent is small, specifically $d < \tfrac{1}{3}N^{1/4}$, the public ratio $e/N$ becomes an extraordinarily good rational approximation to the secret ratio $k/d$ that lurks in the key equation [@wiener-1990]. And there is a classical theorem of number theory that says the *only* fractions that approximate a real number that well are its continued-fraction convergents. So the attacker expands $e/N$ as a continued fraction, and the secret denominator `d` appears as one of the convergents' denominators, recovered from nothing but the public key `(e, N)` [@wiener-1990].
Any real number can be written as a nested fraction $a_0 + 1/(a_1 + 1/(a_2 + \cdots))$. Truncating that expansion after a few terms gives a sequence of rational approximations $h_i/k_i$ called convergents, and they are provably the *best* rational approximations for their denominator size. Wiener's attack turns key recovery into a search through the convergents of $e/N$: one of their denominators is the secret exponent `d`.
Because the whole attack is a short walk through a list of fractions, it is genuinely fast, and it is easy to watch happen. The code below builds an RSA key with a deliberately small `d`, publishes only `(e, N)`, and then recovers `d` from the public key alone.
{`
from math import isqrt, gcd
# Build a deliberately weak RSA key with a very small private exponent d.
p = 999999937
q = 999999893
N = p * q
phi = (p - 1) * (q - 1)
# Wiener succeeds whenever d < (1/3) * N**(1/4). Take the largest such d.
bound = isqrt(isqrt(N)) // 3
d = next(x for x in range(bound, 2, -1) if gcd(x, phi) == 1)
e = pow(d, -1, phi) # matching public exponent
print("Public key: N =", N)
print(" e =", e)
print("Hidden small d =", d, " (Wiener bound about", bound, ")")
# The attacker sees only (e, N). Expand e/N as a continued fraction;
# each convergent's denominator is a candidate for d.
def convergents(num, den):
a = []
x, y = num, den
while y:
a.append(x // y)
x, y = y, x % y
h0, h1 = 0, 1
k0, k1 = 1, 0
for ai in a:
h0, h1 = h1, ai * h1 + h0
k0, k1 = k1, ai * k1 + k0
yield h1, k1 # (candidate k, candidate d)
for k_cand, d_cand in convergents(e, N):
if k_cand == 0:
continue
if (e * d_cand - 1) % k_cand == 0: # phi(N) must be an integer
phi_guess = (e * d_cand - 1) // k_cand
s = N - phi_guess + 1 # candidate p + q
disc = s * s - 4 * N # roots of x^2 - s*x + N
if disc >= 0 and isqrt(disc) ** 2 == disc:
print("Recovered d =", d_cand, " correct:", d_cand == d)
break
`}
Once again the precondition is the whole story. Wiener needs a small `d`. A correctly generated key uses a full-size random `d` on the order of `N` itself, and there is no low-denominator convergent of $e/N$ to find, so the attack has nothing to grab.
Notice what these two attacks share, and where each falls short. Both exploit a *leaked parameter*, not the modulus. Both run in polynomial time. And both were, at first, treated as clever isolated tricks: a broadcast maneuver here, a continued-fraction maneuver there. Hastad even needs an awkward number of near-identical ciphertexts, and Wiener's $N^{1/4}$ bound is visibly loose, as if it could be pushed further with a better tool. For eight years the fast lane stayed a grab-bag of one-offs. Then someone found the single principle hiding underneath all of them.
## 5. Coppersmith's master key
In 1996, Don Coppersmith found the idea that turned the grab-bag into a theory. Stated plainly, it is one of the most useful facts in applied cryptography, and once you see it you cannot unsee it in any of the fast-lane attacks.
Here is the theorem. Take a polynomial $f(x)$ of degree `d`, and suppose it has a root $x_0$ modulo `N` that is *small*, meaning $|x_0| < N^{1/d}$. Then you can find $x_0$ in time polynomial in $\log N$ and `d`, using lattice reduction [@coppersmith-1997]. That is the whole master key. Not "factor `N`," not "guess the message," but: whenever an unknown quantity is *small* and sits inside a *known* algebraic structure, you can solve for it directly.
A lattice is the set of all integer combinations of some basis vectors, an infinite grid of points in space. The same lattice has many bases, some "long and skew," some "short and nearly perpendicular." The Lenstra-Lenstra-Lovasz (LLL) algorithm, from 1982, efficiently turns a bad basis into a reduced one whose vectors are short and close to orthogonal. Throughout this article LLL is a black box with one job: hand it a lattice, and it returns a surprisingly short vector in polynomial time [@may-survey-2009].
The bridge from "small modular root" to "short lattice vector" is the contribution of Nick Howgrave-Graham (1997), whose reformulation is the version taught and coded today [@howgrave-graham-1997]. The trick is elegant. You do not attack $f$ directly. Instead you build a lattice out of shifted and scaled multiples of $f$, all of which vanish at the same secret root $x_0$ modulo powers of `N`.
LLL finds a short combination of them, and shortness has a precise payoff: a polynomial with small enough coefficients that, at the small value $x_0$, it cannot merely be *congruent* to zero modulo `N`; it must be *exactly* zero as an integer [@howgrave-graham-1997]. The modular problem has become an ordinary equation over the integers, and ordinary equations over the integers are easy to solve for their roots. That is the same "collapse to the integers" trick that let Hastad's cube root work, generalized into a machine.
flowchart LR
A["Known structure plus a small unknown"] --> B["Write it as f(x) with a small root mod N"]
B --> C["Build a lattice from shifted multiples of f"]
C --> D["LLL returns a short vector"]
D --> E["A new polynomial, same root, small enough to hold over the integers"]
E --> F["Ordinary root-finding recovers x0"]
A polynomial-time algorithm that, given a monic polynomial $f(x)$ of degree `d` and a modulus `N`, finds every integer root $x_0$ with $|x_0| < N^{1/d}$ satisfying $f(x_0) \equiv 0 \pmod{N}$ [@coppersmith-1997]. The size bound $N^{1/d}$ is the load-bearing threshold: it is generous for tiny degree (a cube-root-sized unknown for $d = 3$) and shrinks fast as the degree grows, which is exactly why a large public exponent starves the method of anything to find.
> **Key idea:** Every fast-lane attack in this article is the same sentence in a different costume: known structure plus a small unknown lets you solve for the unknown. Hastad's broadcast, stereotyped messages, related messages, partial key exposure, and the strongest small-`d` attack are all instances of Coppersmith's small-root method, powered by LLL whenever the unknown is smaller than $N^{1/d}$. The zoo is one animal.
Watch Hastad collapse to a corollary. His broadcast attack is just the small-root method for the polynomial $f(x) = x^e - c$ with the tiny exponent making the root findable; the CRT step is a convenience, not the essence [@coppersmith-1997]. The purest instance of all is textbook RSA with $e = 3$ and no padding, where the message itself is the small root. If $m^3 < N$, the ciphertext never wrapped around the modulus, so the "encryption" is just a cube, and a cube root is the entire attack.
{`
def icbrt(n):
# Exact integer cube root via Newton's method (works for huge integers).
if n < 2:
return n
x = 1 << ((n.bit_length() + 2) // 3)
while True:
y = (2 * x + n // (x * x)) // 3
if y >= x:
return x
x = y
N = (1 << 2047) + 12345 # a 2048-bit stand-in modulus
e = 3
m = 42424242424242 # a short message: m^3 stays far below N
c = pow(m, e, N) # textbook RSA "encryption": c = m^3 mod N
print("Is m^3 < N ?", m**3 < N)
print("recovered m =", icbrt(c), " correct:", icbrt(c) == m)
# Real padding widens the message so that m2^3 exceeds N and wraps around.
m2 = (1 << 700) | m
c2 = pow(m2, e, N)
print("Is (padded m2)^3 < N ?", m2**3 < N)
print("plain cube root now fails:", icbrt(c2) != m2)
`}
The second half of that snippet is the entire defense in miniature. Once the message is widened by real padding so that its cube exceeds `N`, the ciphertext wraps around the modulus, the "small root" is no longer small, and the cube root returns garbage. The attack did not get harder to run; its precondition vanished. Hold onto that distinction, because it is the shape of every result in the next section: one theorem, many doors. So which locks does the master key actually open on a real RSA deployment, and, just as important, which ones stay firmly shut?
## 6. The Coppersmith family today
The mature fast lane is the master key reused, deliberately, by name. Each member of the family has the same shape, known structure hiding one small unknown, and each is neutralized by exactly one standard parameter choice. Walk them in order and the pattern becomes impossible to miss.
**Stereotyped and known-bits messages.** Suppose an attacker knows most of a message, a fixed template `B`, and only a short secret block `x` is unknown, so the plaintext is $B + x$. With public exponent `e`, the ciphertext gives the polynomial $f(x) = (B + x)^e - c$, whose small root is the secret block, recoverable whenever $|x| < N^{1/e}$ [@coppersmith-1997]. A low exponent and a mostly-known message is all it takes. Raise `e` to 65537 and the recoverable window $N^{1/e}$ shrinks to almost nothing; randomize the message with padding and the "small unknown" becomes the entire plaintext, far too big to be a small root.
**Factoring with high bits of `p` known.** Coppersmith's method also attacks the modulus, but only with a head start. If an attacker already knows roughly the top half of the bits of `p`, the remaining low bits form a small root of a polynomial modulo `N`, and the method recovers them, factoring `N` in polynomial time [@coppersmith-1997; @may-survey-2009]. The precondition is severe: you must already know half of a secret prime. Generate both primes from a good random source and no such head start exists.
**Related messages and short pads.** If two messages satisfy a *known linear relation* and are sent under the same small exponent, the attacker forms two polynomials sharing the plaintext as a root and takes their polynomial greatest common divisor, which reveals it. This is the Franklin-Reiter base case [@cfpr-1996]. Coppersmith extended it to the case where the relation is an *unknown but short* pad, solved with the small-root method, the short-pad attack [@cfpr-1996]. Both need a small `e` and a short or structured relationship between messages. [OAEP](/blog/rsa-is-a-trapdoor-not-a-cryptosystem-oaep-pss-and-the-25-yea/)'s long, fully random pad destroys any such relation, which is precisely what it was designed to do.
**Partial key exposure.** Perhaps the most unsettling member: a *fraction* of the private key's bits can reconstruct the rest. Boneh, Durfee, and Frankel showed in 1998 that for a low public exponent, roughly a quarter of the least-significant bits of `d` suffice to recover the whole exponent [@bdf98-1998]. Ernst, Jochemsz, May, and de Weger removed the low-exponent restriction in 2005, extending partial key exposure to full-size exponents with multivariate Coppersmith techniques [@ernst-pke-2005]. The precondition is a *leak*: some bits of `d` or `p` must escape. With no leakage, there is nothing to extend, and *how* bits leak, timing, power, a fault, is the implementation sibling's subject, not RSA's mathematics.
**Boneh-Durfee.** Finally, the master key circles back to finish what Wiener started. Boneh and Durfee re-aimed Coppersmith's lattice at the key equation itself and pushed the vulnerable small-`d` bound from Wiener's $N^{1/4}$ up to $d < N^{0.292}$, the strongest small-exponent attack known [@boneh-durfee-1999]. It is the same lattice engine, pointed at a different polynomial. And it dies against the same defense: a full-size random `d` on the order of `N` sits far above the $N^{0.292}$ threshold.
These are cryptanalytic tools, not shipped software, but they are entirely practical to run. LLL and its stronger cousin BKZ live in the open-source **fplll** library and its Python binding **fpylll** [@fplll; @fpylll], and Coppersmith's small-root method is a single function call, `small_roots()`, in SageMath [@sagemath-smallroots]. The barrier to using them is never the tooling. It is finding a key with a precondition to attack.
A stereotyped-message attack in SageMath looks close to this: work in `Zmod(N)`, define the polynomial `f = (B + x)^e - c` whose small root is the secret block, and call `f.small_roots(X=bound, beta=1)`. The library builds the lattice, runs LLL, and returns the root, with no hand-rolled lattice at all [@sagemath-smallroots]. Swap in a different `f` and the same call becomes factoring-with-known-bits or a related-message attack: one engine, pointed at a different polynomial.
flowchart TD
E["Coppersmith small-root engine"] --> A["Stereotyped or known-bits message: short secret block"]
E --> B["Factoring with high bits of p known: half of p leaks"]
E --> C["Franklin-Reiter and short-pad: same small e, short or known pad"]
E --> D["Partial key exposure: a fraction of d's bits leak"]
E --> F["Boneh-Durfee: deliberately small private exponent d"]
Lay the whole family in a table and the argument writes itself. Every row is a real, polynomial-time attack. Every row also has a right-hand column that a correctly generated RSA-2048 key fills in by default.
| Fast-lane attack | Exact precondition it needs | Closed by |
|------------------|-----------------------------|-----------|
| Hastad broadcast | tiny `e`, same message sent unpadded to many recipients | $e = 65537$ or randomized padding [@hastad-1988] |
| Stereotyped / known-bits | most of the message is a known template, short secret block | randomized OAEP padding [@rfc8017] |
| Factoring, high bits of `p` | roughly half the top bits of `p` already known | independent, well-sourced random primes [@may-survey-2009] |
| Franklin-Reiter / short-pad | same small `e`, a known or short relation between messages | $e = 65537$ plus OAEP's long random pad [@cfpr-1996] |
| Partial key exposure | a constant fraction of `d`'s or `p`'s bits leaked | no key-bit leakage; full-size random `d` [@ernst-pke-2005] |
| Wiener small-`d` | $d < \tfrac{1}{3}N^{1/4}$ | full-size random `d` [@wiener-1990] |
| Boneh-Durfee small-`d` | $d < N^{0.292}$ | full-size random `d` near `N` [@boneh-durfee-1999] |
The randomized padding scheme standardized for RSA encryption in PKCS #1 v2.2 (RFC 8017) [@rfc8017]. Before exponentiation, OAEP mixes the message with fresh random bytes through a two-round structure, so that the integer actually raised to the power `e` is large, high-entropy, and different every time, even for identical plaintexts. That single step removes the "known structure" and the "small unknown" that every Coppersmith-family attack needs, which is why OAEP is the defense that closes most of the table at once.
There is something almost paradoxical here, and it is the sharpest structural point in all of RSA cryptanalysis. None of these attacks is wrong. None is slow. None has been refuted or patched away. They remain perfectly correct, polynomial-time algorithms. They are simply *inapplicable* to a key that never grants their precondition. The fast lane does not fail against a good key by being outrun, the way the slow lane is outrun by a big modulus. It fails by *precondition-absence*: there is nothing for the lattice to grab.
> **Note:** This is the mental model to keep. A larger key defeats the slow lane by making factoring more expensive. Nothing defeats the fast lane, because the fast lane was never a contest of speed. It is a contest of *whether a defect exists*. Remove the defect, small exponent, small `d`, missing padding, leaked bits, correlated primes, and each attack does not slow down; it simply has no input. A correct RSA-2048 key wins the fast lane by forfeit.
An attack that is perfectly correct yet perfectly inapplicable is the sharpest point in RSA cryptanalysis. Against a well-generated key, the fast lane has no applicable attack.
So put the two lanes together against a specific, correct target: RSA-2048 with $e = 65537$, a full-size random `d`, two independent well-sourced primes, and OAEP padding. The slow lane is available but glacial, more than 1,200 bits and an astronomical cost curve away from success. The fast lane is polynomial but inert, because every precondition in the table above is absent [@boneh-survey-1999; @rfc8017]. Against that key, the classical state of the art is a phrase worth memorizing: *no applicable attack.*
The fast lane is fast but conditional; the slow lane is universal but glacial. Put all three roads on one table, and ask the only question that matters: which one actually threatens a well-generated key?
## 7. Three roads, compared
Everything so far has been building one picture. Lay the slow lane, the fast lane, and the third road side by side, and the article's thesis stops being a claim and becomes something you can read straight off a table.
| Dimension | Slow lane: GNFS | Fast lane: Coppersmith family | Third road: Shor |
|-----------|-----------------|-------------------------------|------------------|
| What it attacks | the hardness assumption (factor `N`) | the instantiation (a specific defect) | the hardness assumption (factor `N`) |
| Input required | `N` only | `N` plus a parameter or key-gen defect | `N` only |
| Precondition | none | small `e`, small `d`, no padding, leaked bits, or correlated primes | a working quantum computer of the right size |
| Worst-case time | $L_N[1/3, 1.923]$, sub-exponential | polynomial | polynomial in $\log N$ |
| Breaks a correct RSA-2048 key? | not in practice | no | yes |
| Computational model | classical | classical | quantum |
Read the table as three sentences. The **slow lane** breaks *any* key, needs no mistake, and is asymptotically stalled: its $L_N[1/3, 1.923]$ cost has not improved since 1990, and against 2048 bits it is glacial [@lenstra-nfs-1990]. The **fast lane** is genuinely polynomial and genuinely fast, but it goes completely dark against a correct key, because every one of its attacks needs a defect the key does not have [@coppersmith-1997]. Two roads, and *neither* threatens a well-generated RSA-2048 key in practice: one is too slow, the other has no opening.
That is the corner the argument has painted us into, and it forces the third road into view. If the slow lane is stalled and the fast lane is inert, then the only way to break a correct key is to stop playing the classical game entirely, to change the *machine*. That is Shor's algorithm, first announced at FOCS in 1994 and published in full in 1997 [@shor-focs-1994; @shor-siam-1997].
It attacks the same hardness assumption as the slow lane, factoring `N` with no defect required, but it runs in time polynomial in the number of digits of `N`, an exponential speedup over GNFS. It is the one entry in the table that breaks a flawless key, and it carries the one precondition no careful key generation can supply or deny: a large, fault-tolerant quantum computer, which does not exist as of 2026.
The mechanism is the subject of the next section; for now, the table has delivered its verdict. The only structural attack left standing against a good key is a change of computational model.
That verdict points at one uncomfortable question the table cannot answer. The slow lane is stalled, and we have been treating that as if it were a law of nature. But is factoring *actually* hard, or have we simply not found the trick yet? The honest answer is more unsettling than either the optimists or the doomsayers usually admit.
## 8. Is factoring even hard, and how hard?
Beneath fifty years of engineering confidence lies an uncomfortable truth: nobody has ever *proven* that factoring is hard. RSA's security is a conjecture that has survived a long time, which is a very different thing from a theorem.
Start with the most common misconception, because correcting it reframes everything. People often say factoring is NP-hard, as if RSA inherited the full difficulty of the hardest problems in NP. It did not. The decision version of factoring sits in $\text{NP} \cap \text{co-NP}$: a factor is a short certificate that the answer is "yes," and because primality can be checked efficiently, there is also a short certificate for "no" [@hac-1996]. A problem in that intersection cannot be NP-complete unless NP equals co-NP, which almost no one believes.
So factoring is very likely *not* among the hardest problems in NP, and the casual "RSA is NP-hard" intuition is simply false [@hac-1996].
It may be worse than that, in a precise and interesting way: breaking RSA might be *strictly easier* than factoring. Boneh and Venkatesan gave evidence that no "algebraic reduction" can turn an efficient low-exponent RSA-breaker into a general factoring algorithm, which would mean recovering a message does not require the full strength of factoring [@boneh-venkatesan-1998].
Aggarwal and Maurer later proved that breaking RSA *is* equivalent to factoring, but only in the restricted "generic ring model," where the attacker is forbidden from exploiting the specific bit-representation of numbers [@aggarwal-maurer-2009]. Put together, the honest statement is that we do not know whether the RSA problem and factoring are equally hard. We only know the assumption rests on belief, layered on belief.
What we *can* state precisely are the upper bounds, and the gap between them is the whole story. Classically, the best we can do is GNFS, sub-exponential $L_N[1/3, 1.923]$ [@lenstra-nfs-1990]. On a quantum computer, Shor's algorithm factors in time polynomial in the number of digits of `N`, an exponential improvement [@shor-siam-1997].
There is no known classical *lower* bound anywhere near the upper bound, so the space between "maybe there is a fast classical algorithm we have not found" and "there is definitely a fast quantum algorithm" is enormous and almost entirely unmapped.
Shor's mechanism deserves to be seen, because it is not a faster search; it is a genuinely different idea. Factoring `N` is reduced to finding the *period* of the function $a^x \bmod N$ for a random base `a`, that is, the smallest `r` with $a^r \equiv 1 \pmod{N}$. Classically, finding that period is as hard as factoring.
Quantumly, a superposition over all `x`, a modular exponentiation, and a quantum Fourier transform extract `r` efficiently. Once you have an even `r` with $a^{r/2} \not\equiv -1 \pmod N$, an ordinary classical greatest-common-divisor, $\gcd(a^{r/2} \pm 1, N)$, hands you a factor [@shor-siam-1997]. It is a classical reduction wrapped around a single quantum subroutine.
flowchart TD
A["Pick a random a coprime to N"] --> B["Quantum: find the period r of a^x mod N with the QFT"]
B --> C{"r even and a^(r/2) not congruent to -1?"}
C -->|"no, retry"| A
C -->|"yes"| D["Classical: compute gcd(a^(r/2) plus or minus 1, N)"]
D --> E["A nontrivial factor of N"]
A quantum computer large and reliable enough to run Shor's algorithm against real cryptographic parameters, for example to factor a 2048-bit RSA modulus. Because Shor needs many high-fidelity logical qubits maintained through a long computation, a CRQC requires fault-tolerant error correction over a vast number of physical qubits. No such machine exists as of 2026, and building one is an unsolved engineering problem, not merely a matter of scaling up today's devices.
How far is that machine? The honest answer comes from the people doing the most careful accounting, and their numbers are moving in a way worth understanding. In 2019, Craig Gidney and Martin Ekera estimated that factoring a 2048-bit RSA key with Shor would take roughly 20 million noisy physical qubits running for about 8 hours [@gidney-ekera-2021]. In May 2025, Gidney revised the estimate to *fewer than one million* noisy qubits in under a week, under the *same* hardware assumptions as the 2019 analysis [@gidney-2025].
Read those two figures together carefully. The twentyfold drop did not come from better hardware; it came from better *algorithms* for organizing the computation. The *estimate* is improving far faster than the *machines*, and today's largest quantum devices remain orders of magnitude below even the reduced requirement [@gidney-2025]. No cryptographically relevant quantum computer exists as of 2026.
> **Note:** It is easy to slide from "the resource estimates are dropping fast" to "a quantum break is imminent." That slide is not supported here. As of 2026 there is no machine capable of running Shor against RSA-2048, and predicting when, or whether, one will be built is genuinely uncertain. What the falling estimates establish is that the *paper cost* of the attack is shrinking, not that the *hardware* has arrived. Treat any specific date you see quoted, from anyone, as a forecast, not a fact.
Two facts about scale make the quantum threat qualitatively different from the classical one, and both cut against the defender's usual instinct. First, a bigger key does not help. Shor's cost grows only *polynomially* in the number of digits of `N`, so doubling the modulus from 2048 to 4096 bits multiplies the quantum work by a small constant, not by the astronomical factor that same doubling imposes on GNFS. The move that defeats the slow lane is nearly useless against the third road.
Second, and for the same reason, there is no "safe classical margin" to buy. Against Shor, the defense is not a larger RSA key; it is a different kind of cryptography entirely.
Grover's algorithm is the other quantum result people invoke, and it is a boundary marker, not a structural break [@grover-1996]. It gives a generic square-root speedup for brute-force search, turning a $2^{n}$ key search into about $2^{n/2}$. That halves the effective strength of a symmetric key, which is why AES-256 is favored for post-quantum margin [@nist-sp800-57], but it does nothing structural to RSA: it does not factor `N`, and a square-root speedup on an already-astronomical factoring search changes nothing.
Sit with what this section actually established, because it is the third and deepest shift in the whole article. We cannot prove factoring is hard; its decision problem is not even NP-complete, so RSA rests on a belief rather than a theorem. The fast lane is inert against a correct key, and the slow lane has been asymptotically frozen since 1990. Therefore the only structural break left standing against a well-generated key is a change of computational model, Shor's, and against that change a bigger key does essentially nothing.
The confidence that "a large enough RSA key is safe forever" quietly dissolves. What replaces it is not panic but humility: the security you rely on is an assumption with a possible expiry date you cannot see.
So we cannot prove it is hard, and we cannot yet build the machine that makes it easy. That leaves a precise list of things the field genuinely does not know, and one of them carries a deadline that is invisible precisely because no one can read it.
## 9. What is genuinely unresolved
Strip away the settled results and four honest unknowns remain. This is where the frontier actually sits, and naming the unknowns precisely is more useful than any confident prediction.
**Is factoring in P?** No polynomial-time classical factoring algorithm is known, and none has been ruled out. The strongest evidence for "hard" is negative and empirical: the GNFS exponent has not moved off one third since 1990, and RSA-250 still stands as the largest general-purpose factorization [@lenstra-nfs-1990; @zimmermann-records]. But "we have not found a faster algorithm in 35 years" is not a proof that none exists, and no lower bound forbids one. This is the open problem the entire slow lane rests on.
**Is the RSA problem strictly easier than factoring?** Also open. Boneh and Venkatesan's evidence points toward "yes, at least for algebraic reductions," while Aggarwal and Maurer's equivalence holds only inside the generic ring model [@boneh-venkatesan-1998; @aggarwal-maurer-2009]. Whether recovering an RSA plaintext genuinely requires factoring, in the full model where an attacker can do anything, is unresolved.
**How far can the small-`d` lattice bound be pushed?** Boneh-Durfee reaches $d < N^{0.292}$, and Boneh and Durfee themselves conjecture the true insecurity threshold is $d < N^{0.5}$ [@boneh-durfee-1999]. The gap between $0.292$ and $0.5$ has resisted every attempt to close it, and subsequent lattice reformulations reach the same $0.292$ more cleanly without surpassing it [@may-survey-2009]. Nobody knows where the real boundary lies.
The exponent $0.292\ldots$ is not a round number; it is exactly $1 - 1/\sqrt{2} \approx 0.2929$, a quadratic irrational (the root of $2\delta^2 - 4\delta + 1 = 0$) that falls out of the lattice determinant condition [@boneh-durfee-1999]. Two honesty caveats travel with it: the conjectured true bound $N^{0.5}$ is only a conjecture, and even the proven $N^{0.292}$ result relies on the standard, unproven heuristic that the short lattice vectors LLL returns are algebraically independent. The fast lane's strongest result is itself built on an assumption.
**When does a cryptographically relevant quantum computer arrive?** Genuinely unknowable. And this is the unknown with teeth, because it does not need to be answered to be dangerous.
An attacker records encrypted traffic today and stores it, betting that a cryptographically relevant quantum computer will exist before the data stops being sensitive. When that machine arrives, the archived ciphertext is decrypted retroactively with Shor's algorithm. The threat is live *now*, even though the tool to exploit it does not exist yet, because the interception happens today and only the decryption waits.
Unknowable timelines are not an excuse for paralysis. If you ship RSA today, all four open problems collapse into one concrete, answerable question: what do you actually *do*?
## 10. How not to be the vulnerable key
Here is the practical reward for all this theory: every fast-lane attack in this article maps to exactly one parameter choice that closes it. The defense is not vigilance or luck. It is a short, checkable list, and mainstream libraries already implement most of it by default.
| Do this | It closes | Anchor |
|---------|-----------|--------|
| Use at least 2048-bit keys; 3072-bit for long-lived data | the slow lane (GNFS) | [@nist-sp800-57] |
| Set $e = 65537$, never 3 | Hastad, stereotyped, Franklin-Reiter and short-pad | [@hastad-1988] |
| Use a full-size random `d`, never a small one | Wiener, Boneh-Durfee | [@boneh-durfee-1999] |
| Encrypt with OAEP, never textbook RSA | known-bits and related-message recovery | [@rfc8017] |
| Generate two independent, well-sourced random primes | known-bits-of-`p` factoring | [@may-survey-2009] |
| Begin migrating long-lived secrets to post-quantum schemes | Shor plus harvest-now-decrypt-later | [@gidney-2025] |
NIST maps key sizes to security levels calibrated directly against the GNFS cost curve: RSA-2048 gives roughly 112-bit security and RSA-3072 roughly 128-bit, which is why 3072 bits is the right choice for data that must survive well past 2030 [@nist-sp800-57]. That single row is the *only* place where "use a bigger key" is the correct advice, because it is the only threat, the slow lane, that key size actually defends against.
Why $e = 65537$ specifically? It is $2^{16} + 1$, a Fermat prime. Being greater than the tiny exponents lets it defeat the low-exponent attacks, Hastad's broadcast, stereotyped-message recovery, Franklin-Reiter, while being only 17 bits long, with just two set bits, so encryption stays fast: a square-and-multiply exponentiation needs only 17 steps. It is the sweet spot: recommended by RFC 8017 [@rfc8017] and now the near-ubiquitous default in practice.
The two scaling facts from the last two sections invert the usual intuition. A bigger key buys you *nothing* against a fast-lane defect: an RSA-4096 key with a small `d` falls to Wiener exactly as fast as an RSA-2048 key with a small `d`, because the attack never touched the modulus size. And a bigger key buys you *nothing* against Shor, whose cost grows only polynomially in the key length.
> **Key idea:** A bigger RSA key does one thing: it makes the slow lane slower. It does nothing against a fast-lane defect, because those attacks ignore the modulus, and nothing against Shor, whose cost barely grows with key size. Security against the fast lane comes only from *removing the precondition*; security against the third road comes only from *changing the primitive*. Neither is bought with bits.
> **Note:** Use a 2048-bit key (3072-bit for long-lived data), the default $e = 65537$, a full-size random `d`, two independent random primes from a vetted generator, and OAEP for encryption via your library's high-level API. That configuration closes the entire fast lane by construction and pushes the slow lane past any classical machine. The remaining work is not choosing better parameters, it is starting to plan a migration path for secrets whose confidentiality must outlast the arrival of a quantum computer.
One honest reminder, because a checklist can create false comfort. This list closes the *structural* attacks, the subject of this article. It does not, by itself, protect you from the implementation and protocol failures that break RSA far more often in the real world: padding oracles, timing and fault leaks, weak random-number generators, the ROCA key-generation defect, and downgrade attacks such as FREAK. Those are a different discipline, covered by the empirical sibling *How RSA Breaks in Real Life*. A perfectly parameterized key in a leaky implementation is still a broken key.
Follow the checklist and the entire fast lane goes dark while the slow lane stays glacial, which leaves exactly one way a correctly generated key ever breaks.
## 11. The verdict
Return to the two-speed map, now carrying everything the article has shown. The front door, factoring the modulus, is bolted, and it opens only at a crawl. In 26 years the classical record moved from RSA-129 to RSA-250, roughly 400 bits, and it is still more than 1,200 bits short of a deployed 2048-bit key, on a cost curve that makes the remaining distance astronomical [@zimmermann-records; @boudot-rsa250-2020]. The engineers who picture a break as "someone factors my key" are watching the one door a bigger key actually guards.
The fast cracks come through side windows, and a well-generated key never leaves them open. Against RSA-2048 with $e = 65537$, a full-size random `d`, two independent primes, and OAEP, every Coppersmith-family precondition is absent, and the classical state of the art is simply *no applicable attack* [@boneh-survey-1999; @rfc8017]. The fast lane is not slow against a good key; it is inapplicable, which is a stronger and stranger kind of safety.
The one attack that opens the front door itself is Shor's, structural, polynomial, and almost indifferent to key size. It breaks even a flawless key, and it waits on hardware that does not exist as of 2026, with no credible timeline [@shor-siam-1997]. So the most-likely eventual *structural* break of a good RSA key is not a classical factoring breakthrough at all. It is quantum, on a machine not yet built, and harvest-now-decrypt-later is what makes that future-tense sentence something to act on in the present [@gidney-2025].
The most-likely eventual break of a good RSA key is quantum, on a machine that has not been built. That is exactly why the forecast is actionable today.
The misconceptions this reframing overturns, "RSA is already broken," "a quantum computer just cracked it," "factoring is NP-hard," "a bigger key stops everything," deserve direct answers, which the questions below provide. This article asked how RSA *would* break. The answer is a two-speed map with a quantum horizon, and every road on it is now labeled.
## 12. Frequently asked questions
The claims below are the ones that come up most often, corrected against the evidence in this article.
No. A correctly generated RSA-2048 key with $e = 65537$, a full-size random `d`, independent primes, and OAEP padding has no applicable classical attack: the slow lane (GNFS) is astronomically far from a 2048-bit modulus, and every fast-lane attack needs a defect this key does not have [@boneh-survey-1999; @boudot-rsa250-2020]. RSA is not broken. It is a well-understood assumption with a known and distant classical threat, and a structural quantum threat that has no hardware yet.
No. Recurring headlines claim exactly this, and none has broken RSA-2048. No cryptographically relevant quantum computer exists as of 2026 [@gidney-2025]. The quantum result people most often conflate with a break, Grover's search algorithm, is only a quadratic speedup and is not a structural attack on RSA [@grover-1996]. The classical "shortcut" claims follow the same pattern as Schnorr's 2021 preprint, whose method produced zero usable relations at cryptographic size when implemented [@ducas-schnorrgate; @schneier-2021].
No, and this is the most common technical misconception. The decision version of factoring lies in the intersection of NP and co-NP, so it cannot be NP-complete unless NP equals co-NP, which is widely disbelieved [@hac-1996]. RSA does not inherit the difficulty of the hardest problems in NP. Its security rests on the specific, unproven belief that factoring is hard, not on a theorem [@hac-1996].
No. Shor's cost grows only polynomially in the number of digits of `N`, so doubling the modulus from 2048 to 4096 bits multiplies the quantum work by a small constant, not by the astronomical factor that same change imposes on classical factoring [@shor-siam-1997]. Key size defends only against the slow lane. Against the quantum threat, the answer is a different primitive, not a longer RSA key [@gidney-2025].
With correct OAEP padding, the low-exponent attacks lose their precondition, so $e = 3$ is not automatically fatal [@cfpr-1996; @rfc8017]. But $e = 65537$ is the safer default: it defeats the low-exponent family outright while staying cheap to compute, so a single padding mistake with $e = 3$ does not immediately reopen Hastad's broadcast or the stereotyped-message attack [@hastad-1988]. Choose the exponent that fails safe.
Those are out of scope for this article by design, because they are not breaks of RSA's mathematics. ROCA is a key-generation library defect, Bleichenbacher and Manger are padding oracles, FREAK is a protocol downgrade, and timing and fault attacks are physical side channels. Every one of them breaks the implementation or protocol around RSA, not the algorithm itself. They are the subject of the companion article, *How RSA Breaks in Real Life*.
Yes, but only for data with a long confidentiality lifetime. An attacker can record RSA-encrypted traffic now and decrypt it once a quantum computer exists [@gidney-2025]. If your secrets must stay protected for a decade or more, begin planning migration to post-quantum key-establishment even though no such machine exists today and no credible timeline can be given. For short-lived data, the classical picture in this article still governs.
The question this article opened with was not whether RSA is broken, but how it *would* break if it ever did. The evidence has drawn the map: a bolted front door that opens at a crawl, side windows a good key never leaves ajar, and a single quantum road to a machine still on the horizon.