New attack slashes computing power needed to crack RSA encryption, researchers claim

A new research paper from cryptographers at the University of California San Diego and Inria Nancy claims to have developed an attack that dramatically reduces the computing power required to factor the large primes underpinning RSA encryption. The attack, published as a preprint, targets what is known as textbook RSA — a bare-bones version of the algorithm that lacks the padding used in most practical implementations.

The paper reports that for 1024-bit keys, the number of operations required drops from 2^80 to 2^65; for 2048-bit keys from 2^112 to 2^90; for 3072-bit from 2^128 to 2^105; and for 4096-bit from 2^144 to 2^119. While 2^65 operations remains substantial, it falls into the range that a large state actor could feasibly attempt, the authors note. They also caution that their algorithm is unoptimised and that further improvements — possibly with AI assistance or GPU acceleration — could lower the threshold further.

The attack only works against textbook RSA implementations where the plaintext is known or guessable, and does not directly break padded RSA (such as RSA-OAEP) used in most modern systems. Nonetheless, many legacy systems and some current protocols still rely on RSA in configurations that may be vulnerable.

RSA has been gradually phased out in favour of elliptic-curve cryptography (ECC) and post-quantum algorithms, but it remains in widespread use for digital signatures, key exchange, and older encryption standards. The paper has been submitted for peer review, and the security community is awaiting validation of the results.

Why This Matters

The attack could make decades of RSA-encrypted data vulnerable if widespread, especially data encrypted with short keys (1024-bit) where feasibility is highest.
Even if optimized attacks only target textbook RSA, many real-world implementations — including certain VPNs, smart cards, and older TLS configurations — still use unpadded RSA or related schemes.
If the attack is confirmed and refined, it would accelerate the already underway migration from RSA to elliptic-curve and post-quantum cryptography.

Background

RSA has been the backbone of public-key cryptography since its invention in 1977. Its security relies on the difficulty of factoring large composite numbers. For decades, no practical factoring attack existed for adequately sized keys, and the standard recommendation moved from 1024-bit to 2048-bit or longer. The new paper claims to exploit a mathematical structure in textbook RSA that reduces the cost of factoring, reviving concerns about the algorithm's long-term safety. The work builds on earlier results, including a 2005 attack by two Cambridge scientists, but the new method claims substantially lower complexity.

Key Perspectives

Researchers (UC San Diego / Inria Nancy): They argue the attack demonstrates that textbook RSA is far weaker than previously assumed and that optimisation could make even longer keys breakable. They advocate for immediate scrutiny and a push toward post-quantum replacements. Industry practitioners: Many security engineers have already moved away from RSA for new deployments, but the attack highlights the risk of lingering RSA-dependent infrastructure. Organisations still using RSA for legacy systems may need to accelerate migration plans. Critics / Skeptics: The attack is not yet peer-reviewed and only applies to textbook RSA with known plaintext. Padded RSA (OAEP) and hybrid encryption schemes remain unaffected. Some experts caution that the claimed complexity reductions may not hold under rigorous scrutiny or may require unrealistic attack conditions.

What to Watch

The outcome of peer review: cryptographers will attempt to verify or refute the paper's claims.
Optimisation efforts: if the algorithm can be sped up with GPUs or AI, the practical threat window could shrink.
Responses from standards bodies (e.g., NIST, IETF): accelerated deprecation of RSA key sizes and recommendations for immediate migration to ECC or post-quantum algorithms.

ZOTPAPER