Why do we get like that the message?

[evinda]

Hello! (Wave)

When we encrypt with RSA, we choose two large arbitrary prime numbers $p$ and $q$.
We choose $n=pq$. We compute $\phi(n)=(p-1)(q-1)$.
We choose a number $e>1$ such that $e^{\phi(n)}\equiv 1 \pmod{n}$.

We compute the inverse of $e$, $d \equiv e^{-1}\pmod{\phi(n)}$.
The public key is $(n,e)$ and the private key $(n,d)$.

We encrypt a message $M$ as follows:

$$C(M)=M^e \mod{n}$$

We decrypt the message as follows:

$$M(C)=C^{d} \mod{n}$$

My question is the following:

Why do we have that $M^{ed}=M \mod{n}$, given that $ed=1 \mod{\phi{n}}$ and not modulo $n$ ? (Thinking)

 

[I like Serena]

Hey evinda!

It's a consequence of Euler's theorem that says that if $a$ is coprime with $n$ that then $a^{\phi(n)}=1\bmod n$.

Let $k$ be such that $ed = k\phi(n) + 1$.
If $M$ is coprime with $n$ then it follows that:
$$M^{ed} = M^{k\phi(n) + 1} = (M^{\phi(n)})^k\cdot M = M\bmod n$$

 

[evinda]

Hey evinda!

It's a consequence of Euler's theorem that says that if $a$ is coprime with $n$ that then $a^{\phi(n)}=1\bmod n$.

Let $k$ be such that $ed = k\phi(n) + 1$.
If $M$ is coprime with $n$ then it follows that:
$$M^{ed} = M^{k\phi(n) + 1} = (M^{\phi(n)})^k\cdot M = M\bmod n$$

Ah, I see... Thanks a lot! (Sun)