A new attack on the RSA cryptosystem based on continued fractions
RIS ID
117427
Abstract
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 < 8N 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 √2 N 3/4-t/2 and certainly for d < 2 √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.
Publication Details
Bunder, M. & Tonien, J. (2017). A new attack on the RSA cryptosystem based on continued fractions. Malaysian Journal of Mathematical Sciences, 11 (S3), 45-57.