Welcome to the resource topic for 2008/315
Title:
RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension
Authors: Santanu Sarkar, Subhamoy Maitra, 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.
ePrint: https://eprint.iacr.org/2008/315
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .