- #1

evinda

Gold Member

MHB

- 3,836

- 0

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)