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

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.

• "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? – Ella Rose Oct 8 '19 at 16:11
• 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. – 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.