A Unified Method for Private Exponent Attacks on RSA Using Lattices
Abstract
Let be an RSA public key with private exponent where and 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 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 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 provided that we have approximation of with 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 |