Cryptology ePrint Archive: Report 2014/035

A new attack on RSA with a composed decryption exponent

Abderrahmane Nitaj and Mohamed Ould Douh

Abstract: In this paper, we consider an RSA modulus $N=pq$, where the prime factors $p$, $q$ are of the same size. We present an attack on RSA when the decryption exponent $d$ is in the form $d=Md_1+d_0$ where $M$ is a given positive integer and $d_1$ and $d_0$ are two suitably small unknown integers. In 1999, Boneh and Durfee presented an attack on RSA when $d<N^{0.292}$. When $d=Md_1+d_0$, our attack enables one to overcome Boneh and Durfee's bound and to factor the RSA modulus.

Category / Keywords: public-key cryptography / RSA, Cryptanalysis, Factorization, LLL algorithm, Coppersmith's method

Original Publication (with minor differences): International Journal on Cryptography and Information Security (IJCIS), Vol.3, No. 4, December 2013

Date: received 11 Jan 2014

Contact author: abderrahmane nitaj at unicaen fr

Available format(s): PDF | BibTeX Citation

Version: 20140112:132935 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]