Four billion queries to test an old RSA key

Two Google DeepMind studies quantify the cost of forging an RSA-1024 signature and factoring keys of the same size.

Four billion queries to a simulated signing device preceded the selection of the target. Once that access was cut off, Google DeepMind researchers computed the value serving as the signature in the experiment and verified it using the public key. The team revisited a 1,024-bit RSA case studied by Laura Shea and her coauthors. The key’s prime factors were already known, but only the program simulating the signing device had access to them.

Including preparation, the selected tasks required the equivalent of 391 CPU core-years, compared with 1,380 in the previous experiment. The working paper on signatures reports a 3.5-fold reduction in CPU time for the same case, with some computations performed on GPUs and accounted for separately. The 3.2 days between the start of the large-scale run and verification of the result were largely due to the number of tasks running in parallel. On average, approximately 45,000 CPU cores were operating simultaneously. What the Signing Device Allows Users to Control

A digital signature is used to verify the origin and integrity of a document or software update. In the format examined, the device combines the data it receives with predefined bytes to create a fixed-size block. The researchers investigated how this format affects the problem when someone with access to the signing interface can directly control part of that block.

For a 1,024-bit key, if that person controls roughly half the block, the computation becomes almost as tractable as it would be with an interface that accepts data without a prescribed format. If they can choose only a 32-byte digest, the problem becomes more difficult. For this scenario, Pushmeet Kohli estimates that the new method reduces the cost by a factor of approximately 1,600 compared with the reference method. This figure is based on a theoretical estimate. Devices that compute the message digest themselves fall outside the model examined. Sharing the Preparation Work Across Multiple Keys

The second study, focused on factorization, examines the cost of recovering the two prime numbers whose product appears in an RSA public key. Knowing these factors makes it possible to reconstruct the private key. In the signature forgery experiment, the researchers only needed to compute a signature for the selected target.

The authors propose sharing part of the computational workload across multiple keys of the same size. In their estimate for RSA-1024, the initial preparation costs as much as a single factorization using the conventional method. Once that upfront cost has been covered, each additional key costs approximately 30 times less than with the best previous method under the same computational budget. The proposal remains theoretical. Both papers provide cost estimates for 2,048-bit RSA, while the laboratory computation was performed on 1,024-bit RSA. Who Did What in the Experiment

To reproduce the signature computation, one AI agent developed the plan, established verification procedures, and reviewed the results. Another wrote the code, launched jobs on the computing cluster, and fixed errors. The researcher defined the objective and approved the critical steps. In the factorization study, one agent developed mathematical proofs while another verified them. The authors also used Lean 4 to verify algebraic identities and certain feasibility conditions.