Attacks on Low Private Exponent RSA: An Experimental Study

摘要

RSA cryptosystem is the most popular public key cryptosystem which provides both secrecy and digital signatures. Due to RSA's popularity, many attacks on it have been developed. In this paper, we consider experimentally attacks on low private exponent RSA and find that: (i) lattice attack using Gauss lattice reduction algorithm is more effective than Wiener attack, and (ii) it is not always to recover decryption exponent even if its bit-length is less than one-quarter bit-length of the modulus. The results also raise an open question on the conditions to recover the RSA private key from public key.