Cryptanalysis of Decryption Exponent in RSA Using Lattice Reduction

Cryptanalysis of the RSA decryption exponent is a pivotal issue in public-key cryptography. Currently, many studies have given the insecure ranges of the decryption exponent, which are limited to only using the continued fraction approximation method and considering relationships between the decryption exponent and the modulus. In fact, the security of the RSA decryption exponent is also related to the encryption exponent and the primes. To propose a general security relation, the LW method, a new method to attack the RSA with small decryption exponent is given in this paper. This method first constructs a 2-dimensional lattice using the RSA public key, whose shortest vector is related to the decryption exponent. By finding the shortest vector of this lattice, the decryption exponent can be recovered. The analysis then shows that the LW method will succeed when ped²≤N², where N,e,d are the module, the encryption exponent and the decryption exponent as well as p and q are the primesp≥q of the RSA scheme. Such an attack has the same effect as attacks based on continued fraction approximation, i.e. if the continued fraction approximation succeeds, the LW method succeeds. The LW method is applied to the environment of three kinds of attacks based on the continued fraction approximation to get general insecure ranges of the decryption exponent, which shows that the LW method is general.