Why DeepMind's RSA-1024 Attack Recreated the Math 3.5x Cheaper Without Breaking the Key ── Inside the 4-Billion Oracle Query Bound, Batch NFS Theory, and Lingering Legacy Keys
A forensic examination of DeepMind dual working papers reveals a 3.5x computational optimization under extreme oracle query assumptions, with no private keys extracted and production RSA-2048 unaffected.
Japanese Edition: https://consuloji.substack.com/p/ai35rsa1024bit
Executive Summary & Key Technical Takeaways
- Core Thesis: In November 2026, Google DeepMind published two working papers addressing RSA public-key cryptography: one recreating an affine root attack against RSA-1024 digital signatures and another proposing theoretical batch integer factorization via multiple number field sieve (Batch NFS) factories. Sensationalist coverage asserted that AI had “cracked RSA” or achieved “1,600x algorithmic breakthroughs.” A forensic analysis of the primary literature demonstrates the opposite: no private keys were recovered, no modern production RSA keys (2048-bit or 4096-bit) were compromised, and the only empirically measured efficiency improvement was a 3.5x reduction in compute cost resulting from software implementation tuning rather than algorithmic breakthroughs.
- The Operational Prerequisite: The affine root signature forgery operates strictly under a chosen-message oracle premise requiring approximately 4 billion queries (~2^32 calls) to a physical signing device (such as a Hardware Security Module / HSM). If an enterprise signing architecture does not allow external callers to submit unhashed chosen payloads, the attack cannot execute.
- Theory vs. Empirical Fact: The widely circulated 58x and 30x factorization efficiency claims originate from a purely theoretical paper on Batch NFS with zero physical implementation and zero empirical measurements. Furthermore, the circulating “1,600x” claim appears nowhere in the text of either DeepMind working paper.
- The Lingering Legacy Risk: The National Institute of Standards and Technology (NIST) disallowed 1024-bit RSA for signature generation in SP 800-131A Revision 2. Yet internet-wide scans by SandboxAQ reveal that roughly 120,000 public keys (~1.0% of observed RSA keys)—concentrated in legacy SSH hosts, embedded appliances, and private corporate Certificate Authorities (CAs)—remain at 1024 bits.
- Immediate Actionable Defense: Security teams must verify two specific architectural controls: (1) ensure signing devices mandate internal message hashing (precluding unhashed oracle submissions), and (2) inventory internal networks for lingering 1024-bit RSA certificates and SSH keys.

1. Dissecting the Primary Literature: Working Papers vs. Peer-Reviewed Claims
To establish technical ground truth, this analysis cross-examines five primary cryptographic sources:
- DeepMind Working Paper 1 (Signature Attack): “Faster Affine Root and a 1024-bit Computation” (investigating signature forgery under chosen-message oracle access).
- DeepMind Working Paper 2 (Batch Factorization): “Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS” (dated November 5, 2026, exploring asymptotic batch integer factorization).
- UCSD and Inria Foundational Research (IACR ePrint 2026/2131): The academic origin demonstrating the original 1024-bit affine root computation in 1,380 core-years.
- NIST Special Publication 800-131A Revision 2 (March 2019): The formal standard governing cryptographic transition and key-length validation.
- SandboxAQ Internet Census (January 2025): An empirical scan of 11.5 million public RSA keys deployed across the internet.
Both DeepMind releases are explicitly designated by their authors as “Working Papers”, indicating they have not yet undergone formal academic peer review.

