New Attack on the Rsa Cryptosystem Based on Continued Fractions

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 d2e < 8n 3/2,so if either d or e is relatively small the rsa encryption can be broken. for e ≈ nt,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.