A generalised bound for the Wiener attack on RSA. (August 2020)

• Record Type: Journal Article
• Authors: Susilo, Willy; Tonien, Joseph; Yang, Guomin
• Is Part Of: Journal of information security and applications. Volume 53(2020)
• Publication Date: 2020-08
• Subjects: RSA -- Continued fractions -- Wiener technique -- Small secret exponent; 94A60 -- 11Y05 -- 11Y65; Computer security -- Periodicals; Information technology -- Security measures -- Periodicals; 005.805
• DOI: 10.1016/j.jisa.2020.102531
• Languages: English
• ISSNs: 2214-2126

Abstract

Abstract: Since Wiener pointed out that the RSA can be broken if the private exponent d is relatively small compared to the modulus N, it has been a general belief that the Wiener attack works for d < N 1 4 . On the contrary, in [1], it was shown that the bound d < N 1 4 is not accurate as it has been thought of. Specifically, for the standard assumption of the two primes p and q that q < p < 2 q, the Wiener continued fraction technique is proven to work for d ≤ 1 18 4 N 1 4 . In this paper, we consider a general condition on the RSA primes, namely q < p < α q, and we give the corresponding bound for the Wiener attack to work, which is d ≤ α 4 2 ( α + 1 ) N 1 4 . In a special case when α = 2, this general bound agrees with the result of [1] .