AI agents reproduce 1024-bit RSA attack at lower CPU cost

By Sophie Lindqvist

Google DeepMind says two AI agents reproduced a 1024-bit RSA signature attack in under four days, cutting CPU time to 391 core-years from the academic team’s 1,380. Pushmeet Kohli, Google DeepMind’s VP of research, presented the result Friday in an essay on X, alongside a second paper that lowers the theoretical cost of factoring old RSA keys in bulk.

Kohli set a firm boundary: “In practice, these results only affect obsolete 1024-bit RSA systems, and modern encryption protocols, which almost universally use 2048-bit or larger keys, remain secure.” The limit keeps the immediate target on obsolete systems rather than routine 2048-bit-or-larger deployments.

The first paper says current guidance already rejects 1024-bit RSA for signatures. That distinction matters because this work attacks a signing setup and its cost estimates, not the safety of modern RSA generally.

DeepMind credits Dj Dvijotham and Abhradeep Thakurta with leading the work. Cryptographers Nadia Heninger of UC San Diego and Inria and Emmanuel Thomé of Inria also co-authored it.

How did two agents reproduce the attack?

The benchmark was a 1024-bit instance attacked by Laura Shea, Miro Haller, Adam Suhl, Heninger and Thomé. Their paper appeared on the IACR ePrint archive in September and used a hardware security module as a signing oracle.

The earlier team spent 1,380 CPU core-years over five calendar months. DeepMind’s agents used the same algorithm, polynomials and bounds, but computed the first root in 391 core-years.

The models split the engineering work. One acted as supervisor, writing the design, setting checks for each stage and auditing results. The other wrote and ran the code, then repaired failures.

DeepMind reports that the pair generated about 33,500 lines of new code and launched 336 distributed experiments. The run peaked at roughly 300,000 CPU cores and 16 GPUs, with a human researcher sending about 20 short messages.

Most human replies were approvals, including “follow your recommendation” and “continue.” The agents also had to diagnose a 32-bit index overflow. The paper says the bug made the first computed root wrong.

DeepMind’s paper attributes the lower compute cost mainly to the code rather than the hardware. It also says the much shorter calendar time “reflects mainly parallelism.” The speedup came from better engineering and heavy parallelization, not a new break against modern RSA.

Where does the signing attack apply?

The first working paper asks how much PKCS#1 v1.5 padding protects a key when an attacker can submit chosen data to a signing device. The target could be a hardware security module, which accepts attacker-chosen data and returns a signature.

The analysis turns on control of the 128 bytes in a 1024-bit block. Through the PKCS#11 mechanism CKM_RSA_PKCS, a caller who controls 65 bytes faces a problem no harder than raw, unpadded signing, the authors found.

Their measurements found that a 64-byte digest such as SHA-512 behaved about the same as the raw-signing case. A 32-byte digest such as SHA-256 leaves a harder problem.

Kohli wrote that a new algorithm improves on the previous best method by roughly 1,600 times at 1024 bits, according to DeepMind’s theoretical estimates. The paper says that result is asymptotic and that the authors did not run the new algorithm at that size. The reproduced attack used the earlier method.

The threat model has sharp edges. Mechanisms that hash a message inside the device, including CKM_SHA256_RSA_PKCS, do not let the caller choose the block. The authors place those mechanisms outside both attack models.

An attacker also needs direct calls to the signing interface. The reproduced computation required about 4 billion such calls, and the paper says all of them happened before the target was known.

Those constraints limit the attack to aging systems with an exposed signing interface. The immediate target is obsolete 1024-bit signing deployments, not modern 2048-bit RSA.

What does the bulk-factoring shortcut change?

The second paper, dated Thursday, addresses attackers who want to factor many keys of the same size. Its proposed method remains on paper and has not been implemented.

The starting point is shared precomputation costing about one factorization. Since 1993, Coppersmith’s multiple number field sieve has set the best known cost for each additional integer in that setting, according to the paper.

DeepMind’s proposed “fan factory” gives every target its own family of number fields, all fed by the shared work. At leading order, each further 1024-bit integer would cost about 1/58 of a standard number field sieve run.

The paper says that would make each additional factorization 30 times less costly than Coppersmith’s method. The estimate applies to keys of the same size and depends on the shared work costing roughly one standard factorization.

The proof process also used AI. One model generated the proofs and a second checked them. The authors then machine-checked the algebraic identities in Lean 4.

The authors say no fan factory has been implemented. The bulk-factoring shortcut therefore remains a theoretical result, not a working attack.

What do these findings mean for RSA security?

The September ePrint paper had already extended the signing-oracle concern beyond 1024-bit keys. With access to a signing oracle, its authors concluded that RSA’s concrete security should be 15 to 30 bits lower than factoring-based estimates for keys from 1024 to 4096 bits.

Their conclusion was blunt: “Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model.”

That statement depends on the attack model. The attacker needs chosen data and direct access to the signing interface; the reproduced 1024-bit case required about 4 billion calls.

The agent result adds an engineering dimension to AI cryptanalysis. DeepMind’s reproduction shows two models handling code, validation and massive parallel computation after roughly 20 human messages.

The separate bulk-factoring paper points in another direction. Instead of reproducing a known attack, its models generated and checked a new algebraic construction that could lower the cost of repeated factoring.

For defenders, the immediate policy issue is whether obsolete 1024-bit signing deployments expose a signing oracle. Kohli says modern 2048-bit-or-larger systems remain secure, even as the research reduces theoretical security margins.

Until then, the 30-fold advantage remains theoretical, while the 1024-bit signing result has already run. A working fan factory would be the next step, because the authors have not implemented one.