Malaysian Journal of Mathematical Sciences, August 2017, Vol. 11(S)
Special Issue: The 5th International Cryptology and Information Security Conference (New Ideas in Cryptology)
A New Attack on the RSA Cryptosystem Based on Continued Fractions
Bunder, M. and Tonien, J.
Corresponding Email: joseph_tonien@uow.edu.au
Received date: -
Accepted date: -
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<\frac{1}{3}N^{\frac{1}{4}}\), Wiener's original attack recovers the secret
key \(d\) using the convergents of the continued fraction of \(\frac{e}{N}\). Our new method uses the convergents of the continued fraction of \(\frac{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^{\frac{3}{2}}\), so if either \(d\) or \(e\) is relatively small the RSA encryption can be broken. For \(e\approx N^t\), our method can recover the secret key if \(d<2 \sqrt{2}N^{\frac{3}{4}-\frac{t}{2}}\) and certainly for \(d<2 \sqrt{2}N^{\frac{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.
Keywords: RSA, Wiener's attack, continued fractions
Indexing
