World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

A Unified Method for Private Exponent Attacks on RSA Using Lattices

    https://doi.org/10.1142/S0129054120500045Cited by:4 (Source: Crossref)

    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 edkϕ(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α1312αβ+4α2 provided that we have approximation p0n of p with pp012nα,α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