**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 ]