Wiener’s attack on RSA

E831738

cryptanalytic attack

Wiener’s attack on RSA is a cryptanalytic method that efficiently recovers the private key when the RSA decryption exponent is unusually small, exploiting properties of continued fractions.

Try in SPARQL Jump to: Statements Referenced by

Statements (47)

Predicate	Object
instanceOf	cryptanalytic attack ⓘ
alsoKnownAs	Wiener’s small private exponent attack NERFINISHED ⓘ
appliesTo	RSA cryptosystem NERFINISHED ⓘ
assumes	gcd(e,φ(n)) = 1 ⓘ n = p*q with large primes p and q ⓘ standard RSA key generation ⓘ
author	Michael J. Wiener NERFINISHED ⓘ
basedOn	Diophantine approximation ⓘ properties of continued fractions ⓘ
category	attacks on public-key cryptosystems ⓘ number-theoretic cryptanalysis ⓘ
complexity	efficient ⓘ polynomial time ⓘ
conditionOn	d < n^0.25 / 3 ⓘ d is unusually small ⓘ
countermeasure	avoid small private exponents in RSA key generation ⓘ choose d sufficiently large ⓘ
exploits	small private exponent ⓘ
field	cryptanalysis ⓘ cryptography ⓘ
influenced	subsequent small-exponent attacks on RSA ⓘ
input	public key (n,e) ⓘ
methodStep	compute continued fraction expansion of e/n ⓘ enumerate convergents k_i/d_i of e/n ⓘ recover φ(n) and then d ⓘ test convergents as candidates for k/φ(n) ⓘ
motivated	RSA key generation guidelines to avoid small d ⓘ
namedAfter	Michael J. Wiener NERFINISHED ⓘ
output	factorization of n in some variants ⓘ private exponent d ⓘ
publishedIn	Information and Computation NERFINISHED ⓘ
recovers	RSA private key (n,d) ⓘ private exponent d ⓘ
relatedTo	Boneh–Durfee attack NERFINISHED ⓘ Coppersmith’s method NERFINISHED ⓘ small private exponent attacks ⓘ
requires	public exponent e ⓘ public modulus n ⓘ
securityImplication	RSA implementations must avoid small d ⓘ
targets	RSA decryption exponent ⓘ RSA private key ⓘ
threatens	RSA with small private exponent NERFINISHED ⓘ
uses	continued fractions ⓘ convergents of continued fractions ⓘ
vulnerableParameter	RSA private exponent d ⓘ
worksWhen	d is less than approximately n^0.25 ⓘ
yearProposed	1990 ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Shamir’s attack on RSA with low decryption exponent → relatedTo → Wiener’s attack on RSA ⓘ

Shamir’s attack on RSA with low decryption exponent → improvesOn → Wiener’s attack on RSA ⓘ