Twenty Years of Attacks on the RSA Cryptosystem

Abstract

📜 Abstract

Two decades of research into inverting the RSA function produced some insightful attacks, but no devastating attack has ever been found. The attacks discovered so far mainly illustrate the pitfalls to be avoided when implementing RSA. At the moment it appears that proper implementations can be trusted to provide security in the digital world. We categorized attacks on RSA into four categories: (1) elementary attacks that exploit blatant misuse of the system, (2) low private exponent attacks serious enough that a low private exponent should never be used, (3) low public exponent attacks, (4) and attacks on the implementation. These last attacks illustrate that a study of the underlying mathematical structure is insufficient. Desmedt and Odlyzko [10], Joye and Quisquater [15] and deJonge and Chaum [9] describe some additional attacks. Throughout the paper we observed that many attacks can be defeated by properly padding the message prior to encryption or signing.

Description

✨ Summary

Dan Boneh surveys two decades of attacks against RSA, distinguishing attacks on the mathematical function from attacks caused by unsafe parameters, protocol misuse, or implementation leakage. The paper emphasizes that, as of its publication, no general attack had made properly implemented RSA insecure; instead, the known attacks identify conditions under which RSA deployments fail. The paper is published as a single-author article by Dan Boneh in the February 1999 issue of Notices of the American Mathematical Society. (crypto.stanford.edu)

RSA foundations and factoring: The survey explains the RSA trapdoor permutation, the relationship between factoring the modulus and recovering the private exponent, and the then-open question of whether breaking RSA is equivalent to factoring.
Elementary misuse: Reusing one modulus for multiple users permits users who know their own private keys to factor the shared modulus. Raw textbook RSA signatures are also malleable under multiplicative blinding, demonstrating why hashing and structured signature encoding are required.
Low private exponents: Wiener’s continued-fraction attack can recover an excessively small private exponent. The survey also discusses the stronger Boneh–Durfee bound known at the time, partial private-key exposure, and the risks of choosing CRT exponents that are too small.
Low public exponents: Coppersmith’s small-root technique, implemented using lattice reduction, provides a unifying framework for several attacks. The survey applies it to Håstad’s broadcast attack, Franklin–Reiter related-message attacks, Coppersmith’s short-padding attack, and partial key exposure. The common lesson is that deterministic or algebraically related plaintext encodings can expose RSA plaintexts even without factoring the modulus.
Implementation attacks: Timing analysis, power analysis, CRT fault attacks, and Bleichenbacher’s PKCS #1 formatting-oracle attack show that mathematical security alone is insufficient. Defenses discussed include exponentiation blinding, constant-time or fixed-delay computation, signature verification before release, randomized padding, and avoiding informative error responses.
Central engineering conclusion: RSA must be used with suitable randomized padding, safe parameter choices, protected private keys, side-channel countermeasures, fault checks, and carefully designed decryption interfaces.

The paper became a recurring teaching and reference document for RSA cryptanalysis. It has been assigned or recommended in cryptography courses at institutions including MIT, the University of Toronto, the University of Maryland, and Florida Atlantic University, where its treatment of RSA parameter attacks, lattice methods, timing attacks, and fault attacks is used to introduce practical cryptanalytic reasoning. (cs.toronto.edu)

It was also cited by later engineering-oriented work on RSA padding attacks. For example, a 1999 article in Information Security Technical Report cites the survey while presenting padding attacks as guidance for engineers, risk managers, and system architects. Later literature continues to cite the survey as a compact account of the Wiener, Coppersmith, and related-message attack families; a 2024 bibliometric study lists it among highly cited references in RSA cryptanalysis research. (sciencedirect.com)

The sources located provide clear evidence of educational and research influence, and of its use in discussions of secure padding and implementation design. They do not establish that the survey itself directly determined a particular commercial product or formal standard; the paper’s influence on industry is therefore best characterized as indirect, through the security practices and attack literature it consolidated.