Paper 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^ε > 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- maji16 @ mails tsinghua edu cn
- History
- 2020-10-06: received
- Short URL
- https://ia.cr/2020/1214
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1214,
author = {Majid Mumtaz and Ping Luo},
title = {Cryptanalysis of {RSA}: A Special Case of Boneh-Durfee’s Attack},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1214},
year = {2020},
url = {https://eprint.iacr.org/2020/1214}
}
