A new improved attack on RSA
Martin W. Bunder, Joseph Tonien · Research Online (University of Wollongong) · 2016
This paper presents a new improved attack on RSA based on Wiener's technique using continued fractions. In the RSA cryptosystem with public modulus N=pq, public key e and secret key d, if d < 1/3 N^[1/4], Wiener's original attack recovers the secret key d using the convergents of the continued fraction of e/N. Our new method uses the convergents of the continued fraction of e/N' instead, where N' is a number depending on N. We will show that our method can recover the secret key if d^2 e < 8 N^[3/2], so if either d or e is relatively small the RSA encryption can be broken. For e ~ N^[t], our method can recover the secret key if d < 2 sqrt[2] N^[3/4 - t/2] and certainly for d < 2 sqrt[2] N^[1/4]. Our experiments demonstrate that for a 1024-bit modulus RSA, our method works for values of d of up to 270 bits compared to 255 bits for Wiener.