Paper 2008/315

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

Santanu Sarkar, 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ö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$.

Note: Detailed editorial and technical revision.