Researchers Found a New Way to Break RSA that Doesn’t Require Factoring the Key

Security researchers have demonstrated a faster way to undermine certain RSA deployments without factoring the public modulus, challenging the assumption that RSA’s practical strength always tracks the cost of integer factorization.

The attack converts temporary access to a raw, unpadded RSA signing or decryption service into a lasting capability to forge signatures or decrypt chosen ciphertexts offline.

Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger and Emmanuel Thomé implemented the technique against a 1,024-bit RSA key. Their computation consumed 1,380 CPU core-years over five months and required 232 oracle queries. By comparison, factoring a 1,024-bit RSA modulus is estimated to require roughly 500,000 to one million core-years.

The method, called eNFS by the researchers, belongs to the number field sieve family. Instead of the general number field sieve used to factor RSA moduli, it approaches the faster “special” number field sieve complexity by replacing part of the usual mathematical work with answers from the signing oracle. Crucially, it never recovers the prime factors or RSA private key.

New Way to Break RSA

The attack unfolds in stages. An approximately 1,200-core-year precomputation depends only on the public modulus and exponent. The attacker then submits selected values to the raw RSA oracle. Once those responses are collected, access can disappear: forging any chosen signature or decrypting a target takes about another 180 core-years and can be repeated offline.

The underlying algorithm is not new. Antoine Joux, David Naccache and Emmanuel Thomé introduced it in 2007, but the new work provides its first implementation and large-scale 1,024-bit demonstration. The code builds heavily on CADO-NFS while adding the engineering needed for polynomial selection, sieving, linear algebra, root extraction, and descent at this scale.

This is not a universal RSA break. The attacker needs temporary access to a raw exponentiation oracle, a capability that conventional RSA signatures using PKCS#1 v1.5 or RSA-PSS padding normally do not expose. More plausible targets include HSM interfaces permitting raw PKCS#11 RSA operations and blind-signature protocols such as Privacy Pass, where blinded requests can provide the required oracle behavior.

The researchers estimate 2^{90} work and 2^{43} oracle queries against 2,048-bit RSA in this model, versus the commonly assigned 112-bit factoring strength. They project roughly 2^{119} work for 4,096-bit RSA, leaving it short of a modern 128-bit security target. Those costs remain beyond attackers, but could matter to well-resourced adversaries and protocols with long-lived public keys.

Organizations do not need to abandon correctly padded RSA immediately. Operators should disable unnecessary raw RSA mechanisms, audit HSM policies, limit oracle exposure, and rotate vulnerable blind-signature keys more frequently.

Protocol designers can investigate zero-knowledge proofs of well-formed requests, while longer-term migration should favor modern signature schemes and post-quantum cryptography rather than treating larger RSA keys as a permanent solution.