A generalised bound for the Wiener attack on RSA. (August 2020) - Susilo, Willy
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] .