Advancing the frontier of cryptanalysis

https://x.com/i/article/2118746079923437568

**X Article: Advancing the frontier of cryptanalysis **

Today, we’re sharing new research from @GoogleDeepMind showing how AI agents can accelerate cryptanalysis, or the science of stress-testing encryption. Our team used AI agents, guided by human supervision, to uncover two major weaknesses on legacy 1024-bit RSA-based cryptosystems, showing that these systems can be compromised with a lower computational budget than previously thought possible.

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. They do, however, show how rapidly AI agent systems can evaluate the mathematical “hardness” of the computational problems that underpin digital security. We are sharing this research so that the security community can use these insights to better measure cryptographic strength, and keep modern standards resilient well ahead of potential threats.

From encrypted communications to digital currencies, modern encryption systems rely on the concept of computational “hardness”: mathematical problems that are easy to set up but computationally infeasible for attackers to solve. For decades, systems like RSA have relied on this fact — multiplying two large prime numbers together is easy, but reversing that process (factorising their product) is computationally much harder.

At the same time, the cryptanalysis community has continuously stress-tested and questioned these hardness assumptions to ensure security standards stay ahead of potential threats, using retired systems like RSA-1024 as safe proving grounds, as we did here.

Historically, major advances in this kind of work take years or decades, meaning defenders could assume hardness margins changed only slowly. Our results, led by Dj Dvijotham and Abhradeep Thakurta and in collaboration with Nadia Heninger (UC San Diego and Inria), Emmanuel Thomé (Inria), show that AI can probe these hardness assumptions much faster, making proactive stress-testing more important than ever.

Our first result is about cryptanalysis and has consequences for the security of digital signatures. This is how computers verify that a piece of data — called a message, such as a software update, document or a website — is genuine and really comes from its claimed source.

Before signing a message, many signature standards add preset data, known as “padding”, to fill it out into a fixed-sized block. Cryptographers knew that padding helps prevent forgery, but not how much protection it offers if an attacker is able to feed chosen inputs to a signing device.

We found a strong answer: what matters is how much of the signed block an attacker controls. Once they control roughly half of the block or more, padding adds no protection at all. Forging a signature becomes just as vulnerable to mathematical shortcuts as using no padding at all. Testing this result in a sandboxed simulation—without touching any live systems—our agents engineered an implementation on an already-solved 1024-bit benchmark key from an earlier academic study, reproducing the result with 3.5× less CPU time, and at less than a thousandth of the computing power needed to break the key itself.

When an attacker controls less of the block, like with a short 32-byte digital fingerprint in the message, forging a signature is harder. Even so, we discovered a new algorithm that, according to our theoretical estimates, improves on the previous best method by roughly 1,600x for 1024-bit keys.

Our second result concerns factorising many numbers of the same size: a key question for RSA because keys typically share standard bit length, such as 1024 or 2048 bits. In theory, an attacker trying to break many keys can spread the cost of one large up-front computation across all of them, lowering the cost per key. Our AI agents discovered a new algorithm with better asymptotic complexity than previously known methods, cutting the average cost of factoring each additional 1024-bit key, out of many, by about 30× compared to previous batch methods.

Together, these results show that in a new era of AI-enabled mathematics and computation, we cannot treat cryptographic hardness as a fixed assumption. Using AI to rigorously test our previously held assumptions will ensure that modern encryption stays secure.

For more details on these results from the Google DeepMind Science team, please read our full technical papers on digital signatures and key factorisation.