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}$ ?

  • $\begingroup$ Well, do you understand the Chinese remainder theorem? $\endgroup$ – Zev Chonoles Jun 21 '15 at 6:34
  • $\begingroup$ I think I do. The constructive proof involved inverses but I could not follow it to the above conclusion. $\endgroup$ – 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$.

  • $\begingroup$ I realize my dumbness. Thanks. $\endgroup$ – PleaseHelp Jun 21 '15 at 7:12
  • 1
    $\begingroup$ No worries, happens to all of us sometimes :) $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.