Decrypting Multi-Prime RSA with e, N, and factors of N given

Question

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.

Answer 1

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.