DEV Community

Cover image for RSA encryption: how it works, how it breaks, and why 2048 still holds
Nikoloz Turazashvili (@axrisi)
Nikoloz Turazashvili (@axrisi) Subscriber

Posted on

RSA encryption: how it works, how it breaks, and why 2048 still holds

#cryptography #security #rsa #claude

On September 19, Steve Weis, a software engineer at Anthropic, factored RSA-896: a 270-digit number from the old RSA Factoring Challenge that no one had split before. He did it with Claude and up to 2,048 idle GPUs in ten days. Sixteen days earlier, Cognition had factored RSA-260 the same way. If you use RSA encryption anywhere (SSH keys, TLS certificates, the DKIM key that signs your mail), this is a good moment to understand how RSA works, how it actually breaks, and why a 2048-bit key is still a different animal.

TL;DR

  • RSA's security rests on one assumption: multiplying two large primes is easy, splitting the product back into them is not. Factor the modulus and you have the private key.
  • RSA-896 (896 bits) fell to about 30 GPU-years of spare capacity. The algorithm is the number field sieve, decades old; the new part is an AI agent porting the open-source CADO-NFS sieve to GPUs.
  • Cognition estimates RSA-1024 at about $30 million per number, a real budget for a hyperscaler. RSA-2048 is roughly a billion times harder again: about $38 quadrillion.
  • Weis, in his own words: "No new algorithmic factoring improvements" and "No new threats to deployed keys." Your 2048-bit keys are fine. Your 768-bit and 1024-bit ones are not.

How does RSA encryption work?

RSA (Rivest, Shamir, Adleman, 1977) is public-key cryptography built on modular arithmetic. Key generation, in four steps:

  1. Pick two large random primes, p and q.
  2. Multiply them: n = p × q. This is the public modulus, and its size is the "2048" in RSA-2048.
  3. Compute φ(n) = (p − 1)(q − 1). Only someone who knows p and q can do this cheaply.
  4. Pick a public exponent e (in practice almost always 65537), and compute the private exponent d so that e × d ≡ 1 (mod φ(n)).

The public key is (n, e). The private key is d. Encryption is c = mᵉ mod n; decryption is m = cᵈ mod n; signing is the same operation run with d. A toy example you can run in Python 3.8+ (textbook-sized primes, never use numbers this small):

# toy RSA: every value below is exactly what Python prints
p, q = 61, 53
n = p * q                 # 3233, the public modulus
phi = (p - 1) * (q - 1)   # 3120, needs p and q
e = 17                    # public exponent
d = pow(e, -1, phi)       # 2753, the private exponent
c = pow(65, e, n)         # encrypt m = 65 -> 2790
print(pow(c, d, n))       # decrypt        -> 65
Enter fullscreen mode Exit fullscreen mode

Real keys use primes hundreds of digits long, padding schemes (OAEP for encryption, PSS or PKCS#1 v1.5 for signatures) and a library you didn't write. The structure is the same.

How RSA breaks: factor n and the rest is one line

Look at step 3 again. Everything secret comes from p and q. If an attacker factors n, recovering the private key is two lines:

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)       # the private key
Enter fullscreen mode Exit fullscreen mode

So "breaking RSA" in the classical sense means factoring the modulus. For 3233 you can do it in your head. For a 270-digit number, trial division would outlast the universe. What works is the general number field sieve (GNFS), the fastest known classical algorithm for numbers this size. It is subexponential: each extra bit costs less than doubling the work, but it compounds, so the price still climbs steeply with key size.

That's also why this record doesn't change the math. Weis's clarification on X:

Steve Weis on X, Sep 20 2026:

He corrected himself a few hours later: "Oops, GNFS is subexponential. Just trying to emphasize factoring is still as hard and this didn't improve the runtime."

The number field sieve, stage by stage

Cognition's Eric Lu published a detailed write-up of the RSA-260 run, the closest thing to a public logbook of how a factoring record is set in 2026. The four stages, with his numbers:

Stage What it does RSA-260 (Cognition)
Polynomial selection Finds a polynomial pair that makes the later search cheaper 643 GPU-days ("anomalously high basically due to operator incompetence")
Sieving Hunts for billions of values that split into only small primes ("relations") 3,813 GPU-days; 8.3 billion unique relations
Linear algebra Combines relations so their product becomes a perfect square a 656-million-row matrix with 98.4 billion nonzeros; 467 GPU-days
Square root Takes that square root; a gcd then yields p and q overflowed, rebuilt three times; the final GPU version ran in 88 minutes

Sieving is most of the work, and every candidate is independent of every other one. That makes it the part that moves to GPUs. Linear algebra is the opposite: one giant sparse matrix where every node talks to every other node, which makes it the fragile, communication-heavy stage.

The sieve itself is open source: CADO-NFS, from INRIA and the Loria lab in Nancy, the same software behind the 2020 record. Lu's summary of his own contribution: "I report essentially no algorithmic advancements … 'good old performance engineering'". His Devin agents built "the world's highest-performance GPU lattice siever", about "10x lower cost than the previous public state of the art", and the run used "spare or fragmented compute", a single-digit share of the cluster.

RSA factoring records: from 1977 to two in sixteen days

Year Number How Source
1977 → 1994 RSA-129 (426 bits) Rivest estimated 40 quadrillion years for a 125-digit number; it took about 17 years, 600+ volunteers and two fax machines Wikipedia
2009 RSA-768 (232 digits) about 2,000 single-core CPU-years Wikipedia
2020 RSA-250 (829 bits) about 2,700 core-years, CADO-NFS Wikipedia
Sep 3, 2026 RSA-260 (862 bits) Eric Lu + Devin, about 13.5 GPU-years, ~$400k at market prices Cognition
Sep 19, 2026 RSA-896 (896 bits) Steve Weis + Claude, max 2,048 GPUs, ~30 GPU-years, 10 days saweis.net

