DeepMind’s AI Agents Cut the Cost of Attacking RSA-1024, but the 3.5x Is a Faster Run of a Known Algorithm, and the 1,600x and 30x Are Estimates for Methods Neither Paper Has Run

Google DeepMind said on November 6 that AI agents working under human supervision found two ways to lower the cost of attacking 1024-bit RSA, and SecurityWeek relayed the claims on November 9. The announcement is an X Article by Pushmeet Kohli titled “Advancing the frontier of cryptanalysis”, and it links two working papers written with the cryptographers Nadia Heninger (UC San Diego and Inria) and Emmanuel Thomé (Inria). We read both papers against the announcement. Every headline number traces to the papers or follows directly from them, but they are not the same kind of number: the 3.5x speedup is one measured run of a known algorithm on a known key, the claim that padding stops mattering is proved above about half a block, and the 1,600x and 30x figures are leading-order estimates for two methods that neither paper reports running at cryptographic size.

Both papers also carry a boxed note that the results do not threaten deployed systems that use 2048-bit or larger RSA, which matches the announcement. Where they bite is narrower: a 1024-bit key whose signing interface lets a caller choose about half or more of the block, and a caller who can make billions of calls before the attack starts. We recomputed the estimates, replicated one of the paper’s measurements and checked the arithmetic the papers print. The scripts and their output are at the end.

What was published, and when

The signature paper’s main computation is a re-run, so the sequence matters. On September 22 the IACR ePrint archive approved paper 2026/2131 by Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger and Emmanuel Thomé, “Forging 1024-bit RSA signatures in nearly SNFS time” (SNFS is the special number field sieve). Its abstract reports 1,380 CPU core-years over five calendar months and 2³² oracle queries to forge a signature on a 1024-bit key, with a hardware security module as the signing oracle, and 180 core-years for each further forgery once the precomputation is done. DeepMind’s fan paper is dated November 5, Kohli’s article went up on November 6 at 17:07 UTC, and SecurityWeek’s story is stamped 08:35 UTC on November 9.

Both DeepMind PDFs are labeled “Working Paper”, sit in a Google storage bucket, and defer proofs and parameters to “the full version” (22 mentions in the signature paper, 15 in the fan paper, by our count), which the announcement does not link. The signature paper calls its two agents Model A and Model B and does not name the models. The text of neither paper links code.

The five numbers, checked against the papers

SecurityWeek’s version of each item is faithful, and it carries the caveats that Kohli’s post leaves to the papers: the key was not factored, the algorithm for many keys “has not been implemented”, the forgery “does not work against devices that hash messages internally”, and it needs about 4 billion signing queries made in advance. Two phrases in Kohli’s post drift from the papers. “Previous batch methods” is not the baseline of the 30x: the fan paper compares with MNFS, “which needs no precomputation”, and reports that factoring a batch together without precomputation improves the exponent by at most 0.018. And “Testing this result”, which follows the padding claim, refers to a run that used the raw RSA map with no padding in it; the run connects to the padding result through the theorem (“the same computation applies to the fixed formats above the threshold”, with twice as many queries), not through an experiment.

The 3.5x: one run, the same algorithm, mostly a faster siever

The run used the modulus, polynomials and factor-base bounds of ePrint 2026/2131 and the unrestricted algorithm of Joux, Naccache and Thomé (2007), implemented in C++ on top of CADO-NFS with e = 65537. The oracle was “a separate program, the only one with access to the factorization of N”: it answered 4,055,916,065 queries as 63 parallel tasks in 20 minutes, so no hardware security module and no live key was involved. After the oracle was withdrawn, a target derived from a public seed by SHA-256 was rooted and the result checked as x^e ≡ t (mod N).

Neither column includes polynomial selection, which DeepMind reused. The paper says where the saving comes from: “Sieving accounts for 90% of the saving”, and it compared its optimized fork of the CADO-NFS lattice siever with the upstream siever on one machine. On the same special-q values both find the same relations, and the fork is 1.8 to 1.9 times faster on the core sieve and 3.4 to 4.4 times faster in the second-tier early-exit mode (one thread to 32 threads), so at most a factor of 1.5 on the core sieve and 1.2 on the second tier can come from hardware or other differences. Charging the GPU linear algebra at the earlier study’s 17 core-years gives 3.4x, and adding 7.5 core-years of probes and rehearsals gives 3.3x; we get 3.38 and 3.32. “None of these gains changes the asymptotic cost”, and the paper says the siever optimizations carry over to any CADO-NFS computation.

