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

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 phi(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 phi 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.

Automated summary

This paper presents a new technique that improves the attack on RSA with small private exponent using continued fractions and multicore systems. By finding an interval containing phi(n) and generating different points within the interval, the proposed technique enables the recovery of the private key. Experimental results show that the previous bound of the private key has been extended after three attacks on RSA with small private exponents.