RSA Encryption Explanation

Question

In Khan Academy's RSA Encryption 2 video, I can't understand how they have got from

$$m^e\bmod N\equiv c$$ to $$c^d\bmod N\equiv m\,.$$

The transcript says,

01:39 some piece of information that makes it
01:41 easy to reverse the encryption
01:44 we need to raise $c$ to some other exponent, say $d$,
01:48 which will undo the original operation applied to $m$
01:51 and return the original message $m$.
01:54 So both operations together, is the same as
01:57 $m^e$ all raised to the power of $d$,
02:01 which is the same as $m^{e\times d}$.

The person says if we want to reverse the function to give us $m$ (the encrypted message), we simply have to raise $d$ to another exponent, $d$, and this reverses it.

Although I know this video isn't supposed to fully explain everything I don't understand how this is done. How can you just raise $c$ to some power and get the original message $m$. Is there some sort of proof or can someone explain it in more detail perhaps? By the way, I pretty much know nothing about encryption/ cryptography. I study CS at college (UK) AND was just watching due to curiousity.

Answer 1

What you have (after generating the keys):

$$ \gcd(p, q) = 1 $$ $$ N = pq $$ and a number $e$ and it's inverse $d$, modulo $\phi(N)$. That is: $$ ed \equiv 1 \pmod{\phi(N)}$$

---

Encryption: $$ c \equiv m^e \pmod{N}$$ Decryption: $$ m^\prime \equiv c^d \pmod{N} $$ $$ m^\prime \equiv (m^e)^d \equiv m^{ed} \pmod{N} $$

We don't yet if $m^\prime \equiv m$.

Well... you can use Euler's Theorem: $$ a^{\phi(N)} \equiv 1 \pmod{N}, \text{ if } \gcd(a,N) = 1. $$

Write $ed = 1 + k~\phi(N)$: $$ m^\prime \equiv m^{1+k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot m^{k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot \underbrace{m^{k\phi(N)}}_{1} \pmod{N}$$

So $m^\prime \equiv m \pmod{N}$.