The calendar numbers are a different thing. The run took 3.2 days from the first full-scale sieving job to the verified root, against about five months for the earlier study, which the paper says “reflects mainly parallelism”: about 45,000 cores busy on average (3.4 million core-hours), with peaks near 300,000 cores and 16 GPUs, against about 3,300 cores before. “We do not count it as an efficiency gain.” The cost ratio to factoring is the number the announcement leans on: 391 core-years is 0.04 to 0.08 percent of the 500,000 to 1,000,000 core-years the paper cites for factoring the modulus, which is the “less than a thousandth” in Kohli’s post. Each further root then costs 73 core-years against 180, so computing M roots stays cheaper than factoring up to roughly 6,800 to 13,600 roots; we reproduce 6,812 and 13,624.

What “padding adds no protection” covers

The padding result is about a fixed block format: the signing device writes the caller’s data into a block of the form c + z, where c is fixed and z is the caller’s part. The papers ask how many bits of z the caller must control before the format stops helping. The answer is about half of the block: with a window of about the square root of N offsets, each raw-map query can be answered as the quotient of the roots of two admissible inputs, at the cost of two queries per query. The attack then computes e-th roots of targets, which is what signing a value means, without the key; “they do not recover the key”.

We replicated the paper’s measurement at the threshold (Figure 4, random odd 1024-bit modulus, random constant, random unit, 10,000 draws per window). At a variable part of exactly 512 bits, the paper reports a 79.6 percent chance per draw; we got 79.4 percent. Below half, each missing bit cut our rate by a factor of about four (3.7, 4.0 and 5.3), as the paper’s counting bound says it should: the rate tracks the window size squared over N. The paper also reports 31.7 percent at 2⁵¹¹ and 0.53 percent at 2⁵⁰⁸, where we got 31.2 and 0.4.

The paper’s own Figure 5 maps the result onto the PKCS#11 signing mechanisms, ordered by how much of the 128-byte block the caller chooses.

The paper lists three limits on practical reach. The first is size: 1024 bits is the largest at which the unrestricted algorithm has been run, and “at 2048 bits every cost estimate of this paper is asymptotic.” The second is access: the model needs “direct calls to the signing interface with inputs of the caller’s choice, rather than calls through an application that hashes the message before signing.” The third is volume: “the number of calls is large”, about 4 billion in the computation, all made before the target is known, and about twice that for padded blocks. The raw map is not an approved signature scheme under FIPS 186-5, the paper notes, and NIST SP 800-131A Rev. 2 says 1024-bit RSA “may continue to be used for signature verification but not signature generation.”

The call count is the practical tripwire, so we put it on a clock. We know no device’s signing rate; the table is arithmetic on the paper’s 4.06 billion calls and the doubling for padded blocks.

The two estimates: 1,600x and 30x

Every cost in the papers has the form L[c] = exp((c + o(1))·K), where K = (ln N)^1/3(ln ln N)^2/3, and the analysis does not determine the o(1) term. Setting it to zero turns two exponents into a ratio, exp((c_old − c_new)·K). The fan paper does this for its own result at 1024 bits (about 58.5 against one number field sieve run and 30.2 against MNFS) and says plainly what the ratio is: “it is not a prediction of running times, because the hidden factors differ between algorithms and can be large.” Its abstract states the condition in the same breath: “At leading order, that is, with the o(1) terms set to zero.”

The signature paper never converts its exponent change into a factor. Applying the same formula to 1.8171 and 1.5803 gives 1,646.7 at 1024 bits, which is where “roughly 1,600x” in Kohli’s post comes from as far as we can reproduce it, to within about 3 percent. Our script also reproduces the fan paper’s Table 2 rows for 1024 and 2048 bits (K of 31.27 and 42.13, one run of the number field sieve at 2^86.8 and 2^116.9 steps, 58.5 and 240.1 against one run).

