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)).
Recommendations
Cites work
- scientific article; zbMATH DE number 5770427 (Why is no real title available?)
- scientific article; zbMATH DE number 3728365 (Why is no real title available?)
- scientific article; zbMATH DE number 1258344 (Why is no real title available?)
- scientific article; zbMATH DE number 1951624 (Why is no real title available?)
- scientific article; zbMATH DE number 1852133 (Why is no real title available?)
- A New Lattice Construction for Partial Key Exposure Attack for RSA
- A method for obtaining digital signatures and public-key cryptosystems
- Continued fractions and RSA with small secret exponent
- Cryptanalysis of RSA with Private Key d Less than N 0.292
- Cryptanalysis of `less short' RSA secret exponents
- Cryptanalysis of short RSA secret exponents
- Estimating the Prime-Factors of an RSA Modulus and an Extension of the Wiener Attack
- Partial Key Exposure Attacks on RSA up to Full Size Exponents
- Public Key Cryptography - PKC 2005
Cited in
(16)- The Wiener attack on RSA revisited: a quest for the exact bound
- An application of Euclidean algorithm in cryptanalysis of RSA
- Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA
- Continued fractions and RSA with small secret exponent
- Public Key Cryptography - PKC 2005
- Classical attacks on a variant of the RSA cryptosystem
- scientific article; zbMATH DE number 4148022 (Why is no real title available?)
- Another Generalization of Wiener’s Attack on RSA
- Estimating the Prime-Factors of an RSA Modulus and an Extension of the Wiener Attack
- Public Key Cryptography – PKC 2004
- Small Superset and Big Subset Obfuscation
- A new attack on three variants of the RSA cryptosystem
- Revisiting Wiener’s Attack – New Weak Keys in RSA
- On a generalization of the Dujella method
- On Wiener's attack on RSA cryptosystem
- A Wiener-type attack on an RSA-like cryptosystem constructed from cubic Pell equations
This page was built for publication: A variant of Wiener's attack on RSA
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390948)
