Abstract | ||
---|---|---|
A well-known attack on RSA with low secret-exponent d was given by Wiener in 1990. Wiener showed that using the equation ed - (p - 1)(q - 1)k = 1 and continued fractions, one can efficiently recover the secret-exponent d and factor N = pq from the public key (N, e) as long as d N1/4. In this paper, we present a generalization of Wiener's attack. We show that every public exponent e that satisfies eX - (p - u)(q - v)Y = 1 with 1 ≤ Y X -1/4 N1/4, |u| N1/4, v = [-qu/p - u], and all prime factors of p - u or q - v are less than 1050 yields the factorization of N = pq. We show that the number of these exponents is at least N1/2-Ɛ. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-540-68164-9_12 | AFRICACRYPT |
Keywords | Field | DocType |
continued fraction,y x,prime factor,low secret-exponent,public key,factor n,public exponent e,well-known attack,cryptanalysis | Discrete mathematics,Exponent,Cryptanalysis,Factorization,Prime factor,Public-key cryptography,Mathematics,Wiener's attack | Conference |
Volume | ISSN | ISBN |
5023 | 0302-9743 | 3-540-68159-0 |
Citations | PageRank | References |
6 | 0.59 | 8 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Abderrahmane Nitaj | 1 | 72 | 15.00 |