Cryptology ePrint Archive: Report 2013/846

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~\cite{BODU} 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

Date: received 13 Dec 2013, withdrawn 30 Dec 2013

Contact author: abderrahmane nitaj at unicaen fr

Available format(s): (-- withdrawn --)

Version: 20131230:162102 (All versions of this report)

Short URL: ia.cr/2013/846

Discussion forum: Show discussion | Start new discussion