# Chinese Remainder Theorem and RSA

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.

• When dealing with the cryptosystem you reference, don't forget to look at an update to the system which is necessary for security. – mikeazo May 9 '12 at 11:17
• I would suggest adding the mathematical details of the cryptosystem and how the CRT is used in it to your question. That way people (myself included) don't have to read the paper in order to answer your question. You are bound to get better answers. – mikeazo May 9 '12 at 11:21
• @mikeazo: The security update is not relevant for this conversation at the moment. If I manage to understand the way the CRT is applied for RSA, then I should be able to figure the rest out by myself, because it is similar. Please ignore my reference to DGK for now. – Mihai Todor May 9 '12 at 11:30
• after reading the CRT link you provided and this, perhaps you could explain exactly what you are having difficulty understanding? – mikeazo May 9 '12 at 11:33
• It's not clear to me how the CRT is applied to derive this formula: m = m_2 + (h * q), where h = q_inv * (m_1 - m_2) (mod p). I would really appreciate it if you could detail this procedure. – Mihai Todor May 9 '12 at 11:39

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, 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

• That's a really nice and detailed proof, but I need more help to understand it: First, how did you end up with this formula: $M_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \mod p-1}) \bmod p$? Could you please detail it? I don't understand how you applied Fermat's "Little" Theorem to obtain it. It's clear how you've proven the formulae for the recombination step, but I'm not able to understand how does the CRT work in this case. How do you "immediately deduce that" $m = (M^d \bmod N) \mod pq$? – Mihai Todor May 9 '12 at 18:04
• @MihaiTodor: well, for the first question, the CRT optimization splits $M$ into two parts, $M \bmod p$ and $M \bmod q$. Then, it computes the RSA private operation on both halves, that is, for the p side, we compute $((M \bmod p)^d) \bmod p$. We also note that $M^d \equiv (M \bmod p)^d \mod p$, that is, each of the two sides is effectively independent. We further note that Fermat's Little Theorem implies that $a^b \equiv a^{b \mod p-1} \mod p$ if $p$ is prime, and so it is sufficient to compute $((M \bmod p)^{d \mod p-1}) \bmod p$. – poncho May 9 '12 at 18:27
• @MihaiTodor: as for your second question, well, the Chinese Remainder theorem states that if $p$ and $q$ are relatively prime, and if $A \equiv B \mod p$ and $A \equiv B \mod q$, then $A \equiv B \mod pq$. – poncho May 9 '12 at 18:29
• Thank you very much. I can see that your knowledge of this subject is really good, but I am looking in 2 distinct books at the formulation of the CRT and I am failing to see how this simple statement that you presented above derives from it. The CRT states that a solution for a system of r linear congruences exists and is unique modulo n, where $n = \prod_{i=0}^rn_i$, but how do you use this? The "General Case" on Wikipedia doesn't help: en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case – Mihai Todor May 9 '12 at 18:48
• @MihaiTodor: set $r=2$, $n_0 = p$, $n_1 = q$. Now, CRT says that, given $B \bmod p$ and $B \bmod q$ (with $0 \le B < pq$), there is a unique $0 \le A < pq$ such that $A \equiv B \bmod p \mod p$ and $A \equiv B \bmod q \mod q$. Now, $A \equiv B$ is such a solution. Since the solution is unique, it must be the only solution (and hence we can conclude that $A \equiv B$) – poncho May 9 '12 at 18:56

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)

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.