// HACKER NEWS — CYBERSECURITY
Factoring RSA 260
Over the past few weeks, the Cognition research team and I have been optimizing our job scheduler to better use disaggregated compute. As a proof of concept, and because I’ve enjoyed factoring numbers as a hobby for the past ten years or so, I drove a bevy of Devins to obtain a factorization of RSA-260. In order to do this, my Devins built the world's highest-performance GPU lattice siever, which enables factoring numbers at 10x lower cost than the previous public state of the art. Here is the factorization:
RSA-260 (a 260 digit number) sets a new record for the largest publicly solved RSA Factoring Challenge problem, which benchmarks the feasibility of breaking the RSA cryptosystem. The previous record, RSA-250, was set in February 2020. For reference, state-of-the-art RSA public keys contain 2048 bit (~617 digit) factoring problems, while 1024-bit (~309 digit) RSA was deprecated in 2013.
Below I’ll give some details about how this was accomplished, but here are two important takeaways:
In conclusion, the barrier to entry for cryptanalytic work, other computational mathematics more broadly, and likely most large-scale scientific computing research, is far lower than it used to be. Exciting work beckons anywhere programming can be used to solve a research problem; I encourage all to be ambitious and explore what autonomous software engineering agents can do when applied to these fields!
Contrary to some circulating claims, I did not factor RSA-260 by guessing and checking 130-digit prime numbers by hand. Cognition also has not yet built a multi-thousand-qubit quantum computer. RSA-260 was factored by a new implementation of the general number field sieve (GNFS) for GPUs, prepared and run using Devin. GNFS is the most efficient algorithm known for (most) numbers above roughly 100 digits in size and was used in previous record-breaking RSA number factorizations.
The implementation was a significantly modified CADO-NFS. I report essentially no algorithmic advancements — implementing lattice sieving and sparse linear system solving on GPUs required only “good old performance engineering” to take advantage of the preposterous memory systems of the GPU.
In total, I estimate that this factorization cost about 4,900 GPU-days, or 13.5 GPU-years, which is about $400k at current market prices. In more detail, modern GNFS implementations consist of a few stages run sequentially: polynomial selection, lattice sieving, and linear system solving. The time breakdown was:
I did this as a side project using a single-digit percentage of our cluster, in the course of optimizing our job scheduler to improve allocations to use disaggregated compute. What does this mean for larger RSA instances?
RSA-1024 is equivalent to 309 digits; according to standard GNFS scaling this is merely 78x more computation than RSA-260. I estimate the cost of factoring RSA-1024 at market GPU prices to be roughly $30M, which can trade off against wall clock time. I know for a fact that the current implementation remains significantly suboptimal; I would not be surprised if moderate further work could reduce the cost of factoring RSA-1024 by another multiple of 2.
Of course, the fact that RSA-1024 is insecure is not news. There was speculation that the NSA might have the capability to do RSA-1024 economically as early as the mid-2000s (see e.g. TWIRL or the Bernstein matrix machine). Instead, as we describe below, the main developments are (1) a potentially lower cost (in dollars and time) for the factorization, (2) potentially more parties capable of performing the factorizations (you just need enough GPUs rather than making specialized hardware), and (3) the relative ease with which non-cryptographers can now work on speeding up factoring.