RSA-129's secret message was "The Magic Words are Squeamish Ossifrage". Then came one record per decade, all on CPUs, and six years with none. Then two in sixteen days, both from people with spare GPUs and a coding agent.

Steve Weis on X:

The RSA-896 number once carried a $75,000 prize. RSA Labs ended the challenge prizes in 2007, so Weis got the record, the 2 million views and no cheque.

Why RSA-2048 still holds

Cognition's appendix prices the next steps at $3.50 per GPU-hour:

Modulus Estimated work Estimated cost
RSA-260 (862 bits) 13.5 GPU-years $414k
RSA-1024 (309 digits) 1,050 GPU-years $32.3 million
RSA-2048 (617 digits) 1.23 × 10¹² GPU-years $3.77 × 10¹⁶

RSA-1024 is about 78 times the work of RSA-260. Lu: "Hyperscalers or frontier AI labs could likely factor RSA-1024 numbers at a cost on the order of $30 million per number." That is a real number for a state or a large company, for one key. RSA-2048 "remains roughly a billion times harder than RSA-1024": about 37 quadrillion dollars, which is Rivest's 1977 estimate with the unit changed from years to dollars.

The deadline for RSA-2048 comes from somewhere else. NIST's draft IR 8547 marks RSA at 112 bits of security (RSA-2048) "Deprecated after 2030" and "Disallowed after 2035". The driver is post-quantum migration; better sieves play no part in it. Large quantum computers that could run Shor's algorithm don't exist yet either; Lu notes that Cognition "also has not yet built a multi-thousand-qubit quantum computer."

Did Claude break RSA?

No, and Claude says so. Weis posted its statement: "The credit belongs first to the people who built the number field sieve and CADO-NFS over several decades, and to the teams who set the earlier records. This run used their algorithm and much of their code" (X).

The Hacker News thread argued both sides. gizmodo59: "You don't need AI to solve this. Just lots of compute." charlieyu1 thought GPUs were the wrong tool: "a bunch of cheap CPU cores would do just as well", which Cognition's measured 10× cost reduction answers. dgacmu did the arithmetic: 30 GPU-years over 2,048 GPUs and ten days is about 50 % utilisation, "sneaking in factoring work between training runs". To redox99's "Quite bearish on Anthropic if they had nothing better to do with 2048 GPUs", muglug replied: "1 engineer != Anthropic".

My read: both the headline and the correction are true. The math didn't move. The price did. Idle datacenter GPUs plus an agent that ports old C to CUDA overnight turned a decade-per-record effort into a long weekend. As the best reply put it, from Allan Peng: "2 is a factor of (RSA-896 + 1)".

Which of your RSA keys to check on Monday

SSH keys. ssh-keygen -l prints the key size first. From the test keys on the card in the video:

$ ssh-keygen -l -f ~/.ssh/old-laptop.pub
1024 SHA256:/dO5WFJLKdyo6ST0GrUerhJ1BeBKzSp0Winquwr5I2A old-laptop (RSA)
$ ssh-keygen -l -f ~/.ssh/new-laptop.pub
2048 SHA256:PwD5g6OqW9kmxjOQhXSY9uFJW55E2J5mO5StT39PM7Q new-laptop (RSA)
Enter fullscreen mode Exit fullscreen mode

Anything that prints 1024 is a 2013 problem you kept: 1024-bit RSA was deprecated that year. Replace it (ssh-keygen -t ed25519 is the usual choice now) and remove the old key from authorized_keys everywhere.

DKIM keys. Mail-signing keys live in DNS, in plain sight. HN's vavkamil noticed that Instagram still publishes a 768-bit one, and we checked it the day the episode was made:

$ dig +short TXT pm._domainkey.instagram.com
"k=rsa; p=MHwwDQYJKoZIhvcNAQEBBQADawAwaAJhAIPmiAGqdq8yCwVqNOTWKgALGN+3nJg8vE2i41yJffKNZgrF…
Enter fullscreen mode Exit fullscreen mode

768 bits is RSA-768 territory: factored in 2009 on CPUs, now within reach of spare GPUs. Look up your own selectors the same way, and rotate anything under 2048.

TLS certificates. openssl x509 -in cert.pem -noout -text | grep "Public-Key" shows the modulus size. Internal PKI and old appliances are where small keys hide.

Plan for 2030. RSA-2048 is safe from sieves, and NIST still wants it gone by 2035. Inventory where RSA is used now, so the post-quantum move is a config change and nobody has to run an archaeology project.

Verdict: NEEDS REVIEW

I stamped it NEEDS REVIEW. Your 2048-bit keys are fine: no new algorithm, and a billion-fold gap to RSA-1024's price. A 768-bit key in your DNS is not fine, and the attacker no longer needs a lab, only spare GPUs and a chat window.

FAQ

Is RSA encryption still secure?
RSA-2048 and larger, yes, against classical computers: Cognition estimates RSA-2048 at about $3.8 × 10¹⁶. RSA-1024 is estimated at about $30 million per key, and NIST deprecates RSA-2048 after 2030 for post-quantum reasons.

How long does it take to break RSA-2048?
With the number field sieve, Cognition's estimate is about 1.2 trillion GPU-years. There is no known practical classical attack.

What is RSA-896?
A 270-digit (896-bit) number from the RSA Factoring Challenge, factored by Steve Weis with Claude on September 19, 2026, into two 135-digit primes.

Sources

This article expands on an episode of **The Daily Diff, a five-minute daily video on what shipped and what broke in tech.
Watch the episode · Subscribe on YouTube · the written diff lands in your inbox every morning at thedailydiff.dev.

Top comments (0)