Malaysian Journal of Mathematical Sciences, April 2019, Vol. 13(S)
Special Issue: 3rd International Conference on Mathematical Sciences and Statistics (ICMSS2018)
A New Improved Bound for Short Decryption Exponent on RSA Modulus \(N=pq\) using Wiener�s Method
Abubakar, S. I., Ariffin, M. R. K., and Asbullah, M. A.
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
The use of short decryption exponent to mount an attack on RSA cryptosystem was first reported that the RSA modulus \(N=pq\) is insecure
if the private key \(d<\frac{1}{3}N^{0.25}\). The private key \(d\) can be recovered from the convergents of the continued fraction expansion of \(\frac{e}{N}\) which led to the factorization of \(N\) in polynomial time. Suppose \(N_1=N-\left \lceil \left [ \frac{a^{\frac{j}{i}}+b^{\frac{j}{i}}}{(2ab)^{\frac{j}{2i}}}+\frac{a^{\frac{1}{j}}+b^{\frac{1}{j}}}{(2ab)^{\frac{1}{2j}}} \right ] \sqrt{N}\right \rceil +1\) where \(a,b,i,j\) are small positive integers less than log \(N\). In this paper, we present a new improved attack on RSA which is an extension of the recent bound of \(d<2\sqrt{2}(\frac{N}{e})^{\frac{1}{2}}N^{0.25}\) that shows that the RSA modulus \(N=pq\) can be easily recovered if the short decryption exponent \(d<\sqrt{\frac{a^j+b^i}{2}}(\frac{N}{e})^{\frac{1}{2}}N^{0.375}\). Thus, from the convergents of the continued fraction of \(\frac{e}{N_1}\), the private key \(d\) can be recovered hence lead to the factorization of \(N\) in polynomial time.
Keywords: RSA, cryptanalysis, key equation, decryption, continued fraction
