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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.