RSA’s safety is usually summarised as the difficulty of factoring huge numbers. Ars Technica reports a new method that breaks RSA without factoring at all, and faster than earlier techniques. The distinction matters more than the summary suggests.
The RSA problem in plain terms
RSA is a public-key system: a user publishes a large modulus, the product of two secret prime numbers, together with a public exponent. Anyone can encrypt a message or verify a signature using those public values. Only the holder of the matching private key can decrypt or sign.
An attacker who wants to defeat RSA has an obvious route. Recover the two prime factors of the published modulus, and the private key follows by simple arithmetic. That is the integer factorisation problem, and it is the one most people have heard of.
But factoring is not what an attacker actually needs. What they need is the ability to compute an e-th root modulo the published number — to undo the public operation. Cryptographers call this the RSA problem, and it is a distinct question. Factoring certainly solves it. Whether the reverse holds, whether any method of computing those roots must secretly amount to factoring, has never been proved. The gap between the two problems is where this story sits.
Where the question came from
When public-key cryptography moved from theory to deployment, RSA became the workhorse: it handled key exchange, digital signatures and certificates across the emerging internet. Its security argument was informal from the start. Nobody proved that breaking RSA was as hard as factoring; the community observed that no better approach had been found, that factoring itself had resisted decades of sustained effort, and built on that.
Some other schemes were designed precisely to close that gap. One well-known alternative was constructed so that anyone able to break it could be turned, mechanically, into a factoring algorithm — a property known as a reduction to factoring. RSA has no such proof, and the absence has been recognised as a genuine open problem rather than an oversight.
Work in the theory community has gone further, producing results suggesting that a certain natural class of proofs — those built from straight-line algebraic manipulations — is unlikely ever to establish the equivalence, at least for small public exponents. That falls well short of showing the two problems differ. It does show that the question has been examined seriously and left unresolved, and that practitioners have been relying on an assumption rather than a theorem.
How RSA is broken today
Attacks on RSA deployments have rarely involved factoring the modulus. Most of them exploit the surrounding machinery.
The dominant category is implementation failure. Padding schemes turn a raw mathematical operation into a usable encryption function, and flaws in an older, widely deployed padding standard allowed attackers to decrypt traffic by sending a long series of carefully crafted ciphertexts and observing which ones the server rejected. Variants of that weakness have resurfaced repeatedly in TLS implementations. Separately, timing differences, power consumption and induced hardware faults have all been used to extract private keys from devices performing RSA operations, without touching the mathematics of factoring.
A second category is weak key generation. When a device generates primes from a poor source of randomness, two independently generated keys can share a prime factor, and an attacker holding a large collection of public keys can find those collisions cheaply.
A third involves the structure of messages. If a very small public exponent is used and the message is short or predictable, mathematical techniques based on lattice reduction can recover the plaintext directly, leaving the private key untouched and the modulus unfactored.
Ars Technica reports that a new result adds a further category: a general way of breaking RSA that does not proceed by factoring, and that is faster than what came before. The technical details, the cost of the attack, and whether it threatens key sizes in everyday use are not established here.
Common misunderstandings
The most frequent error is treating “RSA is secure” and “factoring is hard” as the same statement. They are linked but not identical, and the link runs in only one direction that anyone has proved.
A second is assuming that any break must be catastrophic. Cryptanalytic advances are usually incremental: a method that shaves a factor off the work required, or that applies only to particular parameter choices, can be a significant theoretical result while leaving deployed systems intact for years. Whether a given advance crosses from interesting to urgent depends on numbers that take time to settle.
A third is the belief that quantum computing is the only live threat to RSA. A quantum factoring algorithm does, in principle, render RSA insecure, and that prospect is driving the migration to post-quantum schemes. But classical cryptanalysis has not stopped, and the RSA problem remains a target in its own right.
A fourth is conflating the algorithm with the company of a similar name, and with the many products and standards that carry the acronym. The algorithm is a mathematical construction in the public domain of knowledge; it is implemented independently in every major cryptographic library.
Where to look next
Readers wanting the substance rather than the headline should look for the original research paper once it circulates, and specifically for two things: the class of RSA parameters the method applies to, and its concrete cost compared with the best known factoring algorithms at the same key sizes. Those determine whether anything needs to change.
Standards bodies are the next place to watch. National standards agencies and internet engineering groups publish guidance on acceptable key sizes and algorithm choices, and they revise it when cryptanalysis warrants. Their advice is slower than news coverage but considerably more reliable as a basis for decisions.
For background, introductory cryptography textbooks treat the distinction between the factoring assumption and the RSA assumption directly, and the open-source implementations in widely used libraries show how padding, key generation and constant-time arithmetic are handled in practice. The post-quantum migration programmes already under way are also relevant, since organisations moving away from RSA for quantum reasons are, incidentally, reducing their exposure to classical results of this kind.
Frequently asked questions
Is RSA broken?
Not in any practical sense that can be confirmed here. Ars Technica reports a new method of attacking RSA that does not rely on factoring and is faster than previous approaches. Whether it is efficient enough to threaten keys of the sizes used on the public internet is not established in that report. Cryptographic results of this kind usually require careful analysis before their operational significance becomes clear.
What is the difference between factoring and the RSA problem?
Factoring means splitting the public modulus back into the two secret primes that produced it. The RSA problem means computing e-th roots modulo that number — reversing the public operation directly. Anyone who can factor can solve the RSA problem, so factoring is at least as hard. Whether the reverse is true has never been proved, which is why an attack that avoids factoring is theoretically significant.
Does this mean HTTPS is unsafe?
There is no basis for saying so. Modern TLS connections increasingly use elliptic-curve key exchange rather than RSA, though RSA remains common in certificates and signatures. Any practical impact would depend on the attack’s cost at real key sizes, which is not known here. Browser vendors, certificate authorities and standards bodies would announce changes to accepted algorithms if an attack proved deployable.
Why do cryptographers still use RSA?
Largely inertia and interoperability. RSA is implemented everywhere, well understood by developers, and supported by decades of hardware and protocol infrastructure. Its security assumption has held up against sustained attack even without a proof. Newer elliptic-curve systems offer equivalent security with smaller keys and have displaced RSA in many protocols, and post-quantum schemes are now being standardised for long-term use.
Should I switch away from RSA?
For most people this is not an individual decision — it is made by software vendors and protocol designers. Organisations running their own cryptography should already be planning a migration to post-quantum algorithms, on the timetable set by national standards agencies, since a quantum computer capable of factoring would break RSA regardless of this result. That work addresses both threats at once.
Sources and further reading
- Ars Technica, security section — the report of a new non-factoring attack on RSA that prompted this explainer
- National standards agencies publishing key-size and algorithm guidance, including post-quantum migration timelines
- Internet engineering standards documents describing RSA padding schemes and their known weaknesses
- Academic cryptography textbooks and course notes covering the factoring assumption and the RSA assumption as separate problems
Surfaced from the rss:arstechnica signal “a new cryptographic attack”. AI-assisted draft, editorially reviewed.
