Notes from Việt Nam on law, technology, languages, history, culture and travel.

DeepMind’s AI Agents Take a Swing at 1024-bit RSA: What the Two Papers Actually Show

For most of this year the story of “AI meets cryptanalysis” has been about raw factoring records. In September, Cognition researcher Eric Lu used the company’s Devin agent to build a GPU number-field-sieve pipeline and factor the 862-bit RSA-260 challenge number; sixteen days later Stephen A. Weis, a member of technical staff at Anthropic, reported factoring the 896-bit RSA-896 with Claude porting CADO-NFS to GPUs. Both runs were engineering feats rather than new mathematics.

Google DeepMind’s contribution this week is different in kind. On 5–6 November 2026, DeepMind’s VP of science Pushmeet Kohli announced two working papers on legacy 1024-bit RSA, co-authored by DeepMind researchers (led by Krishnamurthy “Dj” Dvijotham and Abhradeep Thakurta) together with two of the best-known names in practical cryptanalysis, Nadia Heninger (UC San Diego, Inria) and Emmanuel Thomé (Inria, a lead developer of CADO-NFS). One paper contains a new algorithm and a full-scale computation run almost entirely by AI agents; the other is a new asymptotic result about factoring many keys at once, with its algebra machine-checked in Lean 4.

Both papers open with the same boxed warning: the results “don’t threaten deployed cryptosystems today that are based on 2048-bit and larger RSA.” That sentence matters, because the headline number circulating on social media — “1,600× faster” — needs a lot of unpacking.

Paper 1: forging signatures with a restricted oracle

The first paper, Modular Roots from a Restricted Oracle: Faster Affine Roots and a 1024-bit Computation, studies a scenario from a 2007 paper by Joux, Naccache and Thomé. An attacker gets temporary access to a signing device — an oracle that will compute RSA e-th roots (i.e. signatures) of inputs the attacker chooses. Later the oracle is gone, and the attacker must sign fresh, random messages on their own. This is much cheaper than factoring the modulus: you never recover the private key, you just collect enough signed “building blocks” to assemble new signatures.

