7
$\begingroup$

I was trying to understand how does RSA with 3 primes work. I have checked Wikipedia but yet I didn’t fully understand their solution. I would like to know how do you encrypt for $n=p*q*r$

How do you decrypt for it, and why is it still proven to work?

$\endgroup$
  • 3
    $\begingroup$ Encryption and decryption are still $m^e\bmod n$ and $c^d\bmod n$, where it must hold that $ed\equiv1\bmod\lambda(n)$. The formulas for $\lambda(n)$ and (if used) the CRT change a little for more prime factors, but all of the number theory remains exactly the same. Could you perhaps be a bit more precise about what you do not understand? $\endgroup$ – yyyyyyy Feb 22 '17 at 21:14
  • $\begingroup$ This answers the "How do you decrypt" part of the question for an arbitrary number of factors, gives a numeric example with 3 factors, quantifies the time saving, and gives security caveats. $\endgroup$ – fgrieu Feb 23 '17 at 10:34
  • $\begingroup$ Just one hint for an additional exercise: You could think about why 2 primes are optimal for RSA cryptography. $\endgroup$ – user27950 Feb 23 '17 at 15:38
11
$\begingroup$

I would like to know how do you encrypt for $n=pqr$?

Encryption works precisely the same as regular RSA; you pad the message $m$, and then compute $m^e \bmod n$. In fact, the encryptor need not know that this is multiprime RSA, and not regular RSA.

How do you decrypt for it?

Well, you could do the same as regular textbook RSA, compute $m = c^d \bmod n$ for the decryption exponent $d$.

However, that's silly; the entire point of multiprime RSA is that it's faster than regular RSA, and the above isn't.

Instead, what we do is first compute the three values:

$$m_p = (c \bmod p)^{d_p} \bmod p$$ $$m_q = (c \bmod q)^{d_q} \bmod q$$ $$m_r = (c \bmod r)^{d_r} \bmod r$$

and then find the value $m$ with $m \equiv m_p \pmod p$, $m \equiv m_q \pmod q$, $m \equiv m_r \pmod r$

That's actually easier than it sounds; with regular RSA CRT, we have $m_p, m_q$, and combine them into $m$. Here, we do the sample, except we two it twice; first, we might combine $m_p, m_q$ into $m_{pq}$ (with $m \equiv m_{pq} \pmod {pq}$, and then combine $m_{pq}$ and $m_r$ to form $m$.

why is it still proven to work

The same reason RSA work. We have the result of encrypting $m$ and then decrypting the result being the same value modulo $p$; that's because we set $d_p = e^{-1} \pmod {p-1}$, and so $(m^e)^{d_p} \equiv m^{e \cdot d_p} \equiv m \bmod p$, and similarly for $q$ and $r$. Hence, as $p, q, r$ are relatively prime, then if both $m$ and the end result are between $0$ and $pqr-1$, then they must be the same.

$\endgroup$
  • $\begingroup$ I got most of it, thanks for your answer. Just for clarification, how does the Mp Mq combine to Mpq (mod pq) if you could please write it in more detail please $\endgroup$ – Jeremy Shiklov Feb 22 '17 at 22:09
  • 2
    $\begingroup$ @JeremyShiklov: the standard way is to have $q^{-1} \bmod p$ precomputed ($qinv$), and then compute $m_{pq} = m_q + q( (qinv \cdot (m_p - m_q)) \bmod p)$ $\endgroup$ – poncho Feb 22 '17 at 22:41
  • 1
    $\begingroup$ How do I generate the public key e for the encryption of m ? $\endgroup$ – Jeremy Shiklov Apr 4 '17 at 7:47
  • $\begingroup$ @JeremyShiklov: pick a value $e>1$ that is relatively prime to $p-1, q-1, r-1$. $\endgroup$ – poncho Apr 4 '17 at 12:38

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.