I can understand how RSA works and how the public/private keys are generated. However, I am confused on the encryption and decryption equations of RSA.
To encrypt the message $m$: $c = m^e \mod n$
While to decrypt: $m = c^d \mod n$
Why the reminder can be used as the encrypt message and why it can get decrypted? How could the 3 inventors derive the equations?
Could anyone help explain it? Any help is appreciated.
Remember that $n=p\cdot q$ for two primes $p,q$ and $e$ must fulfill $1<e<\phi(n)$ and $\gcd(e,\phi(n))=1$, where $\phi$ is the Euler totient function.
We also pick $m$ to be coprime to $p,q$
Our $d$ is the multiplicative inverse of $e$ in $\mod \phi(n)$, so $$e \cdot d + k \cdot \phi(n)=1$$ This means that $e \cdot d = -k \cdot \phi(n)+1$, so we can rewrite
$$m^{ed} = m^{-k\cdot \phi(n)+1}=m\cdot m^{-k\cdot \phi(n)}=m\cdot (m^{\phi(n)})^{-k} \mod n$$
Now if $m$ and $n$ were coprime, we could use the Fermat-Euler theorem
$$m^{\phi(n)}=1 \mod n$$ and be done. But we picked $m$ to be coprime to $p,q$, which are the only nontrivial divisors of $n$, so this is given.
At last we have
$$m\cdot (m^{\phi(n)})^{-k}=m \cdot 1^{-k}=m \mod n$$
Overall we have shown
$$m^{ed}=m \mod n$$