**A variant of Wiener's attack on RSA**

*Andrej Dujella*

**Abstract: **Wiener's attack is a well-known polynomial-time attack on a RSA
cryptosystem with small secret decryption exponent d, which works
if d<n^{0.25}, where n=pq is the modulus of the cryptosystem.
Namely, in that case, d is the denominator of some convergent
p_m/q_m of the continued fraction expansion of e/n, and therefore d
can be computed efficiently from the public key (n,e).

There are several extensions of Wiener's attack that allow the RSA cryptosystem to be broken when d is a few bits longer than n^{0.25}. They all have the run-time complexity (at least) O(D^2), where d=Dn^{0.25}. Here we propose a new variant of Wiener's attack, which uses results on Diophantine approximations of the form |\alpha - p/q| < c/q^2, and "meet-in-the-middle" variant for testing the candidates (of the form rq_{m+1} + sq_m) for the secret exponent. This decreases the run-time complexity of the attack to O(D log(D)) (with the space complexity O(D)).

**Category / Keywords: **public-key cryptography / RSA, continued fractions, cryptanalysis

**Date: **received 31 Oct 2008

**Contact author: **duje at math hr

**Available format(s): **PDF | BibTeX Citation

**Version: **20081102:232917 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]