Cryptology ePrint Archive: Report 2020/1214

Cryptanalysis of RSA: A Special Case of Boneh-Durfee’s Attack

Majid Mumtaz and Ping Luo

Abstract: Boneh-Durfee proposed (at Eurocrypt 1999) a polynomial time attacks on RSA small decryption exponent which exploits lattices and sub-lattice structure to obtain an optimized bounds d < N^0.284 and d < N^0.292 respectively using lattice based Coppersmith’s method. In this paper we propose a special case of Boneh-Durfee’s attack with respect to large private exponent (i.e. d = N^&#949; > e = N^&#945; where &#949; and &#945; are the private and public key exponents respectively) for some &#945; &#8804; &#949;, which satisfy the condition d > &#966;(N) &#8722; N^&#949;. We analyzed lattices whose basis matrices are triangular and non-triangular using large decryption exponent and focus group attacks respectively. The core objective is to explore RSA polynomials underlying algebraic structure so that we can improve the performance of weak key attacks. In our solution, we implemented the attack and perform several experiments to show that an RSA cryptosystem successfully attacked and revealed possible weak keys which can ultimately enables an adversary to factorize the RSA modulus.

Category / Keywords: public-key cryptography / RSA · Cryptanalysis · small Public Key · Lattice Reduction Attack · Large private Key · Coppersmith’s Method.

Date: received 3 Oct 2020

Contact author: maji16 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20201006:094157 (All versions of this report)

Short URL: ia.cr/2020/1214


[ Cryptology ePrint archive ]