Skip to main content
placeholder image

A new improved attack on RSA

Conference Paper


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 Date


  • 2016

Citation


  • 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).

Scopus Eid


  • 2-s2.0-84984653369

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/6050

Has Global Citation Frequency


Start Page


  • 101

End Page


  • 110

Place Of Publication


  • Malaysia

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 Date


  • 2016

Citation


  • 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).

Scopus Eid


  • 2-s2.0-84984653369

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/6050

Has Global Citation Frequency


Start Page


  • 101

End Page


  • 110

Place Of Publication


  • Malaysia