Naslov
A variant of Wiener's attack on RSA

Autori
Dujella, Andrej

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
8th Central European Conference on Cryptography / - Graz : Technische Universitat Graz, 2008, 29-29

Skup
8th Central European Conference on Cryptography

Mjesto i datum
Graz, Austrija, 02.07.2008. - 04.07.2008

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
RSA cryptosystem; continued fractions; cryptanalysis

Sažetak
Wiener's attack is well-known polynomial-time attack on 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 in 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(Dlog(D)) (with the space complexity O(D)).

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA