Alice wants her friends to send her stuff only she can read. RSA public-key encryption allows her to do that: she chooses huge primes $p$ and $q$ and releases $N = pq$ along with an encryption exponent $e$ such that ${\rm gcd}(e,(p-1)(q-1)) = 1$. If Bob wants to send Alice a message $m$, he sends $c = m^e$ modulo $N$ to Alice.

Computing $m$ from $m^e$ is hard if you only know $N$, but becomes easy with the prime factors $p$ and $q$. And, only Alice knows $p$ and $q$. The word “hard” is relative, and maybe someone will find an easy way to do it in the future, perhaps with quantum computers.

However, if you know $p$ and $q$, then you can compute $d$ such that $de = 1$ modulo $(p-1)(q-1)$. That is, you’re computing the inverse of $e$ in the multiplicative group $(\mathbb{Z}/N)^\times$. You can use Fermat’s little theorem: $x^{p-1} = 1$ in $\mathbb{Z}/p^\times$ for an $x\in (\mathbb{Z}/p)^\times$ to compute that $c^d = m^{ed} = m$ modulo $N$. Therefore, $c^d$ in $\mathbb{Z}/N$ is the decrypted message.

More »