A variant of Wiener's attack on RSA

DOI10.1007/S00607-009-0037-8zbMATH Open1171.94005arXiv0811.0063OpenAlexW2103489534WikidataQ57595891 ScholiaQ57595891MaRDI QIDQ2390948FDOQ2390948

Andrej Dujella

Publication date: 10 August 2009

Published in: Computing (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0811.0063

zbMATH Keywords

RSAattackpublic-key cryptosystem

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

• A method for obtaining digital signatures and public-key cryptosystems
• Cryptanalysis of short RSA secret exponents
• Partial Key Exposure Attacks on RSA up to Full Size Exponents
• Title not available (Why is that?)
• Cryptanalysis of RSA with Private Key d Less than N 0.292
• Title not available (Why is that?)
• Continued fractions and RSA with small secret exponent
• Cryptanalysis of `less short' RSA secret exponents
• Estimating the Prime-Factors of an RSA Modulus and an Extension of the Wiener Attack
• Title not available (Why is that?)
• A New Lattice Construction for Partial Key Exposure Attack for RSA
• Title not available (Why is that?)
• Title not available (Why is that?)
• Public Key Cryptography - PKC 2005

Cited In (10)

• An application of Euclidean algorithm in cryptanalysis of RSA
• Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA
• Public Key Cryptography - PKC 2005
• Об обобщении метода Дюжелла
• Title not available (Why is that?)
• Another Generalization of Wiener’s Attack on RSA
• Public Key Cryptography – PKC 2004
• Small Superset and Big Subset Obfuscation
• Revisiting Wiener’s Attack – New Weak Keys in RSA
• A Wiener-type attack on an RSA-like cryptosystem constructed from cubic Pell equations

   Recommendations

• Another Generalization of Wiener’s Attack on RSA 👍 👎
• Title not available (Why is that?) 👍 👎
• Public Key Cryptography – PKC 2004 👍 👎
• Cryptanalysis of `less short' RSA secret exponents 👍 👎
• Cryptanalysis of RSA with Private Key d Less than N 0.292 👍 👎

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)