Researchers have unveiled a novel technique that undermines certain RSA implementations without ever factoring the public modulus—turning what was once temporary access into a permanent threat. This method, demonstrated on a 1,024-bit RSA key, drastically reduces the computational cost compared to traditional integer factorization.
What’s been discovered
The new strategy, named eNFS, allows attackers who gain temporary control over a raw-RSA service—one that processes signatures or decryption without padding—to forge signatures or decrypt messages long after access ends. It hinges on collecting oracle responses rather than extracting private key primes.
Using a 1,024-bit RSA key, the research team spent about 1,380 CPU core-years over five months, issuing 232 specially crafted queries to the oracle. That’s vastly more efficient than the estimated 500,000–1,000,000 core-years that classic factoring of a 1,024-bit modulus would demand.
How eNFS changes the landscape
This attack is based on the “number field sieve” family of algorithms. Instead of relying on the general NFS used in standard RSA attacks, eNFS exploits elements of the “special” NFS, replacing certain algebraic computations with responses from the signing/decryption oracle. Importantly, it never reconstructs the private key or primes—it simply uses oracle output to forge signatures or decrypt chosen ciphertexts offline.
The method involves an initial precomputation phase, roughly 1,200 core-years, that depends only on publicly known components (the modulus and exponent). Once that’s complete, an attacker sends specific values to the oracle. Afterwards, even if oracle access is revoked, forged signatures or decryption of selected ciphertexts can be carried out offline with around 180 more core-years.
The idea isn’t entirely new—its roots trace back to work from 2007—but this latest effort is the first large-scale implementation on a 1,024-bit key. The researchers built on existing number field sieve tools and extended them with engineering for polynomial selection, sieving, descent, linear algebra, and related number-theoretic machinery.
When and where it applies (and when it doesn’t)
This isn’t a universal RSA vulnerability. It only applies when raw, unpadded RSA operations are exposed—something that many systems avoid. Standard RSA signature schemes using PKCS#1 v1.5 or PSS padding typically prevent these attacks. More likely targets include hardware security modules (HSMs) that do allow raw RSA via interfaces like PKCS#11, or blind-signature schemes such as Privacy Pass where an attacker could submit blinded inputs to an oracle and receive the necessary responses.
For key sizes of 2,048 bits, the team estimates about 2^90 computational work plus 2^43 oracle queries would be needed—with 4,096-bit keys requiring roughly 2^119 work. These numbers are much higher, and still out of reach for most adversaries, though this may shift for those with high resources and when protocols rely on long-lived public keys.
What should operators and protocol designers do?
Systems using raw RSA should be audited immediately. Disabling or restricting raw exponentiation in HSMs and minimizing oracle exposure can significantly mitigate risk. Keys used in blind-signature protocols should be rotated more often. For future proofing, many are recommending migration toward modern signature schemes that resist these oracle-based attacks and even considering post-quantum cryptography, instead of simply increasing RSA key sizes.
This breakthrough emphasizes a critical shift in how we assess RSA security. It’s no longer enough to assume that threats scale only with factoring costs—oracle access changes the game. Watch for shifts in standards, tightening of cryptographic implementations, and a surge in interest around padding schemes and post-quantum alternatives. Protocols once thought safe may no longer be so.
