Welcome to the resource topic for 2009/037
Title:
Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)
Authors: M. Jason Hinek, Charles C. Y. Lam
Abstract:In this work we re-examine two common modulus attacks on RSA. First, we show that Guo’s continued fraction attack works much better in practice than previously expected. Given three instances of RSA with a common modulus N and private exponents each smaller than N^{0.33} the attack can factor the modulus about 93\% of the time in practice. The success rate of the attack can be increased up to almost 100\% by including a relatively small exhaustive search. Next, we consider Howgrave-Graham and Seifert’s lattice-based attack and show that a second necessary condition for the attack exists that limits the bounds (beyond the original bounds) once n \geq 7 instances of RSA are used. In particular, by construction, the attack can only succeed when the private exponents are each smaller than N^{0.5-\epsilon}, given sufficiently many instances, instead of the original bound of N^{1-\epsilon}. In addition, we also consider the effectiveness of the attacks when mounted against multi-prime RSA and Tagaki’s variant of RSA. For multi-prime RSA, we show three (or more) instances with a common modulus and private exponents smaller than N^{1/3-\epsilon} is unsafe. For Takagi’s variant, we show that three or more instances with a common modulus N=p^rq is unsafe when all the private exponents are smaller than N^{2/(3(r+1))-\epsilon}. The results, for both variants, is obtained using Guo’s method and are successful almost always with the inclusion of a small exhaustive search. When only two instances are available, Howgrave-Graham and Seifert’s attack can be mounted on multi-prime RSA when the private exponents are smaller than N^{(3+r)/7r-\epsilon} when there are r primes in the modulus.
ePrint: https://eprint.iacr.org/2009/037
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .