# 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 \mod p-1}) \bmod p$

$M_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \mod 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 the; that is, we find a number $m$ such that:

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

$m = (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 = (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_{inv}$ is defined to be the number that, when multiplied by $q$ modulo $p$, results in 1 (that is, $q * q_{inv} = 1 \mod p$). Now, because the above equation is, in fact, computed modulo $p$, we can replace $q * q_{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