Small Private Exponent Attacks on RSA Using Continued Fractions and Multicore Systems

Abstract

The RSA (Rivest–Shamir–Adleman) asymmetric-key cryptosystem is widely used for encryptions and digital signatures. Let (n,e) be the RSA public key and d be the corresponding private key (or private exponent). One of the attacks on RSA is to find the private key d using continued fractions when d is small. In this paper, we present a new technique to improve a small private exponent attack on RSA using continued fractions and multicore systems. The idea of the proposed technique is to find an interval that contains ϕ(n), and then propose a method to generate different points in the interval that can be used by continued fraction and multicore systems to recover the private key, where ϕ is Euler’s totient function. The practical results of three small private exponent attacks on RSA show that we extended the previous bound of the private key that is discovered by continued fractions. When n is 1024 bits, we used 20 cores to extend the bound of d by 0.016 for de Weger, Maitra-Sarkar, and Nassr et al. attacks in average times 7.67 h, 2.7 h, and 44 min, respectively.

Keywords

• continued fractions
• private exponent attack
• RSA
• Wiener’s attack
• integer factorization
• multicore systems