Chinese Remainder Theorem and RSA

Question

Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption algorithm of a more complex homomorphic encryption scheme (DGK) and, for some reason, I'm unable to get my head around the way the Chinese Remainder Theorem is used to achieve this. I don't have a lot of background on modular arithmetic and I would really appreciate it if someone could explain this in more detail.

Edit: Following @mikeazo's comment, I just want to understand the way CRT is applied to speed up the RSA encryption.

Answer 1

Well, the idea behind the CRT optimization is that if we know the factorization of the modulus $N$ (which we may if we have the private key), then we can split up the message $M$ into two halves (one modulo $p$, and one modulo $q$), compute each modulo separately, and then recombine them. That is, we compute:

$m_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \bmod p-1}) \bmod p$

$m_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \bmod q-1}) \bmod q$

(Note that the exponents are reduced modulo $p-1$ and $q-1$; we can do this because $p$ and $q$ are prime (and Fermat's little theorem); this is the source of a good portion of the speedup).

Then, we recombine them; that is, we find a number $m$ such that:

$m \equiv (M^d \bmod N) \mod p$

$m \equiv (M^d \bmod N) \mod q$

Because of the Chinese Remainder Theorem (and because $p$ and $q$ are relatively prime), we can immediately deduce that:

$m \equiv (M^d \bmod N) \mod pq$

which is exactly what we were trying to compute.

Now, the questions in your comments appear to be asking about the details of this recombination step.

Now, it is actually fairly easy to see the correctness of the algorithm. To make the last step work, we need to show that we have come up with a value $m$ such that:

$0 \le m < pq$

$m \equiv m_1 \mod p$

$m \equiv m_2 \mod q$

As for the the first criteria $0 \le m < pq$, well, that's straight-forward; we know that $0 \le m_2 \le q-1$, and $0 \le h \le p-1$, and so the smallest that $m$ can be is $0 + (0 * q) = 0$, and the largest it can be is $q - 1 + ((p-1)*q) = pq - 1$

As for the third criteria, that's also straight-forward; $(m_2 + (h * q)) \bmod q = m_2 \bmod q + (h*q) \bmod q = m_2 \bmod q$

The second one is a little tricker: $(m_2 + (h * q)) \bmod p = (m_2 + q * q_{inv} * ( m_1 - m_2) \bmod p) \bmod p = (m_2 + q * q_{inv} * (m_1 - m_2)) \bmod p$

Now, $q_\mathit{inv}$ is defined to be the number that, when multiplied by $q$ modulo $p$, results in 1 (that is, $q * q_\mathit{inv} \equiv 1 \mod p$). Now, because the above equation is, in fact, computed modulo $p$, we can replace $q * q_\mathit{inv}$ with 1, which gives us:

$m \bmod p = (m_2 + 1 * (m_1 - m_2)) \bmod p = m_1 \bmod p$

QED

Answer 2

What really helped me understand RSA-CRT was Section 3 of Johann Großschädl: "The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip" [1]. What follows is a summary of that section.

---

$\newcommand{\qinv}{q_{\text{inv}}}$ Let $M$ be the message, $C$ the ciphertext, $N = PQ$ the RSA modulus, and $D$ the decryption key. What you don't want to do is compute $C^D$ because $D$ is huge, and do operations modulo $N$ because $N$ is huge.

The Chinese Remainder Theorem (CRT) allows you to find $M$ using $M_P$ and $M_Q$ defined like that: $$M_P = M \bmod P$$ $$M_Q = M \bmod Q$$

And the nice thing is that $M_P$ and $M_Q$ can be computed in a much faster way than $C^D$; indeed:

\begin{aligned} M_P & = M \bmod P\\ & = (C^D \bmod N) \bmod P\\ & = C^D \bmod P & \text{(since $N = PQ$)}\\ & = C^{D \bmod (P-1)} \bmod P & \text{(Fermat's Little Theorem)} \end{aligned}

Let $D_P = D \bmod (P-1)$. You can compute $D_P$ during key generation and compute the following during decryption:

$$M_P = C^{D_P} \bmod P$$

It goes the same for $M_Q$.

Actually you can even go further in the optimization:

$$M_P = C_P^{D_P} \bmod P,\\ \text{ with } C_P = C \bmod P.$$

Now the main thing I think lacks in most explanations is this: If you have a generic CRT algorithm, you are done. Just give $M_P$ and $M_Q$ (and $P$ and $Q$) to the CRT algorithm and you get $M$.

---

The algorithm you always find when you're searching for "RSA with CRT" is more complicated than that, you have additional values to compute like $\qinv$ and $h$ etc... That's what you find in Wikipedia and in poncho's answer.

These computations correspond to the CRT, but with optimization that are possible in the special case of RSA decryption. If you apply the general CRT algorithm (Wikipedia) to RSA decryption with the optimizations we already presented, here is what you get:

$$M = (C_P^{D_P} Q (Q^{-1} \bmod P) + C_Q^{D_Q} P (P^{-1} \bmod Q)) \bmod N$$

As [1] note, you can transform this formula to compute the same thing with less operations using Fermat's Little Theorem:

$$M = (C_P^{D_P} (Q^{P-1} \bmod P) + C_Q^{D_Q} (P^{Q-1} \bmod Q)) \bmod N$$

With $Q^{P-1} \bmod P$ and $P^{Q-1} \bmod Q$ that can be precomputed.

---

The algorithm given in Wikipedia is different and I do not have a step-by-step explanation of how you get there from the general CRT formula. But indeed and as poncho shows in the second part of his answer, if you check, it works:

Let $$M' = M_Q + Q( (Q^{-1} \bmod P)(M_P-M_Q) \bmod P );$$ then

$$M' \bmod Q = M_Q ~~~~\text{(trivial)}$$

and

\begin{aligned} M' \bmod P & = M_Q \bmod P + (M_P-M_Q) \bmod P\\ & = M_P \bmod P\\ & = M_P. \end{aligned}

So $M'$ is $M$, QED.

The latter way of computing $M$ may be faster than the former because you do not have the final reduction modulo $N$ that is present in the former method.

---

References

[1] Johann Großschädl: "The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip". ACSAC 2000: 384-393 https://www.acsac.org/2000/papers/48.pdf (DOI: 10.1109/ACSAC.2000.898893; DBLP: conf/acsac/Grossschadl00)

Answer 3

Regarding the difference between the above explanation and the particular application of the Chinese Remainder Theorem from Wikipedia and various software libraries, that second algorithm is given in the PKCS #1 standard and the pertinent RFCs.

The PDF version of the standard from RSA Inc. cites the Garner Algorithm in its references.