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

Abderrahmane Nitaj; Tajjeeddine Rachidi

Paper 2015/399

New attacks on RSA with Moduli $N = p^{r} q$

Abderrahmane Nitaj and Tajjeeddine Rachidi

Abstract

We present three attacks on the Prime Power RSA with modulus $N = p^{r} q$ . In the first attack, we consider a public exponent $e$ satisfying an equation $e x - ϕ (N) y = z$ where $ϕ (N) = p^{r - 1} (p - 1) (q - 1)$ . We show that one can factor $N$ if the parameters $| x |$ and $| z |$ satisfy $| x z | < 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}^{r} q_{1}$ and $N_{2} = p_{2}^{r} q_{2}$ when $p_{1}$ and $p_{2}$ share a suitable amount of their most significant bits, namely, $| p_{1} - p_{2} | < \frac{p_{1}}{2 r q_{1} q_{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: 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},
      url = {https://eprint.iacr.org/2015/399}
}

Paper 2015/399

New attacks on RSA with Moduli N=prq

Abstract

Metadata

New attacks on RSA with Moduli $N = p^{r} q$