Skip to main content
placeholder image

Divide and capture: An improved cryptanalysis of the encryption standard algorithm RSA

Journal Article


Abstract


  • RSA is a well known standard algorithm used by modern computers to encrypt and decrypt messages. In some applications, to save the decryption time, it is desirable to have a short secret key d compared to the modulus N. The first significant attack that breaks RSA with short secret key given by Wiener in 1990 is based on the continued fraction technique and it works with [Formula presented]. A decade later, in 2000, Boneh and Durfee presented an improved attack based on lattice technique which works with d < N.292. Until this day, Boneh–Durfee attack remain as the best attack on RSA with short secret key. In this paper, we revisit the continued fraction technique and propose a new attack on RSA. Our main result shows that when d

Publication Date


  • 2021

Citation


  • Susilo, W., Tonien, J., & Yang, G. (2021). Divide and capture: An improved cryptanalysis of the encryption standard algorithm RSA. Computer Standards and Interfaces, 74. doi:10.1016/j.csi.2020.103470

Scopus Eid


  • 2-s2.0-85091050132

Volume


  • 74

Abstract


  • RSA is a well known standard algorithm used by modern computers to encrypt and decrypt messages. In some applications, to save the decryption time, it is desirable to have a short secret key d compared to the modulus N. The first significant attack that breaks RSA with short secret key given by Wiener in 1990 is based on the continued fraction technique and it works with [Formula presented]. A decade later, in 2000, Boneh and Durfee presented an improved attack based on lattice technique which works with d < N.292. Until this day, Boneh–Durfee attack remain as the best attack on RSA with short secret key. In this paper, we revisit the continued fraction technique and propose a new attack on RSA. Our main result shows that when d

Publication Date


  • 2021

Citation


  • Susilo, W., Tonien, J., & Yang, G. (2021). Divide and capture: An improved cryptanalysis of the encryption standard algorithm RSA. Computer Standards and Interfaces, 74. doi:10.1016/j.csi.2020.103470

Scopus Eid


  • 2-s2.0-85091050132

Volume


  • 74