Cryptology ePrint Archive: Report 2008/315

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

Santanu Sarkar and Subhamoy Maitra and Sumanta Sarkar

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 {\sf theoretical bound}. Related works have also been presented by Bl{\"o}mer and May (CaLC 2001). However, the {\sf experimental bound} for $d$ that has been reached so far is only $N^{0.280}$ for 1000 bits $N$ (the upper bound on $d$ 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 {\sf theoretical results} as well as {\sf experimental evidences} to {\sf 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 strategy outperforms the existing experimental results by increasing the bounds of $d$. We provide clear evidence that RSA, with $d$ of the order of $N^{0.3}$ for 1000 bit $N$, can be cryptanalysed in practice from the knowledge of $N, e$.

Category / Keywords: public-key cryptography / Cryptanalysis, Factorization, Lattice, LLL Algorithm, RSA, Weak Keys

Date: received 21 Jul 2008, last revised 23 Sep 2008

Contact author: subho at isical ac in

Available format(s): PDF | BibTeX Citation

Note: Detailed editorial and technical revision.

Version: 20080923:060918 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]