2. Paper 1 Teardown: The Signature Oracle Attack and the 4-Billion Query Prerequisite
The first working paper examines an affine root signature forgery against 1024-bit RSA. The attack relies on an extremely rigid threat model:
- Oracle Prerequisite: The adversary must possess temporary access to an authorized signing device (such as an HSM) that computes raw RSA private-key operations on arbitrary caller-supplied inputs.
- The Query Bound: The adversary must execute approximately 4 billion queries against this signing interface. In the underlying UCSD/Inria baseline experiment, physical signing hardware was utilized as the oracle.
- Offline Post-Processing: Once the 4 billion signatures are collected, the attacker completes an offline lattice computation to forge signatures on arbitrary chosen messages without further access to the HSM.
What the Attack Does and Does Not Do
Crucially, this attack does not extract the private key. The private key (d) remains intact and secure inside the cryptographic boundary of the HSM. The paper explicitly affirms that this procedure is not a key-recovery attack.
Furthermore, the attack depends on specific padding weaknesses:
- PKCS #1 v1.5 Formatting Vulnerability: Forgery succeeds only when the caller-controlled message portion exceeds roughly half of the total block length (>64 bytes for a 1024-bit modulus).
- Digest Length Restrictions: The mathematics functions reliably when hash digests are up to 64 bytes (such as SHA-512). When dealing with standard 32-byte digests (SHA-256), substantial algebraic barriers remain unresolved; improvements exist only as asymptotic complexity equations rather than working code.
- Internal Hashing Insulation: In modern production cryptographic workflows, the host application or HSM hashes the message internally before signing (e.g., via PKCS #11 mechanisms). Under this architecture, an external caller cannot manipulate the high-order bits of the formatted block, rendering the attack mathematically impossible.

3. Paper 2 Teardown: Batch Factorization Theory and the Unresolved Memory Wall
The second working paper addresses a separate mathematical challenge: factoring multiple integers of the exact same bit-length simultaneously via Number Field Sieve (NFS) optimizations.
The proposed theoretical architecture utilizes “Factorization Factories”:
- Shared Precomputation: Perform one massive, computationally expensive shared calculation across multiple number fields.
- Marginal Cost Amortization: After completing this precomputation, subsequent individual integers can theoretically be factored at a fraction of standard cost.
- Theoretical Claims: For 1024-bit integers, the paper estimates that setting the shared precomputation equal to the cost of factoring a single integer reduces the marginal cost of factoring each additional integer to roughly 1/58th of baseline (~30x cheaper than prior state-of-the-art methods).
| Metric / Parameter | DeepMind Paper 2 Theoretical Estimate | Operational Baseline / Practical Engineering Reality |
|---|---|---|
| Target Modulus Length | 1024-bit and 2048-bit RSA | Modern internet production standards mandate 2048-bit or 4096-bit keys |
| Asymptotic Complexity Formulation | Marginal cost 1/58th (~30x cheaper) for 1024-bit batch NFS | Based entirely on leading terms of complexity formulas; lower-order terms omitted |
| Physical Implementation | Zero lines of execution code; purely theoretical model | No physical implementation exists; zero physical integer factorization performed |
| Linear Algebra Memory Overhead | Requires exabyte-scale shared matrix storage | The Memory Wall: Matrix solving and relation storage exceed physical server RAM |
| Impact on Modern RSA-2048 | Formula suggests 1/240th marginal cost after full 2048 precomputation | Paper explicitly states: “Does not threaten current operational 2048-bit deployments” |
The paper authors emphasize that these figures represent theoretical estimates derived from leading complexity terms. Crucially, the authors did not implement the batch NFS algorithm, nor did they conduct empirical factorization measurements. The memory requirements for storing and processing the multi-field linear algebra matrix represent an unresolved “Memory Wall” that current datacenter memory architectures cannot bridge.

4. Sorting the Numbers: The 3.5x Measured Reality vs. the 1,600x Ghost Metric
Public reporting conflated three fundamentally different categories of numerical data. Disentangling these metrics is essential for accurate security risk modeling:
- 3.5x Speedup (Empirically Measured Reality):
- In the foundational UCSD/Inria research, completing the affine root precomputation required 1,380 core-years over a 5-month calendar period.
- DeepMind reproduced this exact mathematical computation in 391 core-years (completed in 3.2 calendar days across ~300,000 CPU cores).
- This 3.5x efficiency gain was not an algorithmic revolution; it stemmed from low-level software engineering optimizations (SIMD assembly vectorization, cache line locality tuning, and distributed scheduler optimizations) that achieved 1.8x to 4.4x speedups on identical core architectures.
- 30x / 58x Improvement (Pure Asymptotic Theory):
- Derived exclusively from Paper 2’s theoretical formulas for batch 1024-bit integer factorization. Completely unimplemented and unverified empirically.
- 1,600x Speedup (The Unverified Ghost Metric):
- This figure appeared widely across social media and secondary news summaries. However, the number 1,600 does not appear anywhere in the body of either DeepMind working paper. It appears to be an artifact of third-party commentary multiplying theoretical polynomial root advantages without accounting for physical sieve communication overhead.
| Metric | Quantitative Value | Data Classification | Engineering Basis & Context |
|---|---|---|---|
| Empirical Compute Reduction | 3.5x faster (391 vs. 1,380 core-years) | Empirically Verified | Low-level C/assembly optimization and vectorization; identical underlying algorithm |
| Wall-Clock Completion Time | 3.2 days (vs. ~5 months) | Empirically Verified | Massive parallelization across ~300,000 distributed cloud CPU cores |
| Oracle Query Volume | ~4 billion queries (~2^32 calls) | Threat Model Prerequisite | Requires sustained direct interaction with an unhashed signing interface |
| Batch NFS Marginal Cost | 1/58th (~30x cheaper) for 1024-bit | Pure Asymptotic Theory | Unimplemented algebraic formula based on leading mathematical terms |
| Circulated “1,600x” Multiplier | 1,600x algorithmic breakthrough | Unverified / Absent | Does not appear in primary texts; unverified third-party compounding |
The Real Role of AI: Accelerated Software Engineering
In Paper 1, DeepMind deployed two LLM agents: a supervisory agent that planned execution and verified intermediate outputs, and a coding agent that wrote roughly 33,500 lines of implementation code over four days. Human researchers intervened approximately 20 times with brief steering prompts (primarily approvals). In Paper 2, models assisted in proof exploration, verified by the Lean 4 interactive theorem prover.
The primary significance of AI here was accelerating software engineering cycles and formal proof verification—compressing months of low-level optimization into days. The AI did not discover a fundamental mathematical bypass around RSA encryption.

5. Where 1024-Bit RSA Actually Lurks in Enterprise Infrastructure
Under NIST Special Publication 800-131A Revision 2, 1024-bit RSA was formally deprecated in 2011 and disallowed for digital signature generation beginning in 2013 (reconfirmed in 2019). Modern public web standards enforce 2048-bit keys minimum.
However, real-world cryptographic audits show that legacy keys persist across production environments. In an internet-wide survey conducted by SandboxAQ:
- Out of 11.5 million public RSA keys cataloged across public certificate transparency logs, web servers, and open-source code repositories, roughly 120,000 keys were 1024-bit or smaller (~1.0% of observed keys).
- OpenSSH implementations as late as 2024 still permitted the generation and acceptance of 1024-bit RSA host and user keys if not explicitly restricted in configuration files.
- Common enterprise blind spots include:
- Internal SSH authorized_keys files deployed across legacy production jump boxes.
- Out-of-band management controllers (IPMI, iLO, DRAC) running original factory firmware.
- Private enterprise PKI root and intermediate Certificate Authorities created in the early 2000s that remain embedded in industrial operational technology (OT) networks.
While 1024-bit keys represent a small fraction of public TLS traffic, their survival in unmonitored internal systems represents a viable attack surface if paired with misconfigured signing interfaces.

6. Enterprise Action Items: The 2-Point Cryptographic Defense Protocol
Enterprise security architects should not panic over sensationalized claims, but they must implement two deterministic hygiene checks across their infrastructure:
- Audit Signing Gateways and HSM Call Interfaces:
- Inspect all API endpoints exposing cryptographic signing operations.
- Enforce cryptographic hashing before payload delivery to the signing module, or configure the HSM to compute message digests internally.
- Implement strict rate-limiting, anomaly detection, and query alerting on signing interfaces. If a client attempts to submit millions—let alone 4 billion—signing requests, the connection must immediately sever and raise high-severity security incidents.
- Execute an Internal 1024-Bit Cryptographic Inventory:
- Scan internal server fleets for legacy SSH host keys, client authorized_keys, and local certificates.
- Audit private enterprise PKI hierarchies to retire lingering 1024-bit intermediate CAs.
- Update OpenSSH daemon configurations (
sshd_config) to explicitly reject RSA keys below 2048 bits (CASignatureAlgorithms,PubkeyAcceptedKeyTypes).


Primary Sources & Verified References
- Google DeepMind Working Paper 1: “Faster Affine Root and a 1024-bit Computation” (https://storage.googleapis.com/deepmind-media/papers/Faster_Affine_Root_and_a_1024bit%20Computation.pdf)
- Google DeepMind Working Paper 2: “Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS” (https://storage.googleapis.com/deepmind-media/papers/Fan_Factories_Multiple_Number_Fields_in_Factorization_Factories_and_Batch_NFS.pdf)
- UCSD and Inria Cryptographic Research: IACR Cryptology ePrint Archive Report 2026/2131 (https://eprint.iacr.org/2026/2131)
- National Institute of Standards and Technology (NIST): Special Publication 800-131A Revision 2, Transitioning the Use of Cryptographic Algorithms and Key Lengths (https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf)
- SandboxAQ Cryptographic Research: Survey of Public Keys on the Internet (https://cryptographycaffe.sandboxaq.com/posts/survey-public-keys-internet/)
This article analyzes primary technical and financial disclosures for informational purposes only and does not constitute investment advice.