Common modulus attacks on small private exponent RSA and some fast variants (in practice)

摘要

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 ≥ 7 instances of RSA are used. In particular, by construction, the attack is limited to private exponents at most N~(0.5-ε) , given sufficiently many instances, instead of the original bound of N~(1-ε).In addition, we also consider the effectiveness of the attacks when mounted against multi-prime RSA and Takagi'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-ε) is unsafe. For Takagi's scheme, we show that three or more instances with a common modulus N = p~tq is unsafe when all the private exponents are smaller than N~(2/(3( r+1))-ε). The results, for both variants, is obtained using Guo's method and are almost always successful with the inclusion of a small exhaustive search. When only two instances are available, Howgrave-Graham and Seifert's attack can be successfully mounted on multi-prime RSA, with r primes in the modulus, when the private exponents are both smaller than N~((3+r)/7r)