The ratios grow with key size because the exponent gaps are fixed, so a bigger ratio at 2048 bits says little about feasibility there: one run of the number field sieve is about 2¹¹⁷ steps in the same formula, and a further key under the fan factory costs 1/240 of that, still about 2¹⁰⁹ (our division). The 30x also has a narrow footing. It needs a precomputation as costly as factoring one key; the gain falls to nothing once the budget reaches about 1.9496 in exponent terms, where one polynomial per integer is optimal; and the paper says “no fan factory has been implemented, and the size at which one would overtake a well-tuned number field sieve is empirically open.” The papers’ proofs also sit partly in the full version: the fan paper says its algebraic identities and four exact feasibility witnesses are machine-checked in Lean 4, while the calculus arguments are proved in the text and “were checked numerically”. Our post on the claimed refutations of the Exponential Time Hypothesis covers the related question of what a Lean check does and does not certify.

Context the announcement does not carry

The earlier study drew a stronger conclusion about the model. The ePrint 2026/2131 abstract, by authors who include Heninger and Thomé, says “the concrete security of RSA with a signing oracle should be 15 to 30 bits lower than the factoring-based security estimates for the 1024-bit to 4096-bit RSA parameters that are common in practice”, and “Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model.” It also notes “Blind RSA schemes also provide such a signing oracle”, which is why that model matters beyond hardware modules; our November 6 post on Cloudflare’s post-quantum plan for anonymous credentials covers where blind signatures sit in that design. The DeepMind papers answer a different question, what a deployed system lets an attacker do, and on that question both say they do not threaten deployed 2048-bit RSA. The two statements are not in conflict, but they are not the same claim, and the announcement carries only the second.

Direct factoring of 1024-bit keys was already moving in September. On September 19 Stephen Weis of Anthropic published the factors of RSA-896, done with Claude on up to 2,048 idle GPUs in about 10 days and 30 GPU-years, and wrote that it shows “RSA-1024 keys are vulnerable to many actors with data center-level fleets of GPUs.” Ten days earlier Eric Lu of Cognition, who factored RSA-260 with the Devin agent, wrote that “Hyperscalers or frontier AI labs could likely factor RSA-1024 numbers at a cost on the order of $30 million per number”; his estimate table lists about 546,000 CPU core-years for RSA-1024, inside the range DeepMind uses. Lu’s figures are estimates from scaling, neither post measures anything at 1024 bits, and neither is a DeepMind result. Read together, they suggest that the “obsolete 1024-bit RSA systems” in Kohli’s post are keys that already have a price.

Who found what is documented for the computation, less so for the theory. The signature paper credits the agents with the 1024-bit computation: a supervisor (Model A) that wrote the design, set the checks and audited results, an executor (Model B) that wrote the code and ran the jobs, and a specialist sub-agent for a 5x speed-up of one linear-algebra step, with checks fixed before each stage and a rehearsal at 498 bits. It lists problems that only appeared at full size, including a 32-bit index overflow that made the first computed root wrong and was found because the paper’s check of x^e ≡ t failed. The text we read does not say which of its theorems the agents found. The fan paper is explicit: “one model generated the proofs, and a second model verified them”, and the analysis and Lean formalization “were developed with AI agents.” Kohli’s post says “we discovered” for the 1,600x algorithm and “Our AI agents discovered a new algorithm with better asymptotic complexity than previously known methods” for the 30x one.

What to check this week

• Find RSA signing keys under 2048 bits. NIST’s position is in the quote above. If a 1024-bit key still signs anything, these papers sharpen an existing finding rather than create one.
• List the PKCS#11 mechanisms your clients call. Per the paper’s Figure 5, CKM_RSA_X_509, CKM_RSA_PKCS with 65 or more bytes of caller data at 1024 bits, and a caller-supplied 64-byte digest are inside the unrestricted case. A mechanism that hashes inside the device, such as CKM_SHA256_RSA_PKCS, is outside both models.
• Ask whether an outside party can submit chosen blocks. The attack needs billions of calls before the target is known, so call volume per key and per caller is the tripwire. That inference is ours; the paper lists the number of calls as a limit, not as a control.
• Treat blind-signature services as signing oracles by design. The earlier study’s abstract says so. The question for each is key size and how many blinded values an outsider can get signed.
• For 2048-bit and larger keys, neither DeepMind paper changes the operational picture. The migration clock to watch is the one in NIST IR 8547, which we covered in our post on the final report.

