DeepMind's RSA-1024 agents explained: 3.5x cheaper, and what's unproven

On November 6, Google DeepMind announced that its AI agents had found "two weaknesses" in legacy 1024-bit RSA, the old key size that much of the internet has spent a decade retiring. Trade coverage such as FourWeekMBA and Crypto Briefing repeated the headline. The two working papers behind the announcement are more careful than the headlines. One result was actually computed, one is a proof about how signing formats behave, and one is an estimate for a machine nobody has built. Knowing which is which is the whole story.

The plain-English version

Imagine a bank vault with a very large combination lock. Nobody knows the combination except the bank. But the bank offers a service: you hand a clerk any slip of paper, and they stamp it with the vault's secret stamp. Because only the bank can make that stamp, a stamped slip counts as a signature.

An attacker's dream is to forge the stamp on a slip the clerk would never agree to stamp. Cryptographers know a way to get there without ever learning the combination: collect a huge pile of stamped slips on harmless-looking requests (about four billion in the 2026 experiment), then mathematically combine them into a stamp for a brand-new slip. That is hard work. An academic team recently did it for a 1024-bit key and reported it cost about 1,380 "core-years", meaning one processor running for 1,380 years, which they spread over many machines for about five months.

Here is what DeepMind reports. First, two AI agents repeated that exact computation, using the same method, for 391 core-years, in 3.2 days using up to 300,000 processor cores. The paper says the saving came from better code, not a new idea.

Second, the clerk usually does not stamp raw slips. They wrap your text in a fixed envelope first. The new work proves that if you may fill about half of the envelope, the envelope barely helps: it is as if the clerk stamped anything. If you may fill only a quarter (like a short fingerprint of a document), the attack is harder, and the team offers a faster method, but only on paper.

Third, they claim a smarter way to attack many keys at once, again as a theoretical estimate.

The reassuring part is real: modern keys are 2048 bits or more, and the authors say these results do not threaten them. The unsettling part is the speed. The authors say AI moved a field that usually advances slowly, and that is the claim to watch.

How it actually works

RSA in one paragraph. A public number $N$ is the product of two secret primes. Anyone can "lock" a value by raising it to a public power $e$ modulo $N$. Undoing that, taking the $e$-th root, is easy with the primes and believed hard without them. Signing is exactly that hard step, done by the key's owner. The best known general way for an outsider to do it is to factor $N$ with the number field sieve, which for 1024 bits the authors estimate at 500,000 to 1,000,000 core-years.

The shortcut: use the signer as an oracle. In 2007, Joux, Naccache and Thomé asked a different question: if an attacker can temporarily query a device for $e$-th roots of numbers they choose, how much cheaper is the attack than factoring? In their model the attacker queries first, then the device is withdrawn, then the attacker must compute the root of a random target. The answer is "much cheaper", with a cost near the special number field sieve rather than the general one. In 2026, Shea, Haller, Suhl, Heninger and Thomé carried out the first full 1024-bit run, using about 4.07 billion queries.

The format problem. Real signers do not accept arbitrary numbers. They take your data and place it inside a fixed pattern, and the attacker only controls the data. So the oracle accepts only numbers of the form "fixed part $c$ plus a variable part $z$". This is the "affine" oracle. Earlier work expected this to be far less practical.

New idea one: the half-block threshold. DeepMind's paper proves that if the variable part can be as large as roughly the square root of $N$, the format constraint stops mattering. Two admissible inputs can be combined into a ratio that reaches any target. For a 1024-bit key, the block is 128 bytes, and PKCS#1 v1.5 allows up to 117 bytes of data. More than about 64 bytes, or a 64-byte digest, gives the attacker enough freedom. A 32-byte digest falls below the line.

New idea two: fans of number fields. The number field sieve finds relations between numbers, and a "factory" reuses a large precomputation across many targets. Until now, a precomputation costing about one factorization bought nothing: you were better off ignoring it. The second paper gives every target its own family, a "fan", of number fields, all drawing on the same stored data, which makes mid-sized precomputations worthwhile.

The deep dive

Complexity language

Both papers measure progress using

so an algorithm improves by lowering the constant $c$. The general number field sieve has $c_{GNFS}=(64/9)^{1/3}\approx 1.923$; the special number field sieve has $c_{SNFS}=(32/9)^{1/3}\approx 1.526$. Lowering $c$ by $\Delta$ saves a factor $L_N[1/3,\Delta]$, which grows faster than any power of $\ln N$. This is also why asymptotic claims are slippery: the $o(1)$ terms hide constants that can dominate at 1024 bits. Both papers say so explicitly.

