Publication Type
Journal Article
Version
publishedVersion
Publication Date
2-2021
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 d < 1/4 root 18 N-.(25). 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 < root t (2 root 2 + 8/3) N-.(75)/root e, where e is the public exponent and t is a chosen parameter, our attack can break the RSA with the running time of O(tlog (N)). Our attack is especially well suited for the case where e is much smaller than N. When e approximate to N, the Boneh-Durfee attack outperforms ours. As a result, we could simultaneously run both attacks, our new attack and the classical Boneh-Durfee attack as a backup.
Keywords
RSA, Wiener, Boneh-Durfee, Short key attack, Continued fractions
Discipline
Information Security | Theory and Algorithms
Research Areas
Information Systems and Management
Publication
Computer Standards and Interfaces
Volume
74
First Page
1
Last Page
6
ISSN
0920-5489
Identifier
10.1016/j.csi.2020.103470
Publisher
Elsevier
Citation
SUSILO, Willy; TONIEN, Joseph; and YANG, Guomin.
Divide and capture: An improved cryptanalysis of the encryption standard algorithm RSA. (2021). Computer Standards and Interfaces. 74, 1-6.
Available at: https://ink.library.smu.edu.sg/sis_research/7292
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.1016/j.csi.2020.103470