Researchers demonstrate dramatic reduction in computational cost to break RSA encryption

Cryptographic attacks on RSA have long been deemed impractical, but researchers from UC San Diego and Inria Nancy in France have published findings that could fundamentally alter that assessment—pending peer review. Their work describes a novel method capable of breaking RSA encryption in substantially less time than previously thought possible. This development carries weight because RSA-based cryptography has seen widespread deployment over decades, and despite being gradually phased out in favor of elliptic-curve cryptography and post-quantum algorithms, it remains embedded in many systems operating today.

The computational requirements for compromising an RSA key drop sharply under this attack, assuming the research withstands scrutiny and specific conditions align. For 1024-bit, 2048-bit, 3072-bit, and 4096-bit keys, the necessary operations fall from 280, 2112, 2128, and 2144 respectively down to 265, 290, 2105, and 2119.

Even at 265 operations for 1024-bit keys, the computational burden remains enormous, yet it enters territory where well-resourced actors—including certain nation-states—could feasibly mount an attempt. The researchers note that their algorithms remain far from optimization; further refinement could substantially accelerate the process, potentially aided by artificial intelligence tools and graphics processing units.

The vulnerability applies specifically to textbook, or raw, RSA—a variant less common in everyday applications like website certificates and remote access protocols, yet still present in services including Cloudflare Privacy Pass, iCloud Private Relay, and Private Cloud Compute. Hardware and services relying on PKCS #11 standards also employ this form, encompassing smart cards, USB security tokens, code-signing infrastructure, hardware security modules, and trusted platform modules. Nevertheless, satisfying the conditions necessary to execute the attack proves far more difficult in practice.

To decrypt data, an attacker must first execute an enormous volume of queries directed at the target key, accumulating sufficient data points from the key's oracle function. In real-world scenarios, this typically requires repeatedly querying a live server running that key for encryption, potentially billions of times, though offline hardware devices present an alternative target.

Within cryptographic systems, an oracle accepts input, processes it using a private key, and returns output without exposing the key itself. The textbook RSA variant under examination permits the oracle to accept any input value, enabling attackers to gather the data points required for the mathematical attack described in the research. Once sufficient data is collected, attackers can apply substantial computational resources to decrypt previously captured traffic encrypted with that same key.

Network administrators recognize that launching billions of queries against an active service invites swift countermeasures, including IP blocking and other defensive actions. Organizations like Cloudflare and Apple almost certainly maintain such protections. However, not all operators implement comparable safeguards, particularly those managing key infrastructure that receives minimal oversight, including hardware-based systems. The research team successfully demonstrated their approach against Thales Luna HSMs in both physical and cloud service configurations.

While executing this attack in practice currently demands substantial effort, the critical insight is that the threshold for feasibility may drop considerably. This raises the prospect that encrypted traffic captured today could be decrypted within weeks or months as computing capabilities advance. Additionally, other researchers may build upon these findings, uncovering further vulnerabilities in RSA implementations.