Paper 1: the affine modular root problem

The model asks for $t^{1/e} \bmod N$ for random targets $t$, after an offline phase of non-adaptive queries to an oracle accepting $c+z$ with $|z|\le Z$.

The square-root threshold. The authors show that for every fixed $c$, an oracle with a window of $O(N^{1/2})$ offsets simulates the unrestricted oracle using two queries per query, after a constant number of re-randomisations on average. Writing a residue as a ratio $\rho = (c+z)/(c+z')$ is a closest-vector problem in a two-dimensional lattice of determinant $N$, and the root of $\rho$ is the quotient of two oracle answers. The statement is proved without heuristics down to $N^{1/2}$. At 1024 bits with a window of half the bits they measured 1.26 re-randomisations per query. Below $N^{1/2}$, a counting argument says the required re-randomisations multiply by four for every bit removed from the window.

The practical reading, from their classification of PKCS#11 mechanisms: raw maps and long data are unrestricted; a 64-byte digest at 1024 bits sits at the threshold; a 32-byte digest is a genuine affine problem; a digest computed inside the device is outside the model. Because the property belongs to the format, it holds "for every correct implementation of it", as the discussion section puts it.

A faster affine algorithm. For the genuine affine case, the old algorithm cost $L[6^{1/3}]\approx L[1.8171]$ per root because the initialisation of the descent was paid per target. The new method costs $L[0.9602]$ queries, offline $L[1.5803]$ and online $L[1.5803]$ per root. With a larger offline phase $L[1.5930]$ the online cost drops to $L[c_{SNFS}]$, and with $L[1.6373]$ it approaches $L[(8/3)^{1/3}]=L[1.3867]$. The gains come from optimal multi-stage early-abort smoothness testing. A candidate is discarded as soon as the smooth part found so far is too small. For $s$ stages the cost is

where $C_s$ is the largest left Riemann sum of $r^2$ on $s$ intervals of $[0,1]$, and $C_s\to 1/3$ so the cost tends to $L[(4y/3)^{1/3}]$. The paper adds a factor-base extension using only admissible inputs. Importantly, the offline exponent never falls below $c_{SNFS}$, and the authors state they did not run this algorithm at cryptographic size, because the number fields of degree two or more that a generic $c$ requires make the offline phase far more expensive. The "~1,600x" figure comes from DeepMind's announcement, which calls it a theoretical estimate for forging signatures over 32-byte digests. We could not find that number in the paper itself; it presumably reflects the exponent drop from $1.8171$ to $1.5803$ at leading order, and the paper flags that result as asymptotic and not run at this size.

The 1024-bit computation

This is the measured result. Same modulus, same polynomials, same factor-base bounds as the earlier study, implemented in C++ on top of CADO-NFS with $e=65537$.

Both numbers come from the authors; the comparison uses costs the earlier team reported on different hardware. The paper bounds that caveat with a same-machine test of the siever (1.8 to 4.4 times faster than CADO-NFS, finding the same relations), which accounts for about 90% of the saving. Stage-wise savings were 2.7x and 4.0x in the two sieving stages, 2.2x in the descent and about 6x in root extraction. The authors state the factor of 3.5 is "one of implementation and execution, not of algorithms". They also compute that once the offline work is done, additional roots cost 0.007% to 0.015% of factoring, so computing roots for fewer than roughly 6,800 to 13,600 targets beats factoring the modulus.

Paper 2: Fan Factories

Coppersmith's factory spends $L[2.007]$ once on the rational side of the sieve, then $L[1.639]$ per integer. With a budget near one factorization, the best known per-integer cost was Coppersmith's MNFS at $c_{MNFS}=\big((92+26\sqrt{13})/27\big)^{1/3}\approx1.9019$, unchanged since 1993. The new construction gives each target a fan of $L[\tau]$ algebraic polynomials, all tested against the same stored pairs. The authors solve for the minimum per-target exponent at every precomputation budget in closed form. For a budget of one factorization, the per-integer exponent is $L[1.793]$. The improvement holds for budget exponents strictly between 1.902 and $(2401/324)^{1/3}\approx1.950$; above that, one field per integer is optimal. For batches factored together with no precomputation, the gain is at most 0.018 in the exponent, or at most 1.75x. The headline "1/58 of the cost, 30x below MNFS" is explicitly at leading order with $o(1)$ terms set to zero, and no fan factory has been implemented. The algebraic identities and feasibility witnesses are machine-checked in Lean 4.

The agent setup

For the computation, a supervisor model wrote the design, set checkpoints and audited results while an executor model wrote the code and ran jobs. The agents wrote about 33,500 lines of new code, ran 336 distributed experiments, and fixed failures that a rehearsal missed, including descent nodes of 82 to 85 bits that the siever abandoned and a 32-bit index overflow that had made the first computed root wrong. The human researcher sent about twenty short messages, mostly approvals. For the factoring paper, one model generated proofs and a second verified them.

Why it matters

For everyday users: nothing breaks today. Web traffic, banking and messaging overwhelmingly use 2048-bit or larger keys, and the authors say these are unaffected. NIST already limits 1024-bit RSA to verifying existing signatures, and DKIM email signing, according to one analysis citing RFC 8301, still tolerates 1024-bit keys while recommending 2048.

For developers and security teams: the sharpest lesson is about interfaces, not key sizes. The half-block threshold says that an API letting a caller choose a large part of the signed block hands them an oracle regardless of how carefully the padding is implemented. The practical hygiene is to hash inside the device, avoid raw modes, and retire 1024-bit keys, especially in hardware security modules and smart cards reachable by untrusted callers. The attack needs billions of queries, which is also something rate limits and monitoring can notice.

For companies: the cost to a determined attacker with a large cluster dropped by a factor of a few. Defensive planning should not hinge on the headline ratios, but legacy 1024-bit systems that remained out of inertia have a less comfortable story.

For the field: two points. First, a reproduction that took five months by an academic team took 3.2 days once agents handled the engineering at 300,000 cores, though most of that difference is parallelism, per the paper. Second, the agents built machine-checkable proofs. If this pattern holds, the cadence of cryptanalytic improvement may speed up, which strengthens the case for planning key-size and format transitions earlier. The authors say as much in the paper's outlook.

What to be skeptical of

• Three grades of evidence, one headline. Only the 391 core-year run was executed at 1024 bits. The ~1,600x signature figure appears as a theoretical estimate in the announcement and is described in the paper as asymptotic and not run. The ~30x batch figure is a leading-order estimate with the $o(1)$ terms dropped, and nothing was built.
• The 3.5x is mostly engineering. The authors themselves attribute it to code, not algorithms. Their comparison also uses costs reported on other hardware, though they bound the effect with a same-machine siever test.
• "Found by AI" is partly framing. The attack algorithm dates to Joux, Naccache and Thomé in 2007 and the 1024-bit target and parameters came from the earlier team. The agents' credited contribution is execution and proofs, and a human directed the work with Heninger and Thomé, who wrote the original attack, among the authors. That makes them informed collaborators rather than independent reviewers.
• Not peer-reviewed or replicated. Both are working papers. We found no independent cryptographer assessment as of November 8, and the coverage we read relied on DeepMind's own materials, with at least one outlet saying so openly.
• Threat model is narrow. The attack needs direct, caller-controlled calls to a signing interface, about four billion of them, all chosen before the target is known. Devices that hash internally are out of scope.
• Asymptotics at 1024 bits are shaky. Both papers say hidden $o(1)$ factors are not determined by the analysis.

What to watch next

• Peer review and outside replication of the 391 core-year computation, and of the same-machine siever speed-ups, in the CADO-NFS community.
• Whether anyone runs the affine algorithm or builds a fan factory at a real size. The authors list making the affine offline phase practical as the main open problem.
• Vendor responses from HSM and smart-card makers on whether any product exposes a caller-controlled interface above the half-block threshold, and any guidance from NIST or standards bodies on formats.
• The 1024-bit tail: watch for further moves to disallow or flag 1024-bit signing keys in email and certificate ecosystems.
• Follow-on AI-for-mathematics results. Our earlier coverage of OpenAI's Lean-checked maths papers and the ETH disproof shows the same pattern of machine-checked claims, and Anthropic's quantum circuit work sits nearby.
• Related offensive-AI context in OpenAI's 948 Linux root exploits for how agents are changing the cost of security research.

How this was made: researched and written by an AI model (Claude) from the primary sources listed above, then checked claim-by-claim against those sources in a separate AI fact-check pass. Spotted an error? Email [email protected] and we correct it publicly. Our process.