$\newcommand{\qinv}{q_{\text{inv}}} $It could be just me, but I had a hard time understanding @poncho's anwer.

What really helped me understand RSA-CRT was Section 3 of [1] (see "references" below). I will summarize what the author explains in [1]:

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)

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)

$\newcommand{\qinv}{q_{\text{inv}}} $It could be just me, but I had a hard time understanding @poncho's anwer.

What really helped me understand RSA-CRT was Section 3 of [1] (see "references" below). I will summarize what the author explains in [1]:

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 back $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 then 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)

$\newcommand{\qinv}{q_{\text{inv}}} $It could be just me, but I had a hard time understanding @poncho's anwer.

What really helped me understand RSA-CRT was Section 3 of [1] (see "references" below). I will summarize what the author explains in [1]:

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)

$\newcommand{\qinv}{q_{\text{inv}}}$

It could be just me, but I had a hard time understanding @poncho's anwer.

What really helped me understand RSA-CRT was Section 3 of [1] (see "references" below). I will summarize what the author explains in [1]:

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 back $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 then 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: http://dx.doi.org/10.1109/ACSAC.2000.898893; DBLP: http://dblp.org/rec/html/conf/acsac/Grossschadl00)

$\newcommand{\qinv}{q_{\text{inv}}} $It could be just me, but I had a hard time understanding @poncho's anwer.

What really helped me understand RSA-CRT was Section 3 of [1] (see "references" below). I will summarize what the author explains in [1]:

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 back $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 then 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)