Imagine a lock whose secret is the product of two enormous prime numbers. Anyone can see the product. Almost no one can recover the original primes. For nearly fifty years, that picture has been the public story of RSA, the public-key scheme that still signs certificates, tokens, and software across the internet. In their paper “Forging 1024-bit RSA signatures in nearly SNFS time”, researchers Laura Shea, Miro Haller, Adam Suhl, and Nadia Heninger of the University of California San Diego and Emmanuel Thomé of Inria Nancy show that the picture is incomplete. If an attacker can briefly ask a raw, unpadded RSA machine to sign or decrypt chosen numbers, that attacker can later forge any signature of choice for that same key, offline, without needing to recover the primes at all.
RSA starts with a one-way trick. You pick two huge prime numbers, p and q, and multiply them. The product, N, can be posted on a billboard. Multiplying is easy. Recovering the two primes from N is not, since the primes are large enough. That recovery problem is integer factorization, and it's why RSA was trusted.
Think of N as a padlock you can buy by the crate. Anyone can snap it shut on a box. Only the person who still has the two primes can make the matching key. In the protocol, that key is a second number, d. The lock itself is a public number, e, used together with N. To sign a message, or to unwrap a secret, you use d. To check a signature, or to lock a secret to you, everyone else uses e and N. If someone factors N and gets p and q back, they can build d and impersonate you. If they cannot factor N, the usual story says they cannot.
A 1024-bit key was the old default and is now treated as legacy. A 2048-bit key is the size most websites, tokens, and software-signing systems use today. A 3072-bit or 4096-bit key is what people reach for when they want a thicker margin against future computers, not because everyday software requires it. The paper is about a different way of not picking the lock by factoring N, but learning to mint valid signatures after a limited session with the machine that already holds d.
RSA is still used because splitting a large N into its primes has been treated as too expensive for ordinary attackers. Websites use RSA signatures in TLS certificates so a browser can check that it is talking to the intended server. OAuth uses RSA signatures on tokens so one service can prove that another service authorized a request. DNSSEC uses RSA to sign DNS records. DKIM uses RSA to sign email. Hardware security modules store private keys and perform RSA operations without exposing the key to the host computer. Blind signature systems ask a signer to produce an RSA signature on a hidden input; some privacy-token and electronic-cash protocols use this design. In each case the usual security claim is the same: if N cannot be factored, the private key remains safe.
Factoring a large RSA modulus is not a search for one hidden divisor. The fastest known method on ordinary computers, for a typical RSA number, is the general number field sieve. That method does not test primes one by one. It builds two related number systems that both connect back to N, then searches through huge ranges for values that break into small prime factors. Each useful hit is a relation. After collecting enough relations, they form a very large system of equations. Solving that system produces a factor of N.
The special number field sieve follows the same outline when N has a convenient shape, such as being close to a power of two. That extra structure makes the search cheaper. In 2007, researchers factored a 1039-bit number of that special form this way. A typical 1024-bit RSA modulus, which is not built to be special, has not been publicly factored. Current estimates say a general number field sieve factorization of 1024-bit RSA would take about 500,000 to 1,000,000 CPU core-years: that is, hundreds of thousands of processor cores, each running for a year.
The researchers' method is not the general number field sieve, nor the special number field sieve used on unusually shaped numbers. It is a 2007 algorithm by Antoine Joux, David Naccache, and Emmanuel Thomé. In the new paper, they call it the *e*th-root number field sieve.
The attack assumes a two-stage setting they call delayed-target RSA. First, the attacker knows only the public key and has temporary access to a service that will perform the private RSA operation on numbers the attacker chooses. That service is acting as a signing or decryption box. Then access ends. The attacker is given a new target number and must produce a valid RSA signature or decryption of that target.
The algorithm never finds the secret primes or the private exponent. While the box is still answering questions, the attacker collects the private operation on many specially chosen inputs. Those answers become a stock of known pieces. Later, the attacker rewrites any target they care about as a combination of those pieces. Because the attacker already knows the private operation on each piece, they can assemble a valid result for the new target without using the box again.
The computation has three parts. The first part uses only the public modulus. The researchers do a long search for numbers tied to N that break into small factors. That search does not need the private key and does not need the signing box. The second part does need the box. For each useful number from the search, and for many small primes, they ask the box to perform the raw private RSA operation, and they store the answers. They can repeat the third part later, with no further access to the box. Given a target they want to forge, they rewrite that target in terms of the stored pieces, combine the stored answers, and produce a valid signature.
The researchers ran the method against a 1024-bit RSA key stored in Thales Luna hardware security modules. The work ran from March 13 to August 31, 2026. That was about five months of cluster time and 1,380 CPU core-years in total. Most of the cost came first. Preparing the attack from the public modulus took about 1,200 core-years. The modules then answered about 4.07 billion raw RSA requests. After that, forging one chosen target took about 180 core-years and did not require the modules again. They published the target and the forged value so anyone can check the result: raising the forged value to the public exponent recovers the target, working modulo N. The code is in the public repository that accompanies the paper. The private key never left the hardware. The attack produced the ability to sign anyway.
Those figures change what RSA security ratings mean if a raw signing box is available. Security ratings are often given in bits. An 80-bit rating means work on the scale of 2⁸⁰ operations. A lower number means a weaker margin. Factoring-based tables still treat 1024-bit RSA as about 80 bits, 2048-bit RSA as about 112 bits, and 4096-bit RSA as about 144 to 152 bits.
The researchers estimate their attack at about 2⁶⁵ work for 1024-bit RSA, 15 bits below the factoring figure. Using the same scaling, they project about 2⁹⁰ work and 2⁴³ queries for 2048-bit RSA; 2¹⁰⁵ work and 2⁵¹ queries for 3072-bit RSA; and 2¹¹⁹ work and 2⁵⁷ queries for 4096-bit RSA. In this model, 4096-bit RSA does not reach the 128-bit level that many current standards treat as a baseline. They present these numbers as an upper bound. They did not show that their parameters were optimal, and later speedups, including the GPU methods already used in recent factoring work, would apply to this attack as well.
The attack does not apply to every RSA system. Most signatures in use today add padding before the private operation. Two common methods are PKCS #1 v1.5 and PSS. They attach structured extra data to the message so the number being signed is not an arbitrary integer chosen by an outsider. A service that will only sign padded inputs is a weaker helper than the raw box used in this paper. A 2007 variant of the algorithm targets that padded setting, but it is closer in cost to factoring, and the researchers did not run it at 1024 bits.
Public signatures collected from ordinary traffic also do not replace the box. Those values are hashes that have already been padded to the full length of N. They are not the specially chosen numbers the method needs. The result that matters is narrower. It applies when a stable public key is paired with a service that will perform raw, unpadded RSA on inputs the attacker chooses. In that case, security estimates based only on factoring N are the wrong measure.
Raw RSA on chosen numbers is not confined to labs. Some hardware security modules can perform that operation if the feature is enabled. This happens when software wants a signing method the module doesn't include, or when the server hashes a message and sends only the number to sign. The private key stays in the module. The server around it can still ask for signatures. Blind signature systems do the same thing on purpose. The signer returns the private RSA operation on a hidden number and cannot see whether the request is honest. Privacy Pass uses this to issue anonymous tokens. GNU Taler uses it to mint electronic coins. Because the public key is known in advance, the long preparation can finish before the requests begin. After that, an attacker can create tokens or coins the real signer never made.
1024-bit RSA has been discouraged for new signatures for years, but it’s still in use. In a scan reported in the paper, 17,455 successful TLS connections used a 1024-bit RSA certificate. Among top-level domains that returned DNSSEC keys, 89 percent of the zone-signing keys were 1024-bit RSA. In a sample of DKIM email-signing keys, about one third were 1024-bit. Those systems generally add padding before signing, so they don't match the attack described here. They show that old key sizes remain in production and must be found during migration, not assumed gone.
According to the researchers, if raw RSA or blind RSA must stay in use, the best approach is to replace the key before the long preparation can finish and turn off raw RSA when padded signatures are enough. A larger RSA key helps only inside this weaker model: 2048-bit RSA is projected near 90 bits here, not 112. NIST plans to deprecate RSA by 2030 and disallow it by 2035. The researchers treat that shift as the time to adopt algorithms whose security claims match how the keys are used. The attack does not apply to ECDSA or Ed25519 and does not need a quantum computer. For RSA with a raw signing service, factoring is not the full measure of risk.
The next step is to find every service that will perform raw RSA on chosen numbers with a long-lived key. Treat that service as able to give an attacker a lasting ability to forge signatures after a large but finite number of requests. Where blind signatures are required, add checks that the hidden message is well formed, or use a different design. Move new signing systems to algorithms that are not judged only by how hard it is to factor N.
Factoring a 1024-bit modulus remains expensive. This research shows that, with temporary access to a raw signing service, an attacker may not have to factor it at all.
This article used AI to craft the contents and is shared at no charge for educational and informational purposes only.
Red Sky Alliance is a Cyber Threat Analysis and Intelligence Service organization. We provide indicators of compromise information (CTI) via a notification/Tier I analysis service (RedXray) or an analysis service (CTAC). For questions, comments, or assistance, please contact the office directly at 1-844-492-7225 or feedback@redskyalliance.com
- Reporting: https://www.redskyalliance.org/
- Website: https://www.redskyalliance.com/
- LinkedIn: https://www.linkedin.com/company/64265941
Weekly Cyber Intelligence Briefings:
REDSHORTS - Weekly Cyber Intelligence Briefings
https://attendee.gotowebinar.com/register/7855487668891299929
Comments