5
$\begingroup$

I read this post Does RSA work for any message M?, but I cant prove that $(M^e)^d-M\equiv 0\pmod{p}$ like this:

$\endgroup$
1
  • $\begingroup$ I have updated my answer to the original question, so that it is self-contained, with a proof similar to that in this answer. $\endgroup$
    – fgrieu
    Nov 7, 2016 at 16:25

2 Answers 2

5
$\begingroup$

Let $p$ be a prime. Fermat Little Theorem says that for any integer $a$ co-prime to $p$ (i.e., such that $\gcd(a,p) = 1$), one has $a^{p-1} \equiv 1 \pmod {p}$.

For RSA, we have $ed \equiv 1 \pmod{(p-1)}$ and thus there exists an integer $k$ such that $ed = 1 + k(p-1)$.

There are two cases:

  1. if $\gcd(M,p) = 1$ then $M^{ed} \equiv M^{1 + k(p-1)} \equiv M \cdot M^{k(p-1)} \equiv M \cdot (M^{p-1})^k \equiv M \cdot 1^k \equiv M \pmod p$ by Fermat Little Theorem;
  2. if $\gcd(M,p) \neq 1$ then $M$ is a multiple $p$ (or equivalently $M \equiv 0 \pmod p$) and thus $M^{ed} \equiv 0^{ed} \equiv 0 \equiv M \pmod p$.

In both cases, we thus have $M^{ed} \equiv M \pmod p$.

For RSA, since we also have $ed \equiv 1 \pmod{(q-1)}$, it can be shown in the same way that $M^{ed} \equiv M \pmod{q}$.

By Chinese remaindering, we thus have $M^{ed} \equiv M \pmod N$ where $N = pq$.

$\endgroup$
2
  • $\begingroup$ I don't quite understand the Chinese Remainder step. Wouldn't it be (m + m) mod N if we use the CRT? $\endgroup$
    – jvdh
    Aug 26, 2018 at 9:23
  • $\begingroup$ @jvdh not really, you're solving equation $a = b$ in some ring $R_1$ by translating it to ring $R_2$ where $f: R_1 \to R_2$ is an isomorphism between the two rings. So if you want to prove $a = b$ and you prove $f(a) = f(b)$ then, inverting the $f$ leads you inmediately to $a = b$ (of course there is no need to carry out the inversion of $f$ explicitely) $\endgroup$ Feb 1, 2019 at 10:56
5
$\begingroup$

By construction, we have $ed\equiv 1\pmod{\lambda(n)}$, hence $ed\equiv1\pmod{\lambda(n)}$ since $\lambda(p)=p-1$ divides $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Fermat's little theorem thus implies that $(M^e)^d-M\equiv M^{ed}-M\equiv0\pmod p$ for any $M\in\mathbb Z$.

$\endgroup$
1
  • 1
    $\begingroup$ Actually, it's not true that we necessarily have $ed \equiv 1 \pmod{\phi(n)}$. We do have $ed \equiv 1 \pmod{\text{lcm}(p-1,q-1)}$, which implies $ed \equiv 1 \pmod{p-1}$, which gives your result $\endgroup$
    – poncho
    Nov 7, 2016 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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