Name
Abstract | ||
|---|---|---|
Let (n = pq, e = n(beta)) be an RSA public key with private exponent d = n(delta), where p and q are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation ed - k phi(n) = 1 of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith's interval. We determine a Coppersmith's interval for a given RSA public key (n, e): The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if delta < beta + 1/3 alpha - 1/3 root 12 alpha beta + 4 alpha(2) provided that we have approximation p(0) >= root n of p with vertical bar p - p(0)vertical bar <= 1/2 n(alpha), alpha <= 1/2. The attack is an extension of Coppersmith's result. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1142/S0129054120500045 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | DocType | Volume |
Coppersmith's method, cryptanalysis, LLL algorithm, lattice basis reduction, multi-prime RSA, private exponent attack, RSA | Journal | 31 |
Issue | ISSN | Citations |
2 | 0129-0541 | 1 |
PageRank | References | Authors |
0.39 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hatem M. Bahig | 1 | 23 | 7.53 |
| Dieaa I. Nassr | 2 | 7 | 1.23 |
| Ashraf Bhery | 3 | 10 | 1.99 |
| Abderrahmane Nitaj | 4 | 72 | 15.00 |