Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2019

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.

Keywords

RSA, Continued fractions, Wiener technique, Small secret exponent

Discipline

Information Security

Research Areas

Cybersecurity

Publication

Information Security and Privacy: 24th Australasian Conference, ACISP 2019, Christchurch, New Zealand, July 3-5: Proceedings

Volume

11547

First Page

381

Last Page

398

ISBN

9783030215477

Identifier

10.1007/978-3-030-21548-4_21

Publisher

Springer

City or Country

Cham

Additional URL

https://doi.org/10.1007/978-3-030-21548-4_21

Download

Share

COinS