Run the checks yourself

Three standard-library scripts for Python 3.13. The first recomputes the leading-order ratios; its output matches the fan paper’s Table 2 rows for 1024 and 2048 bits.

"""ratios.py: recompute the leading-order multipliers behind the 1,600x and 30x claims.

Python 3.13, standard library only. Every cost in the two papers has the form
L[c] = exp((c + o(1)) * K), with K = (ln N)^(1/3) * (ln ln N)^(2/3).
Setting o(1) to zero turns two exponents into a ratio: exp((c_old - c_new) * K).
"""
import math


def k(bits):
    """K for N = 2**bits."""
    ln_n = bits * math.log(2)
    return ln_n ** (1 / 3) * math.log(ln_n) ** (2 / 3)


C_GNFS = (64 / 9) ** (1 / 3)                          # general number field sieve
C_MNFS = ((92 + 26 * math.sqrt(13)) / 27) ** (1 / 3)  # Coppersmith's multiple NFS
C_JNT = 6 ** (1 / 3)                                  # affine roots, Joux-Naccache-Thome 2007
NEW_AFFINE = 1.5803                                   # Theorem 3.1, signature paper
NEW_FAN = 1.7929                                      # Theorem 3.3, fan paper, budget of one GNFS run

print(f"c_GNFS = {C_GNFS:.4f}   c_MNFS = {C_MNFS:.4f}   c_JNT (affine) = {C_JNT:.4f}")

CASES = [
    ("32-byte digest: 1.8171 -> 1.5803", C_JNT, NEW_AFFINE),
    ("fan factory vs MNFS: 1.9019 -> 1.7929", C_MNFS, NEW_FAN),
    ("fan factory vs one GNFS run: 1.9230 -> 1.7929", C_GNFS, NEW_FAN),
]

BATCH_GAIN = 0.0180                                   # fan paper, best exponent gain when a batch is factored together

for bits in (1024, 2048):
    print(f"--- {bits}-bit N: K = {k(bits):.2f}, one GNFS run = 2^{C_GNFS * k(bits) / math.log(2):.1f} steps")
    for name, old, new in CASES:
        print(f"  {name:<48} ratio = {math.exp((old - new) * k(bits)):>9,.1f}")
    print(f"  {'fan batch mode, best case: gain 0.0180':<48} ratio = {math.exp(BATCH_GAIN * k(bits)):>9,.1f}")

Its output:

c_GNFS = 1.9230   c_MNFS = 1.9019   c_JNT (affine) = 1.8171
--- 1024-bit N: K = 31.27, one GNFS run = 2^86.8 steps
  32-byte digest: 1.8171 -> 1.5803                 ratio =   1,646.7
  fan factory vs MNFS: 1.9019 -> 1.7929            ratio =      30.2
  fan factory vs one GNFS run: 1.9230 -> 1.7929    ratio =      58.5
  fan batch mode, best case: gain 0.0180           ratio =       1.8
--- 2048-bit N: K = 42.13, one GNFS run = 2^116.9 steps
  32-byte digest: 1.8171 -> 1.5803                 ratio =  21,535.6
  fan factory vs MNFS: 1.9019 -> 1.7929            ratio =      98.6
  fan factory vs one GNFS run: 1.9230 -> 1.7929    ratio =     240.1
  fan batch mode, best case: gain 0.0180           ratio =       2.1

The second checks the arithmetic the papers print (core-year ratios, core-hours, the oracle query total, break-even, tool calls) and prints the days of signing calls at three assumed rates.

"""checks.py: arithmetic checks on numbers the two DeepMind papers print.

Python 3.13, standard library only. Inputs are copied from the signature paper
(Table 2, Section 5.3, Section 6, Table 3) and from the abstract of ePrint 2026/2131.
"""
HOURS_PER_YEAR = 8766

