Cryptanalysis of RSA: A Survey
Carlos Cid · 2003
1 Abstract The RSA is the most widely deployed public-key cryptosystem and is used for both encryption and digital signature. It is commonly used in securing ecommerce and e-mail, implementing virtual private networks and providing authenticity of electronic documents. It is implemented in most Web servers and browsers, and present in most commercially available security products. In fact, the ubiquity of RSA has placed it at the heart of modern information security. It would not be an overstatement to say that Internet security relies heavily on the security properties of the RSA cryptosystem. Since its invention in 1977, the RSA cryptosystem has been extensively analyzed for vulnerabilities. While no devastating attack has ever been found, years of cryptanalysis of RSA have given us a broad insight into its properties and provided us with valuable guidelines for proper use and implementation. In this paper we give a survey of the main methods used in attacks against the RSA cryptosystem. We describe the main factoring methods, attacks on the underlying mathematical function, as well as attacks that exploit details in implementations of th e algori thm. While many attacks exist, the system has proven to be very secure, and most problems arise as a result of misuse of the system, bad choice of parameters or flaws in implementations. To conclude, we list a couple of countermeasures that can be used to prevent many of the attacks described. 2 Overview of Public-Key Cryptography Cryptography can be defined as the study of mathematical techniques related to the security of transmission and storage of information. Cryptography is an important tool in today's information security, and although it has been historically linked to confidentiality, modern cryptography addresses also the issues of integrity, authentication and non-repudiation. Basically, there are two types of cryptography: symmetric-key cryptography and public-key cryptography. Symm etric-key (or secret-key) cryptography can be seen as an outgrowth of classical cryptography. If users want to s ecurely communicate with each other, they must share a key, which is used to both encrypt and decrypt messages 1 . The security of a symmetric-key scheme should rely on the secrecy of the key, as well as in the “infeasibility” of decryption without knowledge of the same. Examples of symm etric-key encryption algorithms are DES, RC4, Blowfish and AES.