Skip to main content
placeholder image

The Wiener Attack on RSA Revisited: A Quest for the Exact Bound

Journal Article


Abstract


  • Since Wiener pointed out that the RSA can be broken if the private exponent d is relatively small compared to the modulus N (using the continued fraction technique), it has been a general belief that the Wiener attack works for. On the contrary, in this work, we give an example where the Wiener attack fails with, thus, showing that the bound is not accurate as it has been thought of. By using the classical Legendre Theorem on continued fractions, in 1999 Boneh provided the first rigorous proof which showed that the Wiener attack works for. However, the question remains whether is the best bound for the Wiener attack. Additionally, the question whether another rigorous proof for a better bound exists remains an elusive research problem. In this paper, we attempt to answer the aforementioned problems by improving Boneh’s bound after the two decades of research. By a new proof, we show that the Wiener continued fraction technique works for a wider range, namely, for. Our new analysis is supported by an experimental result where it is shown that the Wiener attack can successfully perform the factorization on the RSA modulus N and determine a private key d where.

Publication Date


  • 2019

Citation


  • Susilo, W., Tonien, J. & Yang, G. (2019). The Wiener Attack on RSA Revisited: A Quest for the Exact Bound. Lecture Notes in Computer Science, 11547 LNCS 381-398.

Scopus Eid


  • 2-s2.0-85068714556

Number Of Pages


  • 17

Start Page


  • 381

End Page


  • 398

Volume


  • 11547 LNCS

Place Of Publication


  • Germany

Abstract


  • Since Wiener pointed out that the RSA can be broken if the private exponent d is relatively small compared to the modulus N (using the continued fraction technique), it has been a general belief that the Wiener attack works for. On the contrary, in this work, we give an example where the Wiener attack fails with, thus, showing that the bound is not accurate as it has been thought of. By using the classical Legendre Theorem on continued fractions, in 1999 Boneh provided the first rigorous proof which showed that the Wiener attack works for. However, the question remains whether is the best bound for the Wiener attack. Additionally, the question whether another rigorous proof for a better bound exists remains an elusive research problem. In this paper, we attempt to answer the aforementioned problems by improving Boneh’s bound after the two decades of research. By a new proof, we show that the Wiener continued fraction technique works for a wider range, namely, for. Our new analysis is supported by an experimental result where it is shown that the Wiener attack can successfully perform the factorization on the RSA modulus N and determine a private key d where.

Publication Date


  • 2019

Citation


  • Susilo, W., Tonien, J. & Yang, G. (2019). The Wiener Attack on RSA Revisited: A Quest for the Exact Bound. Lecture Notes in Computer Science, 11547 LNCS 381-398.

Scopus Eid


  • 2-s2.0-85068714556

Number Of Pages


  • 17

Start Page


  • 381

End Page


  • 398

Volume


  • 11547 LNCS

Place Of Publication


  • Germany