Cryptanalysis of RSA: A Survey

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, Internet security relies heavily on the security properties of the RSA cryptosystem. 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 the algorithm. 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.