Forging 1024-bit RSA signatures in nearly SNFS time
Researchers forged 1024-bit RSA signatures near SNFS speed using a signing oracle, without factoring the modulus.
An IACR ePrint paper implements the 2007 Joux–Naccache–Thomé algorithm to forge RSA signatures after temporary access to a raw signing or decryption oracle, without factoring the modulus. The authors report a 1024-bit demonstration totaling about 1380 CPU core-years, with cost close to the special number field sieve rather than the general number field sieve used for RSA key-size estimates. They argue practical signature security can be weaker than factoring-based guidance when such an oracle is available.
- Requires temporary access to a raw RSA signing or decryption oracle.
- 1024-bit demonstration consumed about 1380 CPU core-years.
- Runtime is close to SNFS, not a full GNFS factorization.
- Argues factoring-based key-size guidance can overstate signature security.
Alternate title: Nearly SNFS-Speed Signature Forgery Sans Factoring N (NSNFSSSFSFN) Abstract. The security of RSA is generally understood to be based on the complexity of factoring, and key size parameters are extrapolated from the general number field sieve (GNFS). However, this may not accurately represent RSA security in practical scenarios. An under-appreciated 2007 algorithm of Joux, Naccache, and Thom´e allows an attacker to forge RSA signatures after temporary access to a raw RSA signing/decryption oracle in time close to the special number field sieve (SNFS) without factoring the key. We implement and run this algorithm for 1024-bit RSA. In total, the attack took 1380 CPU core-years…
This source does not provide full text. Read it at eprint.iacr.org.