Paper 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}$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. C2SI-Berger2015
Keywords
RSA
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2015-05-01: received
Short URL
https://ia.cr/2015/399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/399,
      author = {Abderrahmane Nitaj and Tajjeeddine Rachidi},
      title = {New attacks on  RSA with Moduli $N=p^rq$},
      howpublished = {Cryptology ePrint Archive, Paper 2015/399},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/399}},
      url = {https://eprint.iacr.org/2015/399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.