A Unified Method for Private Exponent Attacks on RSA Using Lattices
Abstract
Let (n=pq,e=nβ) be an RSA public key with private exponent d=nδ, 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ϕ(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 δ<β+13α−13√12αβ+4α2 provided that we have approximation p0≥√n of p with |p−p0|≤12nα,α≤12. The attack is an extension of Coppersmith’s result.
Communicated by Oscar Ibarra
Remember to check out the Most Cited Articles! |
---|
Check out these Handbooks in Computer Science |