Cryptology ePrint Archive: Report 2015/399

New attacks on RSA with Moduli $N=p^rq$

Abderrahmane Nitaj and Tajjeeddine Rachidi

Abstract: We present three attacks on the Prime Power RSA with modulus $N=p^rq$. In the first attack, we consider a public exponent $e$ satisfying an equation $ex-\phi(N)y=z$ where $\phi(N)=p^{r-1}(p-1)(q-1)$. We show that one can factor $N$ if the parameters $|x|$ and $|z|$ satisfy $|xz|<N^\frac{r(r-1)}{(r+1)^2}$ thereby extending the recent results of Sakar~\cite{SARKAR}. In the second attack, we consider two public exponents $e_1$ and $e_2$ and their corresponding private exponents $d_1$ and $d_2$. We show that one can factor $N$ when $d_1$ and $d_2$ share a suitable amount of their most significant bits, that is $|d_1-d_2|<N^{\frac{r(r-1)}{(r+1)^2}}$. The third attack enables us to factor two Prime Power RSA moduli $N_1=p_1^rq_1$ and $N_2=p_2^rq_2$ when $p_1$ and $p_2$ share a suitable amount of their most significant bits, namely, $|p_1-p_2|<\frac{p_1}{2rq_1q_2}$.

Category / Keywords: public-key cryptography / RSA

Original Publication (in the same form): C2SI-Berger2015

Date: received 27 Apr 2015

Contact author: abderrahmane nitaj at unicaen fr

Available format(s): PDF | BibTeX Citation

Version: 20150501:120825 (All versions of this report)

Short URL: ia.cr/2015/399

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]