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

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 commonmodulus N and private exponents each smaller than N0.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 N0.5–ε, given sufficiently many instances, instead of the original bound of N1–ε.

Keywords

• rsa
• common modulus
• multi-prime rsa
• takagi's scheme
• small private exponent
• lattice reduction
• continued fractions