A new improved attack on RSA
RIS ID
107538
Abstract
This paper presents a new improved attack on RSA based on Wiener's technique using continued fractions. In the RSA cryptosystem with public modulus N=pq, public key e and secret key d, if d < 1/3 N^[1/4], Wiener's original attack recovers the secret key d using the convergents of the continued fraction of e/N. Our new method uses the convergents of the continued fraction of e/N' instead, where N' is a number depending on N. We will show that our method can recover the secret key if d^2 e < 8 N^[3/2], so if either d or e is relatively small the RSA encryption can be broken. For e ~ N^[t], our method can recover the secret key if d < 2 sqrt[2] N^[3/4 - t/2] and certainly for d < 2 sqrt[2] N^[1/4]. Our experiments demonstrate that for a 1024-bit modulus RSA, our method works for values of d of up to 270 bits compared to 255 bits for Wiener.
Publication Details
Bunder, M. & Tonien, J. (2016). A new improved attack on RSA. In M. Rezal Kame. Ariffin, M. Rushdan Md. Said, M. Soeheila. Mohamad, H. Swee. Huay, H. Kamarulhaili, G. Bok. Min & A. Hamzah Abd. Ghafar (Eds.), Proceedings of the 5th International Cryptology and Information Security Conference (pp. 101-110). Malaysia: Institute for Mathematical Research (INSPEM).