Cryptanalysis of RSA with two decryption exponents

In this paper, we consider RSA with N=pq, where p,q are of same bit size, i.e., q<p<2q. We study the weaknesses of RSA when multiple encryption and decryption exponents are considered with same RSA modulus N. A decade back, Howgrave-Graham and Seifert (CQRE 1999) studied this problem in detail and presented the bounds on the decryption exponents for which RSA is weak. For the case of two decryption exponents, the bound was N^0.357. We have exploited a different lattice based technique to show that RSA is weak beyond this bound. Our analysis provides improved results and it shows that for two exponents, RSA is weak when the RSA decryption exponents are less than N^0.416. Moreover, we get further improvement in the bound when some of the most significant bits (MSBs) of the decryption exponents are same (but unknown).