# Chinese remainder theorem - RSA

The following is a excerpt from RSA Decryption correctness proof (section 4) :

\begin{align} C^d &\equiv M\pmod {p} \tag{1}\\ C^d &\equiv M\pmod {q} \tag{2} \end{align} Now by the Chinese Remainder Theorem, since $\gcd(p, q) = 1$ ($p$ and $q$ are different primes), there is exactly one number mod $pq$ that has properties $(1)$ and $(2)$ – it is $M \pmod{pq}$. So $C^d\equiv M\pmod {pq}$.

Question : How is that number $M\pmod {pq}$ ?

• Well, do you understand the Chinese remainder theorem? – Zev Chonoles Jun 21 '15 at 6:34
• I think I do. The constructive proof involved inverses but I could not follow it to the above conclusion. – PleaseHelp Jun 21 '15 at 6:43

$M$ is an integer. Suppose $X$ is some integer with the property that $$X\equiv M\bmod p,\qquad X\equiv M\bmod q.$$ The Chinese remainder theorem then says that if $Y$ is any integer such that $$Y\equiv M\bmod p,\qquad Y\equiv M\bmod q$$ then $Y\equiv X\bmod pq$. But obviously, $M$ is an integer with the property that $$M\equiv M\bmod p,\qquad M\equiv M\bmod q.$$ Therefore, any $Y$ such that $$Y\equiv M\bmod p,\qquad Y\equiv M\bmod q$$ must satisfy $Y\equiv M\bmod pq$.

• I realize my dumbness. Thanks. – PleaseHelp Jun 21 '15 at 7:12
• No worries, happens to all of us sometimes :) – Zev Chonoles Jun 21 '15 at 7:12

$p$ and $q$ being two different primes, there exists two integers $m,n$ such that $$mp-nq=1$$

Your two equations can also be rewritten

$$C^d = M +\alpha p \\ C^d = M + \beta q$$

Multiplying the first by $-nq$ and the second by $mp$ and summing them, we get $$(mp-nq)C^d = (mp-nq)M + (\beta m-\alpha n)pq$$ And now returning to a modular expression you get $$C^d = M \mod {pq}$$

As $gcd(p,q) =1$, we have a group isomorphism $$\pi: \mathbb Z / pq \rightarrow \mathbb Z / p \times \mathbb Z / q, \ x + pq \mathbb Z \mapsto (x + p \mathbb Z, x + q \mathbb Z)$$

You're looking for some $M + pq \mathbb Z \in \mathbb Z$ that satifies $\pi (M + pq \mathbb Z) = (C^d + p \mathbb Z, C^d + q \mathbb Z)$. By the above such a value $M$ exists and is unique.