# Core-year totals for the first root on the same 1024-bit modulus.
prior, new = 1380, 391
print(f"core-years: {prior} / {new} = {prior / new:.2f}x")
print(f"  with the prior stage costs (1,204 + 179): {1383 / new:.2f}x")
print(f"  charging GPU linear algebra at 17 core-years: {prior / (new + 17):.2f}x")
print(f"  and adding 7.5 core-years of probes: {prior / (new + 17 + 7.5):.2f}x")

# Calendar time and cores.
hours = new * HOURS_PER_YEAR
print(f"{new} core-years = {hours / 1e6:.2f} million core-hours")
print(f"  over 3.2 days that is {3.4e6 / (3.2 * 24):,.0f} cores busy on average")
print(f"  prior run: 12.2 million core-hours at 3,300 cores = {12.2e6 / 3300 / 24 / 30.4:.1f} months")

# Oracle queries.
parts = [1, 2_874_398_515, 106_106_172, 1_075_411_377]
total = sum(parts)
print(f"queries: sum of the four parts = {total:,}  (paper: 4,055,916,065)")
print(f"  2^32 = {2 ** 32:,}; the run used {total / 2 ** 32:.1%} of that")
print(f"  20 minutes -> {total / 1200:,.0f} queries per second in total")

# Against factoring the modulus (500,000 to 1,000,000 core-years).
for cost in (500_000, 1_000_000):
    print(f"  first root = {new / cost:.3%} of a {cost:,} core-year factoring; "
          f"break-even M = {cost / 73.4:,.0f} roots at 73.4 core-years each")

# Agent work: tool calls per role.
print(f"tool calls: {15_140} + {959} + {193} = {15_140 + 959 + 193:,}  (paper: 16,292)")

# Why the query count matters on a real signing device.
print("days of signing calls, if a device answered R calls per second:")
print(f"  {'R/s':>8} {'4.06e9 (raw map)':>18} {'8.11e9 (formatted)':>20}")
for rate in (1_000, 10_000, 100_000):
    d1 = total / rate / 86_400
    d2 = 2 * total / rate / 86_400
    print(f"  {rate:>8,} {d1:>18.1f} {d2:>20.1f}")