There are two flavours of oracle. An unrestricted oracle signs anything (in PKCS#11 terms, the raw CKM_RSA_X_509 mechanism). An affine oracle only signs inputs of a fixed format with a small caller-controlled part — which is how real signing interfaces work: the device applies PKCS#1 v1.5 padding around the data you hand it.

The paper has three results:

  1. When padding stops mattering. The authors prove that once the caller controls roughly half the bits of the input (about √N possible values), the affine oracle can simulate the unrestricted one at a cost of two queries per query. Concretely, for CKM_RSA_PKCS at 1024 bits, supplying more than about half a block of data — or a 64-byte digest — gives the attacker nothing harder than the raw-RSA case. A 32-byte digest (e.g. SHA-256) falls below the threshold. Devices that hash the message internally are outside both models entirely.
  2. A faster algorithm for the hard (affine) case. The cost per forged signature drops from LN[1/3, 1.8171] to LN[1/3, 1.5803], with a further trade-off that can push online cost toward LN[1/3, 1.3867]. The gains come from optimal multi-stage “early abort” smoothness testing and a smarter factor base. This is where the 1,600× comes from: plugging the exponent drop into the L-notation at 1024 bits with the o(1) terms set to zero gives a factor of roughly 1,600. Kohli’s announcement is careful to say “according to our theoretical estimates”; the paper never ran the affine algorithm at any cryptographic size and lists making it practical as the main open problem.
  3. A real 1024-bit computation. This is the part that actually ran. The agents reproduced the 2026 computation by Shea, Haller, Suhl, Heninger and Thomé, which used the unrestricted oracle against a 1024-bit modulus. With the same algorithm, polynomials and bounds, the first forged root cost 391 CPU core-years (318 offline, 73 online) against 1,380 in the original — 3.5× less CPU time. The authors explicitly attribute this to “implementation and execution, not … algorithms”: their optimized siever is 1.8–4.4× faster than stock CADO-NFS on the same machine. For comparison, factoring that modulus outright is estimated at 500,000 to 1,000,000 core-years.

The agent setup is the real story for developers

Section 6 of the paper reads like a case study in agentic software engineering. Two language-model agents (the paper calls them only “Model A” and “Model B”) split the work:

  • Model A, the supervisor, wrote the design document, set per-stage CPU and memory budgets, defined the checks each stage had to pass, audited every result and made go/no-go calls. It spun up a specialist sub-agent for one task, a 5× speed-up of the block Wiedemann linear-generator step.
  • Model B, the executor, wrote and tested code, launched and monitored distributed jobs and fixed failures.
  • The human researcher set the goal and approved irreversible steps — about 20 messages, mostly “follow your recommendation” and “continue”.

The numbers: 33,500 lines of new code (24,000 of C++/CUDA, 8,400 of Python), 336 distributed experiments, 16,292 tool calls, 218 agent-to-agent messages, peaks of about 300,000 CPU cores and 16 GPUs, and 3.2 days from the first full-scale sieving job to a verified root (versus about five months for the original). The workflow was gated: every stage ran first on a probe or a 1% canary slice, and the one-shot oracle batch could not start until all pre-agreed checks passed. The agents caught and fixed problems a small rehearsal could not reveal, including a 32-bit index overflow that made the first computed root wrong.

If you build CI pipelines or run large batch jobs, that pattern — written design, budgets, canaries, an auditor separate from the doer, a human only at irreversible gates — is the transferable lesson, independent of the cryptography.

Paper 2: “fan factories” for batch factoring

The second paper, Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS (dated 5 November), asks what happens when an attacker wants to factor many RSA keys of the same size. Coppersmith’s “factorization factory” already lets you precompute the rational side of the sieve once and reuse it — but only with a very large up-front budget. With a budget of about one ordinary factorization, the best per-key method since 1993 has been Coppersmith’s multiple number field sieve (MNFS).

The new idea gives every target key its own fan of number fields, all fed by the shared precomputation. With a one-factorization budget, each further key costs L[1/3, 1.793] instead of 1.902. At 1024 bits and leading order, that means each additional key costs about 1/58 of a normal NFS factorization — 30 times less than MNFS. Batching keys without any precomputation helps only marginally (at most about 1.75×).

Two caveats are in the paper itself: “no fan factory has been implemented,” and the figures ignore lower-order terms. The proofs were produced by a two-agent harness — one model generating, another verifying — with the algebraic identities checked in Lean 4.

Why it matters, and what to be sceptical about

For security teams, nothing here breaks RSA-2048. NIST has disallowed RSA keys under 2048 bits for new signatures for years, but 1024-bit keys linger in DKIM records, old HSM configurations, embedded firmware signing and legacy PKI. The practical takeaways are narrow but real: an HSM that exposes raw RSA or PKCS#1 v1.5 signing over caller-supplied data or 64-byte digests on a 1024-bit key is in the threat model that just got 3.5× cheaper in practice; billions of signing queries (the 1024-bit run made about 4 × 10⁹) are required, which rate limits and logging should catch.

For the AI field, the significance is the speed of the research loop. A field where constants in L-notation move once a decade saw two new asymptotic improvements and a record-class computation land together, with agents doing the engineering and drafting proofs under expert supervision. That is a stronger claim than “AI factored a big number,” and a more consequential one.

Open questions remain. These are non-peer-reviewed working papers; the 1,600× and 1/58 figures are leading-order estimates with o(1) dropped, which at 1024 bits can move results by large factors; the agent models are not named, so the setup cannot be replicated; and the measured 3.5× is about better code and parallelism on Google-scale infrastructure. The honest summary is the one the authors give: the work sharpens our picture of what older signature standards can resist — and shows how fast AI-assisted research can now move.

Sources