**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^ε > e = N^α where ε and α are the private and public key exponents respectively) for some α ≤ ε, which satisfy the condition d > φ(N) − N^ε. 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 ]