At the very end of (most) proofs of RSA's correctness we have something like $$m^{ed}\equiv m\pmod p$$ $$m^{ed}\equiv m\pmod q$$ Therefore by the Chinese Remainder Theorem (CRT) $$m^{ed}\equiv m\pmod n$$ where $n=pq$, $ed\equiv 1\pmod{\phi(n)}$ and $m<n$

It's not obvious to me what work the CRT is doing here. If anyone can help that would be great, thank you!

My working so far

CRT (as I have it) says that if we have $n=n_1...n_k$ where $n_1...n_k$ are pairwise coprime and a series of equations $x\equiv a_i\pmod{n_i}$ for $1\leq i\leq n$ then there is a unique solution for $x$ modulo $n$

To find $x$ we can use $$x=\left(\sum_{i=1}^ka_im_iy_i\right)\bmod n$$ where $m_i=n/n_i$ and $y_i=m_i^{-1}$ (mod $n_i$)

So for the RSA proof we let $x=m^{ed}$ and say we have $x\equiv m\pmod p$ and $x\equiv m\pmod q$

Let $q' = q^{-1}\pmod p$ and $p'=p^{-1}\pmod q$

Therefore using the above equation we have \begin{align} x&=(mqq'+mpp')\bmod n\\ &=m(qq'+pp')\bmod n \end{align} So I need to show that $qq'+pp'\equiv 1\pmod n$

  • $\begingroup$ Similar question was answered on sister SEs: here and here $\endgroup$ – Ran G. Jun 1 '15 at 20:22
  • $\begingroup$ Maybe what you missed is that this holds for the special case where $GCD(m,n)\ne 1$, that is, either $m= t\cdot p$ or $m=t\cdot q$ for some integer $t$. $\endgroup$ – Ran G. Jun 1 '15 at 20:35

Your Answer

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

Browse other questions tagged or ask your own question.