The Wiener Attack on RSA Revisited: A Quest for the Exact Bound
The Wiener Attack on RSA Revisited: A Quest for the Exact Bound
复制标题
DOI：
10.1007/978-3-030-21548-4_21
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
W. Susilo;Joseph Tonien;Guomin Yang
中科院分区：
文献类型：
--
作者：
W. Susilo;Joseph Tonien;Guomin Yang
Since Wiener pointed out that the RSA can be broken if the private exponentdis relatively small compared to the modulusN(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 boundis 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 whetheris 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 $$d \le \frac{1}{\root 4 \of {18}} N^{\frac{1}{4}} = \frac{1}{2.06...} N^{\frac{1}{4}}$$. 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 modulusNand determine a private keydwhere $$d = \left\lfloor \frac{1}{\root 4 \of {18}} N^{\frac{1}{4}} \right\rfloor $$.
Since Wiener pointed out that the RSA can be broken if the private exponentdis relatively small compared to the modulusN(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 boundis 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 whetheris 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 $$d \le \frac{1}{\root 4 \of {18}} N^{\frac{1}{4}} = \frac{1}{2.06...} N^{\frac{1}{4}}$$. 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 modulusNand determine a private keydwhere $$d = \left\lfloor \frac{1}{\root 4 \of {18}} N^{\frac{1}{4}} \right\rfloor $$.