Zhidx (WeChat official account: zhidxcom)
Author | Sun Xiaowen
Editor | Cheng Qian
Zhidx reported on November 10 that on November 7, Pushmeet Kohli, vice president of Google DeepMind, disclosed two AI-assisted cryptanalysis findings on the social platform X. Under the guidance of human researchers, AI agents found two improved attack paths against legacy 1024-bit RSA cryptosystems. In particular, two AI agents reproduced in less than four days a computational experiment that a previous research team had taken roughly five months to complete, reducing CPU computation from about 1,380 core-years to 391 core-years—a decrease of approximately 72%.
▲Google DeepMind’s official announcement (Source: X)
▲Comparison of the CPU costs of the previous experiment and the AI reproduction; GPU costs are additional (Source: Google DeepMind paper)
The study shows that AI agents can already take on a large amount of complex software development and computational work in cryptographic research, and help researchers find attack paths that require less computation.
RSA is like a lock on the internet and also like an anti-counterfeiting seal. It can help protect information and verify whether a file came from a trusted source. For example, when a computer downloads a software update, it checks the digital signature provided by the vendor to make sure the installation package has not been swapped out.
The way RSA works relies on a mathematical challenge: multiplying two large primes is easy, but if you know only the product, it is much harder to work backward to the original two primes.
Attackers who want to forge an RSA signature can try two routes. One is to factor the product, recover the private key, and generate a signature themselves; the other is to skip the private-key recovery step and use mathematics to forge a signature that passes verification. This time, Google DeepMind approached these two directions separately and improved the corresponding attack methods.
Batch integer factorization: The team proposed the Fan Factories algorithm, which allows multiple targets of the same bit length to share results from the earlier stages of computation. The paper estimates that after an upfront investment roughly equivalent to the computational cost of one general number field sieve factorization, the theoretical cost for each subsequent 1024-bit target can be reduced to about 1/30 of that of the previous best method. Under the same precomputation budget, this is the first improvement since 1993 to the best-known theoretical cost per subsequent target.
▲Comparison of the theoretical costs of the two algorithms under the same precomputation budget (Source: Google DeepMind paper)
Digital signature forgery: The team found that when an attacker can control about half of the input content, fixed padding no longer increases the computational difficulty of such attacks. Some RSA signature standards incorporate predetermined content—known as “padding”—to limit the inputs that callers can choose themselves. The study found that if an attacker can temporarily invoke a specific signing interface and control roughly half or more of a data block, they can forge a signature using the same mathematical method as in the unpadded case.
When the controllable portion is smaller—for example, when it is only a 32-byte digest—the team also proposed a new algorithm. The theoretical estimate at the 1024-bit scale puts its computational cost at about 1/1,600 of that of the previous best method.
The study was led by Dj Dvijotham and Abhradeep Thakurta of Google DeepMind, in collaboration with cryptographers from the University of California, San Diego, and Inria, the French National Institute for Research in Digital Science and Technology. The team has now published two working papers, one on modular root extraction under restricted signing interfaces and the other on batch integer factorization under shared precomputation.
In practical use, 1024-bit RSA has been phased out of mainstream website certificate systems.Currently, most publicly trusted websites require TLS certificates to use RSA keys of at least 2048 bits. However, for compatibility reasons, some products still retain the 1024-bit option, including Google Workspace and email-signing services such as Amazon AWS SES.
I. Two parallel paths: Google DeepMind dramatically reduces the cost of 1024-bit RSA attacks
This Google DeepMind study addresses “digital signature forgery” and “batch integer factorization.”
1. Digital signature forgery: Two AI agents reproduce the experiment in under four days, reducing CPU computation by about 72%
In the signing experiment, researchers first had the AI agents complete preliminary data preparation and query a simulated signing interface. After the interface was closed, valid signatures were generated for new, previously unknown targets.
In the initial phase, a program written by the AI agents selected its own inputs, made approximately 4.06 billion queries to the interface, saved the returned results, and organized mathematical relationships for later use. Researchers then closed the interface and generated previously unknown random targets. The program subsequently used the existing algorithm and saved data to complete the signature computations for the new targets.
To test the computational efficiency of the AI agents, Google DeepMind used the same 1024-bit instance, mathematical algorithm, and key parameters as the previous work, and had the AI agents rewrite and optimize the computational program.
The two principal agents were responsible for supervision and execution. The “supervisor agent” was responsible for devising the plan and budget and defining review requirements, while the “executor agent” wrote code, ran tasks, and troubleshot issues. Human researchers set the objectives and key conditions and sent approximately 20 messages during the process, most of them to approve operations.
▲Division of tasks between the supervisor agent and the executor agent (Image source: Google DeepMind paper)
The entire experiment took 3 days and 22 hours. The two AI agents newly wrote approximately 33,500 lines of code and conducted 336 distributed computing experiments. During the process, the agents also found and fixed a 32-bit index overflow issue, allowing the computational results to ultimately pass validation.
On the same 1024-bit instance, the CPU computation for this experiment fell from approximately 1,380 CPU core-years in previous work to 391 CPU core-years, a reduction of approximately 72%.
▲Task execution record for the 1024-bit RSA computation experiment (Image source: Google DeepMind paper)
In reducing computational overhead, the AI agents focused on optimizing the screening stage. The experiment needed to examine large numbers of candidates to identify mathematical relationships that could be used for subsequent root finding, a process that consumed substantial CPU resources. The technical report states that approximately 90% of the CPU-computation savings came from optimizing the screening programs.
On the same machine with identical parameters, the optimized core screening program ran approximately 1.8–1.9 times as fast as the original program, while the second-stage screening program ran approximately 3.4–4.4 times as fast as the original. This preliminary preparation consumed approximately 318 CPU core-years, while computation for the new targets consumed approximately 73 CPU core-years.
▲Comparison of the CPU costs of preliminary preparation and new-target computation; SHS+26 represents the previous experiment (Image source: Google DeepMind paper)
To shorten the timeline, Google DeepMind researchers also expanded the scale of parallel computation, using a peak of approximately 300,000 CPU cores and 16 GPUs. The paper primarily attributes the difference between a duration of approximately five months and one of less than four days to the difference in parallel scale. GPU computing costs were counted separately.
2. Batch integer factorization: Improved precomputation utilization reduces the theoretical cost of each subsequent target to approximately 1/30
For multiple RSA integers of the same bit length, traditional methods can first complete an expensive precomputation and then use the results for different targets, thereby sharing the computational cost. Such an approach is called a “factorization factory.”
The traditional factoring factory assigns one number field to each target and requires substantial upfront investment to fully realize its advantages. If the precomputation budget is equivalent to only one general number field sieve factorization, a traditional factoring factory cannot be faster than the general number field sieve. Under this budget, researchers’ best previous option was still to run the multiple number field sieve method proposed in 1993 separately for each target.
The Fan Factories algorithm proposed by Google DeepMind assigns multiple number fields to each target, improving the utilization of the same batch of precomputation results. The algorithm checks for shared results across different number fields. A result that cannot form a valid relation in one number field may still be useful in another; the algorithm then aggregates the relations obtained for the same target to complete the subsequent factorization.
The paper estimates that after an initial computational cost equivalent to approximately one general number field sieve factorization, the theoretical cost for each subsequent 1024-bit target can be reduced to about 1/30 of that of the previous best method.
Even when precomputation is included in the total cost, the paper’s theoretical estimates show that the new method costs less than running the previous multiple number field sieve separately when processing at least three 1024-bit targets. Under the same precomputation budget, this result marks the first reduction since 1993 in the optimal theoretical cost of factoring subsequent individual targets, which had not been improved since then.
▲Under a precomputation budget equivalent to one general number field sieve factorization, the optimal theoretical factoring cost for each subsequent individual target has fallen for the first time since 1993. Estimated at the 1024-bit scale, Fan Factories reduces this cost to about 1/30 of that of the previous method (Image source: Google DeepMind paper)
II. AI development aids progress as multiple RSA studies advance this year along two separate attack paths
In the past, RSA cryptanalysis required enormous computational resources. This year, several AI companies have joined the research effort, using agents to optimize GPU programs and schedule computing resources, reduce computational costs, and achieve successive new advances.
On September 9, Cognition used its AI coding agent Devin to complete the approximately 862-bit RSA-260 factorization through the integer factorization route. Devin helped convert an existing computational program into a GPU implementation. According to a technical article published by Cognition, extrapolating from the 2020 RSA-250 experiment, the estimated cost of the new GPU implementation at the same factorization scale was about 1/10 that of the previous CPU implementation. RSA-260 also became the largest RSA challenge to have been publicly factored at the time.
On September 19, Anthropic researcher Stephen Weis used the company’s large language model Claude to complete the factorization of an 896-bit RSA integer, also through the integer factorization route. Claude helped port the GPU program and schedule up to 2,048 GPUs, using idle computing capacity in the cluster to complete the calculation in approximately 10 days.
Later that month, researchers from the University of California, San Diego, and Inria in France took the digital signature forgery route, using an existing root-extraction algorithm and signature-device query results to generate a valid 1024-bit RSA signature without extracting the private key. The experiment took approximately five months and consumed about 1,380 CPU core-years.
This Google DeepMind experiment was a replication of that signature-forgery experiment. It had two AI agents use the same instance, algorithm, and principal parameters to reimplement and optimize the computational program. In less than four days, the two agents reproduced an experiment that had previously taken approximately five months, reducing the CPU computation from about 1,380 core-years to 391 core-years—a reduction of approximately 72%.
Conclusion: AI agents lower the cost of legacy RSA attacks and help assess cryptographic security
Previous RSA integer factorization studies assisted by Devin and Claude primarily improved computational efficiency by rewriting GPU programs and scheduling computing resources. This time, Google DeepMind went further by allowing agents to participate in improving signature attacks and batch factorization algorithms, lowering theoretical computational costs under certain conditions.
In cryptanalysis research, human researchers first define the problem and set experimental conditions, then have agents perform computations, optimize programs, and try different approaches, before the researchers review the results. With this division of labor, researchers can complete verification work requiring repeated experiments more quickly.
Source: Google DeepMind, X
(empty)
