I was wondering if there was any way to compute the private key $d$ when knowing only $e$ and $N$, and being able to factor $N$ as 4 prime numbers $p, q, r$ and $s$. I've been searching for days and I can't find any way.

  • $\begingroup$ "being able to factor $N$ as 4 prime numbers $p, q, r$ and $s$" - does this mean that you know/can find the values of $p, q, r, s$, or merely that you know that $N$ has 4 factors? $\endgroup$
    – Ella Rose
    Oct 8 '19 at 16:11
  • $\begingroup$ I have found p, q, r and s. But I have no clue what way to go next. I've tried calculating the totient but I don't think that's the good way because I didn't get the answer I wanted. $\endgroup$
    – Dominic
    Oct 8 '19 at 16:14

In multi-prime RSA, the definition of a valid private exponent $d$ is the same as in regular RSA: any $d$ such that $e\,d\equiv1\pmod{\lambda(N)}$, where $\lambda$ is Carmichael's function. That includes any $d$ such that $e\,d\equiv1\pmod{\varphi(N)}$, where $\varphi$ is Euler's totient.

With the factorization of $N$ into primes $p$, $q$, $r$, $s$ known and under the assumption that these 4 primes are distinct, computing a valid $d$ can be done as $$d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1,r-1,s-1)$$ or $$d\gets e^{-1}\bmod\bigl((p-1)\,(q-1)\,(r-1)\,(s-1)\bigr)$$

If some of the primes are equal, we need to use more general expressions of $\lambda(N)$ or $\varphi(N)$. The simplest might be that $\varphi(N)$ is the product of factors of $N$ with the first occurrence of a unique prime replaced by one less than this prime. For example, if $p=q$ and $r=s$ and $p\ne r$, we can use $$d\gets e^{-1}\bmod\bigl((p-1)\,q\,(r-1)\,s\bigr)$$

Also, be aware that the function $x\mapsto x^e\bmod N$ no longer is a bijection over $\Bbb Z_n$; in other words, some rare ciphertexts can correspond to multiple plaintexts. That affects plaintexts that are non-zero multiples of a prime present two times in the factorization.

For example, with

  • $N=67\times71^2\times73=24655531$,
  • $\varphi(N)=66\times70\times71\times72=23617440$,
  • $e=13$,
  • $d=10900357$, but we have the problem that
  • $71^e\bmod N$ and $3125420^e\bmod N$ both are $6603710$.

Note: the rationale of using multi-prime RSA is to obtain speedups that require not using $d$; but using $d$ will work anyway, only slower.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.