International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension

Authors:
Santanu Sarkar
Subhamoy Maitra
Sumanta Sarkar
Download:
URL: http://eprint.iacr.org/2008/315
Search ePrint
Search Google
Abstract: We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Boneh and Durfee (Eurocrypt 1999, IEEE-IT 2000) used Coppersmith's method (Journal of Cryptology, 1997) to factorize $N$ using $e$ when $d < N^{0.292}$, the theoretical bound. However, the experimental bound that has been reached so far is only $N^{0.280}$ for 1000 bits integers (and less for higher number of bits). The basic idea relied on LLL algorithm, but the experimental bounds were constrained by large lattice dimensions. In this paper we present theoretical results and experimental evidences to extend the bound of $d$ for which RSA is weak. This requires the knowledge of a few most significant bits of $p$ (alternatively these bits need to be searched exhaustively). We provide experimental results to highlight that the problem can be solved with low lattice dimensions in practice. Our results outperform the existing experimental results by increasing the bounds of $d$ and also we provide clear evidence that RSA with 1000 bit $N$ and $d$ of the order of $N^{0.3}$ can be cryptanalysed in practice from the knowledge of $N, e$.
BibTeX
@misc{eprint-2008-17992,
  title={RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Cryptanalysis, Factorization, Lattice, LLL Algorithm, RSA, Weak Keys},
  url={http://eprint.iacr.org/2008/315},
  note={ subho@isical.ac.in 14112 received 21 Jul 2008, last revised 21 Aug 2008},
  author={Santanu Sarkar and Subhamoy Maitra and Sumanta Sarkar},
  year=2008
}