# Theorem 4.1: a window of 2^(8*l) offsets reduces to the raw map once 8*l >= (1/2) * log2(N) + 2.1.
for bits in (1024, 2048):
    need = next(l for l in range(1, bits // 8) if 8 * l >= bits / 2 + 2.1)
    print(f"{bits}-bit key: caller must supply at least {need} of {bits // 8} bytes; "
          f"CKM_RSA_PKCS accepts up to {bits // 8 - 11}")

Its output:

core-years: 1380 / 391 = 3.53x
  with the prior stage costs (1,204 + 179): 3.54x
  charging GPU linear algebra at 17 core-years: 3.38x
  and adding 7.5 core-years of probes: 3.32x
391 core-years = 3.43 million core-hours
  over 3.2 days that is 44,271 cores busy on average
  prior run: 12.2 million core-hours at 3,300 cores = 5.1 months
queries: sum of the four parts = 4,055,916,065  (paper: 4,055,916,065)
  2^32 = 4,294,967,296; the run used 94.4% of that
  20 minutes -> 3,379,930 queries per second in total
  first root = 0.078% of a 500,000 core-year factoring; break-even M = 6,812 roots at 73.4 core-years each
  first root = 0.039% of a 1,000,000 core-year factoring; break-even M = 13,624 roots at 73.4 core-years each
tool calls: 15140 + 959 + 193 = 16,292  (paper: 16,292)
days of signing calls, if a device answered R calls per second:
       R/s   4.06e9 (raw map)   8.11e9 (formatted)
     1,000               46.9                 93.9
    10,000                4.7                  9.4
   100,000                0.5                  0.9
1024-bit key: caller must supply at least 65 of 128 bytes; CKM_RSA_PKCS accepts up to 117
2048-bit key: caller must supply at least 129 of 256 bytes; CKM_RSA_PKCS accepts up to 245

The third replicates the threshold measurement. It runs about 45 seconds and uses fixed seeds.

"""rerandomize.py: replicate the re-randomization success rate (Figure 4 of the signature paper).

Python 3.13, standard library only. For a random odd 1024-bit N, a random c and a random unit rho,
find z, z2 in [0, W) with c + z = rho * (c + z2) (mod N). Writing z = z0 + x and z2 = y, the pairs
(x, y) with x = rho * y (mod N) form a lattice of determinant N; we reduce a basis (Lagrange-Gauss),
round the target (the middle of the box) to the lattice, and search the 3 x 3 points around it.
"""
import math
import random
import sys


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]


def nearest(num, den):
    """Nearest integer to num/den, den may be negative."""
    if den < 0:
        num, den = -num, -den
    return (2 * num + den) // (2 * den)


def gauss(u, v):
    """Lagrange-Gauss reduction of a 2-D integer lattice basis."""
    while True:
        if dot(v, v) < dot(u, u):
            u, v = v, u
        m = nearest(dot(u, v), dot(u, u))
        if m == 0:
            return u, v
        v = (v[0] - m * u[0], v[1] - m * u[1])


def one_draw(rng, bits, width):
    n = rng.getrandbits(bits - 1) | (1 << (bits - 1)) | 1       # odd, in [2^(bits-1), 2^bits)
    c = rng.randrange(n)
    while True:
        rho = rng.randrange(2, n - 1)
        if math.gcd(rho, n) == 1:
            break
    z0 = (rho - 1) * c % n
    u, v = gauss((n, 0), (rho, 1))
    det = u[0] * v[1] - u[1] * v[0]
    px, py = width - 2 * z0, width                              # twice the box centre, relative to (z0, 0)
    ra = nearest(px * v[1] - py * v[0], 2 * det)
    rb = nearest(u[0] * py - u[1] * px, 2 * det)
    for i in (ra - 1, ra, ra + 1):
        for j in (rb - 1, rb, rb + 1):
            x = i * u[0] + j * v[0]
            y = i * u[1] + j * v[1]
            if 0 <= z0 + x < width and 0 <= y < width:
                return True
    return False


def main(bits=1024, draws=10_000, seed=2026):
    print(f"{bits}-bit N, {draws:,} draws per window; paper reports 79.6% at W = 2^512")
    for e in range(bits // 2 - 4, bits // 2 + 4):
        rng = random.Random(seed + e)
        hits = sum(one_draw(rng, bits, 1 << e) for _ in range(draws))
        print(f"  W = 2^{e}: {hits / draws:6.1%}")


if __name__ == "__main__":
    main(draws=int(sys.argv[1]) if len(sys.argv) > 1 else 10_000)

Its output:

1024-bit N, 10,000 draws per window; paper reports 79.6% at W = 2^512
  W = 2^508:   0.4%
  W = 2^509:   2.1%
  W = 2^510:   8.4%
  W = 2^511:  31.2%
  W = 2^512:  79.4%
  W = 2^513:  95.4%
  W = 2^514:  98.9%
  W = 2^515:  99.7%

Limits: we did not run either algorithm from the papers, never touched a signing oracle, and did not read the “full version” the PDFs defer to. The ePrint PDF for 2026/2131 answered our scripted fetches with HTTP 403, so what we say about that study rests on its abstract page and on how the signature paper cites it. Kohli’s article was read through a public JSON mirror of X, and its text matches the quotations in SecurityWeek. Our replication follows the paper’s description of Figure 4 and is not the authors’ code; it agrees with the paper’s 79.6 percent within the sampling error of 10,000 draws. The ratios are the papers’ leading-order estimates, which the fan paper says do not predict running times.

Sources

• Pushmeet Kohli, “Advancing the frontier of cryptanalysis” (X Article, November 6, 2026)
• Modular Roots from a Restricted Oracle: Faster Affine Roots and a 1024-bit Computation (Google DeepMind working paper)
• Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS (Google DeepMind working paper, November 5, 2026)
• Forging 1024-bit RSA signatures in nearly SNFS time (IACR ePrint 2026/2131)
• SecurityWeek, Eduard Kovacs, November 9, 2026
• NIST SP 800-131A Rev. 2
• Stephen A. Weis, RSA-896 and Eric Lu, Factoring RSA-260 (Cognition)