RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension.
Santanu Sarkar, Subhamoy Maitra, Sumanta Sarkar · 2008
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. Related works have also been presented by Blömer and May (CaLC 2001). However, the 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 theoretical results as well as 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 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.