Paper 2009/037
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 reexamine 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 HowgraveGraham and Seifert's latticebased 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 multiprime RSA and Tagaki's variant of RSA. For multiprime 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, HowgraveGraham and Seifert's attack can be mounted on multiprime RSA when the private exponents are smaller than $N^{(3+r)/7r\epsilon}$ when there are $r$ primes in the modulus.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 RSAcommon modulus attackmultiprime RSATakagi's variantsmall exponent RSA
 Contact author(s)
 mjhinek @ alumni uwaterloo ca
 History
 20090125: received
 Short URL
 https://ia.cr/2009/037
 License

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} }