Given a 'message' $M$, a proof of the 'correctness' of RSA encryption means to show that $(M^e)^d \equiv M \pmod{n}$, where $n=pq$ is a product of primes, and $ed \equiv 1 \pmod{\phi(n)}$, where $\phi$ is Euler's totient function, so that $\phi(n)=(p-1)(q-1)$.

Most sources attribute the correctness of RSA encryption to Euler's theorem (a generalisation of Fermat's little theorem), however the end of the intro of the Wikipedia page claims this is erroneous, since it doesn't apply in the case when $\gcd(M,n) \neq 1$, and that actually it is sufficient and necessary to use the "uniqueness provision of the Chinese Remainder Theorem". However, in every proof I can find on the web and on this site, Fermat's little theorem is used as well as CRT.

So, my question is, is it necessary to use FLT? And is it necessary to use CRT?

If so, is there a proof of this, i.e. that FLT / CRT $\Leftarrow (M^e)^d \equiv M \pmod{n}$ ?

  • $\begingroup$ Related Does RSA work for any message M?. No need to CRT, right? $\endgroup$ – kelalaka Jun 23 at 18:28
  • 1
    $\begingroup$ As any theorem, Fermat's Little Theorem can be proved. Thus from any proof making use of Fermat's Little Theorem, we can make a proof that does not; it's only a matter of reformulation. Similarly, the second of the two wikipedia proofs acknowledges that it is really using a proof of Euler's theorem in order to not use Euler's theorem. $\endgroup$ – fgrieu Jun 23 at 19:09
  • $\begingroup$ @fgrieu Good point, I guess its naïve to talk about logical sufficiency and necessity for true statements. And I suppose this means the paragraph on Wikipedia is wrong to say "it is necessary to use CRT"? In a more informal way, are there proofs out there of the RSA thing that isn't clearly by Fermat's little theorem, or an obvious derivative of it? $\endgroup$ – Elliott Cawtheray Jun 23 at 20:07

The proposition following «show that» in the question's first paragraph requires $p\ne q$ to become true. Problems are that when $p=q$, the expression $\phi(n)=(p-1)(q-1)$ no longer holds, and even fixing it to $\phi(n)=(p-1)\,p$ does not make the proposition true for quite all $M$ and $e$, when $p\ne2$. For example the proposition fails for $p=q=M=3$, $n=9$, $e=d=5$, for both the correct $\phi(n)=6$ and the incorrect $\phi(n)=4$.

This proof of that propostion does without the full Chinese Remainder Theorem. Rather, following a suggestion in comment, it uses the more basic fact that if $p$ and $q$ both divide $Z$ and are coprime (including: are distinct primes), then $p\,q$ divides $Z$.

In a nutshell, this is applied to the quantity $Z\underset{\text{def}}=(M^e)^d-M$, leading to the desired conclusion. To show that $p$ divide that $Z$, we distinguish the easy case $M\equiv0\pmod p$, from the other where that follows from $e\,d \equiv 1 \pmod{\phi(n)}$ rewritten as $\exists k,\ e\,d=k\,(p-1)(q-1)+1$, and Fermat's Little Theorem. We could further integrate one of the proofs of the FLT in the demonstration.

In conclusion, we can rigorously prove that RSA works without explicitly using either the FLT or CRT, by using or proving slightly less general statements along the way. I see no reason to thus circumvent the use of FLT, because it is so useful. For CRT, that makes sense.

From a pedagogical perspective, if the audience can't stand the FLT, it's not ready for a proof anyway, and we can as well proceed by affirmation and example. At least, let's try to affirm only true propositions.

A former version of the question used slightly incorrect notation. It is best as it stands now, with $(M^e)^d \equiv M \pmod{n}$ and $e\,d \equiv 1 \pmod{\phi(n)}$. The opening parenthesis immediately on the left of $\bmod$ is to denote modular equivalence, rather than an operator with restriction of the output range to non-negative integers less than the modulus. That notation is obtained with \pmod in $\LaTeX$. Alternatively, we could write $(M^e)^d\bmod{n}=M$ if we add $0\le M<n$. And we could write $d = e^{-1}\bmod{\phi(n)}$.

| improve this answer | |
  • 1
    $\begingroup$ Thanks for the answer, and help with the notation! $\endgroup$ – Elliott Cawtheray Jun 25 at 9:19

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.