RSA
- $\gcd(p,q) = 1$
- $N = pq$
- $ed = 1 \bmod{\phi(N)}$
The proof of correctness of RSA involves 2 cases
Case 1) $\gcd(m, N) = 1$
I understand the proof of correctness for this case using Euler's Theorem
Case 2) $\gcd(m, N) \neq 1$
For proving this, the Chinese Remainder Theorem is used
All the proofs say that as per CRT
If
- $x = y \pmod{p}$ - 1 and
- $x = y \pmod{q}$ - 2
then
- $x = y \pmod{pq}$ ====> 3
I know that Line 1 is true & it's easily proven, but how does Chinese Remainder theorem come in here? How do you use CRT to get from (1)&(2) to (3)?
For e.g. check the Wikipedia article (it's not just Wikipedia, I saw it in several other places also)
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Proof_using_Fermat's_little_theorem
In that article check the line "To check whether two numbers, such as med and m, are congruent mod pq, it suffices (and in fact is equivalent) to check that they are congruent mod p and mod q separately" - they have [note2] for it where it says "This is part of the Chinese remainder theorem, although it is not the significant part of that theorem."
Let $p$ and $q$ be distinct prime numbers, and let $a$ be an integer that is divisible by both $p$ and $q$. Then $a$ is divisible by $pq$. (Do you agree?)
In other words, if $a\equiv 0 \bmod p$ and $a\equiv 0\bmod q$, then $a\equiv 0\bmod pq$.
Now just let $a=x-y$.