# A variant of Wiener's attack on RSA

Andrej Dujella

Arxiv ID: 0811.0063•Last updated: 8/30/2021

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 |α- 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)).

#### PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.