Name
Abstract | ||
|---|---|---|
Let n = pq be an RSA modulus with unknown prime factors of equal bit-size. Let e be the public exponent and d be the secret exponent satisfying ed = 1 (mod phi(n)) where phi(n) is the Euler totient function. To reduce the decryption time or the signature generation time, one might be tempted to use a small private exponent d. Unfortunately, in 1990, Wiener showed that private exponents smaller than 1/3n(1/4) are insecure and in 1999, Boneh and Durfee improved the bound to n(0.292). In this paper, we show that instances of RSA with even large private exponents can be efficiently broken if there exist positive integers X, Y such that vertical bar eY - XF(u)vertical bar and Y are suitably small where F is a function of publicly known expression for which there exists an integer u not equal 0 satisfying F(u) approximate to n and pu or qu is computable from F(u) and n. We show that the number of such exponents is at least O(n(3/4-epsilon)) when F(u) = p(q - u). |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1142/S1793042109002122 | INTERNATIONAL JOURNAL OF NUMBER THEORY |
Keywords | Field | DocType |
RSA cryptosystem, cryptanalysis, continued fractions, Blomer-May attack, Coppersmith's algorithm | Integer,Generation time,Discrete mathematics,Exponent,Cryptanalysis,Prime factor,Mathematics,Euler's totient function | Journal |
Volume | Issue | ISSN |
5 | 2 | 1793-0421 |
Citations | PageRank | References |
1 | 0.37 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abderrahmane Nitaj | 1 | 72 | 15.00 |