### Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)

M. Jason Hinek and 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
RSAcommon modulus attackmulti-prime RSATakagi's variantsmall exponent RSA
Contact author(s)
mjhinek @ alumni uwaterloo ca
History
Short URL
https://ia.cr/2009/037

CC BY

BibTeX

@misc{cryptoeprint:2009/037,
author = {M.  Jason Hinek and Charles C.  Y.  Lam},
title = {Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)},
howpublished = {Cryptology ePrint Archive, Paper 2009/037},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/037}},
url = {https://eprint.iacr.org/2009/037}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.