RSA with 3 primes

Question

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?

Answer 1

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.