DeepMind’s agents, with cryptographers, cheapen two attacks on legacy 1024-bit RSA
Pushmeet Kohli’s essay, posted Friday, and two working papers separate three figures that do not describe the same experiment. A rerun of a published 1024-bit computation used 391 core-years, 3.5 times less CPU than the earlier run. A theoretical estimate for a harder signature case is about 1,600 times. Batch factoring of further 1024-bit integers is about 30 times cheaper than an older method, at leading order. Both papers say 2048-bit RSA in use today is not threatened.
Deep dive6 minIn-depth
Priya Shah6 min read
- Google DeepMind
- RSA
- Cryptography
- Agents

Photo: Google DeepMind / Pushmeet KohliSource page
Google DeepMind on Friday published two working papers, and an essay by Pushmeet Kohli, on attacks against 1024-bit RSA, the key length the industry has been retiring for years. Kohli, DeepMind’s vice president of science, posted the essay on X at 17:07 UTC. He writes that AI agents, guided by people, found two weaknesses, and that the results “only affect obsolete 1024-bit RSA systems.” Modern protocols, he writes, “almost universally use 2048-bit or larger keys” and “remain secure.” Both papers carry a box to the same effect: the results do not threaten deployed systems based on 2048-bit and larger RSA. The papers do not name the models.
The work is led, in Kohli’s account, by Dj Dvijotham and Abhradeep Thakurta, with Nadia Heninger and Emmanuel Thomé. The papers list those four among a longer set of authors. A footnote says Heninger is also at UC San Diego and Inria, and Thomé is at Inria. Kohli is an author of both papers. The factoring paper is dated 5 November. The signature paper is marked only as a working paper. Kohli’s essay links both PDFs.
Three numbers, three different claims
The figures in the essay are easy to stack into one “faster attack.” They are not one experiment. The 3.5 times is a measured rerun of a computation that had already been done, with the same algorithm. The roughly 1,600 times is Kohli’s theoretical estimate for a harder signature problem, not a clock on that rerun. The about 30 times is a leading-order comparison for factoring further 1024-bit integers after a shared preparation, against an older batch method, and the factoring paper says the identities behind it were checked in Lean while the running-time claims still use the usual heuristics of the number field sieve.
What was measured
The signature paper’s experiment reproduces a 1024-bit instance published by Shea, Haller, Suhl, Heninger and Thomé, using what the paper calls an unrestricted oracle: a signer that will return a root for any residue it is given, then goes away. With the same algorithm, polynomials and bounds, the first root took 391 CPU core-years, against 1,380 in the earlier computation, which the paper splits as about 1,200 offline and 180 online. That is the 3.5 times. The paper says the factor is one of implementation and execution, not a new algorithm. It estimates that factoring the same modulus would take 500,000 to 1,000,000 core-years, which is the comparison behind Kohli’s line that the run used less than a thousandth of the computing power needed to break the key itself.
Two agents designed, ran and debugged that computation. The abstract says they did it in under four days. The body is more specific and less flattering to the calendar. From the first full-scale sieving job, the run took 3.2 days, on peaks of about 300,000 CPU cores and 16 GPUs, against about five months for the earlier computation. The paper says that gap is mostly parallelism — an average of about 45,000 cores busy, against about 3,300 — and that it does not count the shorter calendar as an efficiency gain. A human sent about twenty short messages, most of them approvals. The agents wrote about 33,500 lines of new code and launched 336 distributed experiments. The paper describes a supervisor model that set the design and checked results, and an executor that wrote code and fixed failures during the run. It does not say which models those were.
Padding, and how much of the block the caller holds
The cryptanalytic claim is about signatures that pad a message into a fixed block before applying the RSA secret map. Kohli’s essay says that once an attacker controls roughly half the signed block or more, “padding adds no protection at all,” and forging a signature is as exposed to shortcuts as using no padding. The paper’s version is a threshold. For a fixed format, once the caller-controlled part can be any integer up to roughly the square root of the modulus, the format stops making the problem harder than the unrestricted oracle. For the PKCS#1 v1.5 format used by the PKCS#11 mechanism CKM_RSA_PKCS, the paper says that is more than about half a block of data. A 64-byte digest at 1024 bits — 512 bits, half the block — sits at that line. The paper says this case is about two bits under the theorem’s bound, and that in measurements on random 1024-bit moduli a window of exactly half the bits succeeded on 79.6 percent of draws, so a query cost 1.26 draws on average. A 32-byte digest, it says, is a harder problem, called the affine modular root problem, and is not covered by that reduction.
The measured 391 core-years are the unrestricted instance. The paper says the half-block result means the same computation also applies to a formatted signature in which the caller controls about half the block. It is not a report of a signature forged on a live service. Kohli writes that the test was a sandboxed simulation on an already-solved benchmark key, “without touching any live systems.”
For the harder case, the paper lowers the cost of one root, preparation included, from the older estimate L_N[1/3, 1.8171] to L_N[1/3, 1.5803]. With a larger preparation, still described as far below the cost of factoring, the online cost per root approaches L_N[1/3, 1.3867]. Kohli’s essay says that for a short 32-byte fingerprint, a new algorithm improves on the previous best method by roughly 1,600 times for 1024-bit keys, “according to our theoretical estimates.” The paper states the change in the exponent. It does not print 1,600. That multiple is the essay’s reading of the estimate at 1024 bits, not a second measured run.
Factoring many keys of one length
The second paper is about sharing work when many integers of the same size have to be factored. The number field sieve factors one integer in heuristic time L_N[1/3, c] with c about 1.923. Coppersmith’s multiple number field sieve, which needs no shared preparation, has stood at about 1.902 per integer since 1993, the paper says. The new construction gives each integer its own family of number fields, a “fan,” fed by one shared rational side. With a preparation budget equal to one factorization, each further integer costs L_N[1/3, 1.793]. At leading order — the paper says it sets the lower-order terms to zero — that preparation lets each further 1024-bit integer be factored at about 1/58 the cost of a full sieve, and 30 times less than with the multiple number field sieve. Kohli’s essay shortens this to about 30 times against previous batch methods, for each additional 1024-bit key out of many.
The paper says the results use the standard heuristics of sieve analysis, and that the algebraic identities and the exact feasibility witnesses were machine-checked in Lean 4. It also says the results were obtained with a two-agent harness: one model generated the proofs, and a second model verified them. It does not name the models, and it does not report a measured factoring of a batch of 1024-bit keys at that 30-times ratio. The 30 times is the leading-order comparison. The same boxed warning applies: deployed 2048-bit and larger RSA is not what the paper says it has made cheaper to break.


