2
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2019 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, 2019 at 16:14
  • $\begingroup$ [ the security of Multi-prime RSA is undeniably better than the standard RSA] $\endgroup$
    – user108420
    Mar 20, 2023 at 2:05
  • $\begingroup$ @user108420: are you Captain Nemo? He's quoted in two patents has having writen "RSA Moduli Should Have 3 Prime Factors" in August 1996. I wish I could locate the document. See this question. $\endgroup$
    – fgrieu
    Mar 20, 2023 at 6:10

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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