Title: An improved cryptanalysis of large RSA decryption exponent with constrained secret key

Authors: Majid Mumtaz; Luo Ping

Addresses: Key Laboratory for Information Systems Security, School of Software, Tsinghua University, Beijing 100084, China ' Key Laboratory for Information Systems Security, School of Software, Tsinghua University, Beijing 100084, China

Abstract: In this study, we revisit the RSA public key cryptosystem in some special case of Boneh and Durfee's attack when the private key d assumes to be larger than the public key e. The attack in this study is the variation of an approach adopted by Luo et al. (2009) based on large decryption exponent. They had chosen a large private key (d > e) and found the weak keys in some specific range between N^0.258 ≤ e ≤ N^0.857. We highlight the shortcomings and new improvements in our study with more refined bound analysis up to the range between N^0.104 ≤ e ≤ N^0.923. Our experimental results revealed more refined bounds using lattice-based Coppersmith's method. In our experimental yield, we find the small roots of the devised polynomial, which helps to factorise the RSA modulus of size up to 1,024-bits. We also measure the probability of a specific range of weak keys, which further certify our results about weak keys in an RSA constrained secret key environment.

Keywords: RSA; cryptanalysis; low public keys; lattice reduction; constrained keys; large private key.

DOI: 10.1504/IJICS.2021.113168

International Journal of Information and Computer Security, 2021 Vol.14 No.2, pp.102 - 117

Received: 25 Apr 2019
Accepted: 16 Sep 2019
Published online: 23 Feb 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article