Forging 1024-bit RSA signatures in nearly SNFS time
Alternative title: Nearly SNFS-Speed Signature Forgery Sans Factoring N (NSNFSSSFSFN)
This repository accompanies the paper (eprint 2026/2131) and contains code implementing a variant of the number field sieve (NFS) algorithm.
It shows that an attacker can use temporary access to a raw, unpadded RSA signing/decryption oracle to gain the permanent ability to forge signatures / decrypt ciphertexts. In other words, the attacker can in essence steal the secret key (in that they can forge signatures/decrypt offline), without actually factoring the public key, and using much less computation than factoring the public key would have taken.
This demonstrates that factoring-based estimates for RSA security may be too optimistic and should be revised, but likely does not pose an immediate operational threat to most deployed RSA in the real world.
The algorithm is not polynomial-time. It's not even close. It's "subexponential-time" which is the same class as the best factoring algorithms. However it manages to be a faster subexponential-time: "special" number field sieve rather than "general" number field sieve.
Factoring a 1024-bit modulus is predicted to take 500,000-1,000,000 core-years. Running this algorithm on a 1024-bit modulus took us 1,380 core-years.
The algorithm is not new. It was invented in 2007 by Joux, Naccache, and Thomé. However this is the first public implementation and large-scale run.
Most of the code is not new; it builds on CADO-NFS.
The algorithm only works if a raw signing oracle is available. Most RSA usage in practice (that is, RSA signatures using PKCS#1v1.5 or RSA-PSS padding) do not expose such an oracle, and thus this attack does not pose a practical risk. Examples of RSA use that do expose such a signing oracle would include blind RSA signatures (e.g. Privacy Pass) or HSM APIs.
General FAQ
- Are people actually still using RSA?
Yes, particularly for digital signatures (e.g. certificates, TLS handshakes, tokens, OAuth). Key exchange for protocols like TLS uses ECDH or has transitioned to ML-KEM, and the attack does not apply to these algorithms.
- Is there an immediate need to stop using RSA?
No. The attack does not pose a practical risk for most uses of RSA. Even in the scenarios that might be vulnerable, we estimate that the attack cost for 2048-bit RSA is $2^{90}$. This is below the estimated $2^{112}$ cost to factor a 2048-bit RSA key, but is 1000 times more work than the estimated $2^{80}$ cost to factor a 1024-bit RSA key, and nobody has factored a 1024-bit RSA key in public yet. If you're still worried, elliptic curve cryptography (e.g. ECDSA or Ed25519 for signatures) does not appear to be vulnerable to this type of attack.
- Is there a non-immediate need to stop using RSA?
In our opinion, yes. This attack shows that RSA key sizes up to 4096 bits do not meet modern cryptographic security levels. The ongoing transition to post-quantum cryptography provides an opportunity to move away from legacy cryptography like RSA altogether.
- What if I use 2048-bit keys for blind RSA (e.g. Privacy Pass)?
The attack does apply. We estimate it would take $2^{90}$ work and $2^{43}$ oracle queries, which is likely below your desired security margin while being infeasible for all but the largest, most sophisticated adversaries to exploit. In the short term, you may consider shortening key epochs and increasing RSA key lengths. In the medium term, protocol designers could eliminate this attack vector by adding a zero-knowledge proof. In the long term, we hope that there will be acceptable post-quantum replacements for constructions like blind signatures.
- Can I compile this code and immediately forge 1024-bit RSA signatures?
Only if you have access to significant computational resources. With our academic-sized CPU cluster it took us months to do the forgery computation. The amount of computation was somewhere between the RSA-240 and RSA-250 records.
- Can an AI/GPUs speed up this implementation?
Almost certainly yes.
- Did you use AI/GPUs?
No.
- I use 2048-bit keys with PKCS or PSS padding for signatures. Should I be worried?
No, our attack does not seem to be feasible in this case.
- Why isn't this just the textbook RSA attack?
This attack is more powerful, because the attacker can use the temporary ability to request signatures to steal abilities equivalent to having the secret key, without actually having the secret key. (That is, being able to forge any signature of their choice, offline, in the future.) Most of the work is a single precomputation that depends only on the public key; after this is finished individual signature forgeries are much more efficient to compute.
- Why, in September 2026, am I hearing about an algorithm from 2007?
The 1024-bit computation we did took significant effort (see our paper for the hairy details). Relatively few researchers are working in this area, there is little funding, and the job market is more interested in students working in post-quantum cryptography (and now, AI). However, without this kind of computational work the algorithms would remain theoretical.
- What does
SNFS time mean?
"Special" number field sieve. This is also the running time to factor special-form integers like Mersenne numbers, which can be done more quickly than generic integers like well-formed RSA moduli. Read about it on Wikipedia if you're curious.
Special FAQ
- I use 1024-bit RSA and my modulus is
119761307924183143227323805033445425142683607945593313835302891299066516303843000359184032065280614739228104709307215190162897575231548821264285875476222037118119400262673724895150267064851629266552653543645482302630040586124860255443008330625425740446416414144702538281275665910057429738414800482721215922451. What should I do?
Change your key.
- When did you do this computation?
The 1024-bit size took us several months. It finished on August 31, 2026.
这个仓库包含了与论文（eprint 2026/2131）配套的代码，实现了一种数域筛法的变体：能临时访问原始 RSA 签名预言机的攻击者可以永久性地伪造签名或解密密文，而完全不需要分解公开的模数 N。