Two AI Agents Cut a 1,380-Core-Year RSA Attack to 391 — and Proved the Maths in Lean 4

Summary card: two AI agents reproduced a 1024-bit RSA signature forgery in 391 CPU core-years against 1,380 previously, 3.5 times less, in under four days; a new batch-factoring result puts each further 1024-bit key at about 1/58 of the cost of the number field sieve, 30 times less than the previous best batch method; both papers state that 2048-bit and larger RSA is not threatened — Original graphic by Guruji Corporation. Sources: Google DeepMind working papers on affine roots and batch NFS, 5–6 November 2026.

Two AI agents took a computation that consumed 1,380 CPU core-years across five calendar months and reproduced it in 391 core-years — debugging it in under four days.[1] Google DeepMind published the result on 6 November 2026, together with a second paper whose algebraic identities are machine-checked in Lean 4.[2][3]

The target was 1024-bit RSA, a key size the public web retired years ago. That is exactly why the result matters: it tells you how fast AI-assisted cryptanalysis now moves the assumptions underneath standards you are still using somewhere.

What actually happened

DeepMind's announcement is an article by Pushmeet Kohli, Chief Scientist at Google Cloud and VP at DeepMind, describing work led by Dj Dvijotham and Abhradeep Thakurta with Nadia Heninger (UC San Diego and Inria) and Emmanuel Thomé (Inria).[1] Two working papers back it: one on affine roots and a 1024-bit computation, one on batch factoring.[2][3]

Both papers carry the same caveat in bold: "Our results don't threaten deployed cryptosystems today that are based on 2048-bit and larger RSA."[2][3] The sandbox was a retired key size, attacked inside a simulation, with no live system touched.[1]

What changed is the tempo: work like this used to take years or decades, which is why defenders treated cryptographic hardness as a slowly moving assumption. DeepMind says it now has to be re-tested continuously.[1]

The signature result: padding was doing less than assumed

Digital signatures work by having a device apply the private key to a padded block. The attacker's model in the paper is an affine oracle: a signing interface that adds a fixed format to the caller's data and returns the signature — which is what an HSM, a signing API, or a blind-signature scheme looks like from outside.[2]

The paper's first finding is blunt. Once an attacker controls roughly half of the signed block or more, the format stops mattering entirely: PKCS#1 v1.5, given more than half a block of data, or a 64-byte digest at 1024 bits, is no harder than an oracle that accepts every input. A 32-byte digest still leaves a harder problem.[2]

For that harder case, DeepMind lowers the cost of computing one root — offline phase included — from L_N[1/3, 1.8171] to L_N[1/3, 1.5803], and with a bigger offline phase the online cost per root approaches L_N[1/3, 1.3867], still far below the cost of factoring. The article puts the improvement in plainer terms: roughly 1,600× better than the previous best method for a 32-byte fingerprint, by theoretical estimate.[1][2]

Then the experiment. Reproducing the 1024-bit instance published by Shea, Haller, Suhl, Heninger and Thomé in September 2026 — with the same algorithm, polynomials and bounds — the first root took 391 CPU core-years against the original 1,380, a 3.5× saving, at less than a thousandth of the computing power needed to break the key itself.[2][4] The original attack, for reference, made 2^32 oracle queries and could forge any signature offline in 180 core-years afterwards.[4]

The factoring result, and a Lean 4 proof

The second paper attacks a different assumption: that factoring many keys of the same size has no shared shortcut worth taking. Coppersmith's factorization factory precomputes the rational side of the sieve once at cost L_N[1/3, 2.007] and then factors each integer at L_N[1/3, 1.639]; with a budget of about one factorization, the best known per-integer cost has been L_N[1/3, 1.902] since 1993.[3]

DeepMind's fan factories give every integer its own family of number fields fed by one shared rational side. At a budget of one factorization, each further integer costs L_N[1/3, 1.793]. At leading order, that means a precomputation equal to one factorization lets each further 1024-bit integer be factored at about 1/58 of the cost of the number field sieve — 30× less than the multiple number field sieve.[3]

The results hold under the standard heuristics of NFS analysis, and the identities and feasibility witnesses behind them are machine-checked in Lean 4. The harness was itself two agents: one model generated the proofs, a second verified them.[3]

What this does not mean

It does not mean 2048-bit RSA is broken. Both papers state the opposite, and the second paper's own numbers show why the distinction is real: these are asymptotic constants on a retired key size, not an attack on deployed keys.[2][3]

Nor does it put your TLS certificates at risk. But the UC San Diego and Inria paper it builds on makes a separate point worth writing down: RSA used with a signing oracle should be treated as 15 to 30 bits weaker than factoring-based estimates suggest for 1024- to 4096-bit keys, and even 4096-bit RSA does not appear to meet a 128-bit security level in that attack model. That paper used a hardware security module as the oracle, impersonating it through black-box API calls without exfiltrating the key.[4]

Why it matters for Indian SMBs and mid-market teams

The 1024-bit key you think is gone is probably still somewhere. Public TLS has required a modulus of at least 2048 bits for years — the CA/Browser Forum Baseline Requirements, version 2.3.1 dated 4 October 2026, state it in section 6.1.5 — but that rule covers publicly-trusted certificates only.[5] Internal CAs, old VPN appliances, printer and NAS interfaces, a 2010-era Java keystore, EDI gateways and smart-token signing utilities all sit outside it. Those are where a 1024-bit key survives, and they are where nobody has looked since the person who installed them left.

Inventory is the only part you can act on. Ask three questions this month and write the answers into an asset register: which certificates and keys in production are below 2048 bits, which services accept raw or lightly-formatted data into a signing or decryption interface, and who owns the replacement of each. A certificate you cannot find in an inventory is a certificate you cannot rotate.

Treat signing interfaces as a boundary, not a utility. The affine-oracle result formalises a principle that costs nothing to apply: a service that signs whatever it is handed gives an attacker a head start. Rate limits, authenticated callers, a narrow accepted input format, and an audit log of every signature request are the controls that survive the next paper.

Shorten the review interval on cryptography. DeepMind's own framing is the actionable sentence in the announcement: hardness assumptions should be stress-tested continuously rather than trusted because they held for twenty years.[1] For a mid-market team that means a dated annual review of key sizes and algorithms, not a one-time migration — plus a contract clause that key sizes must be declared and reported when they change.

Where Guruji Corporation fits in

We did not contribute to this research, and we do not break encryption. What we build is the part these findings keep requiring: an asset register that records key sizes, algorithms and expiry dates for every certificate and key you run; an integration layer that keeps credentials, scopes and signing operations separated per service; and a review process that turns "this is outdated" into a dated task with a named owner.

If you cannot list, today, which of your systems still holds a 1024-bit key, that is the first thing worth fixing. Send a short project brief and we will scope the inventory against what you already run.

Sources