How RSA Would Break: Why Factoring Is the Slow Path and Coppersmith Is the Fast One

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.

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.

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 ^[5]. Rivest, Shamir, and Adleman supplied the lock ^[6].

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 ^{[7, 8]}.

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 ^[6]. 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.

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 ^[9]. 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 ^[10], and his rho method (1975), which finds a small factor p in about $O(p^{1/2})$ steps using almost no memory ^[11]. 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 ^[12]. 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]$ ^[13]. 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 ^[14].

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.

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 ^{[15, 18]}. 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 ^{[1, 19]}. ※ 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 ^[20]. 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" ^[8]. 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 ^[10]. 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 ^[21]. 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 ^[23].

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$ ^[25].

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 ^[25].

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 ^[26]. 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) ^[26].

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 ^[27]. 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.

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 ^[29]. 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 ^[29]. 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"]

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 ^[27]. 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}$ ^[27]. 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 ^{[27, 28]}. 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 ^[30]. 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 ^[30]. Both need a small e and a short or structured relationship between messages. OAEP'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 ^[31]. 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 ^[32]. 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 ^[33]. 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 ^{[34, 35]}, and Coppersmith's small-root method is a single function call, small_roots(), in SageMath ^[36]. The barrier to using them is never the tooling. It is finding a key with a precondition to attack.

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.

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.

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 ^{[2, 37]}. 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.

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 ^[14]. 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 ^[27]. 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 ^{[38, 3]}.

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" ^[39]. 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 ^[39].

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 ^[40].

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 ^[41]. 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]$ ^[14]. On a quantum computer, Shor's algorithm factors in time polynomial in the number of digits of N, an exponential improvement ^[3].

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 ^[3]. 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"]

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 ^[42]. 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 ^[4].

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 ^[4]. No cryptographically relevant quantum computer exists as of 2026.

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.

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 ^{[14, 15]}. 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 ^{[40, 41]}. 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}$ ^[33]. 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 ^[28]. Nobody knows where the real boundary lies.

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.

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.

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 ^[44]. 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.

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.

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.

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 ^{[15, 1]}. 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 ^{[2, 37]}. 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 ^[3]. 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 ^[4].

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.

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.