RSASystem

We need some theorems from Number Theory.

Extended Euclidean algorithm Let $a$ and $b$ be integers and $d=\text{gcd}(a,b)$. Then there are integers $x$ and $y$ such that $ax+by=d$.
Fermat's Little Theorem. Let $p$ be a prime number not dividing the integer $n$. Then $n^{p-1}\equiv 1\pmod p$. (Proof)
Suppose that $a\equiv b\pmod m$ and $a\equiv b\pmod n$. If $m$ and $n$ are coprime, then $a\equiv b\pmod {mn}$. (Proof)
Suppose that $1\leq a<m$ and $\gcd(a,m)=1$. Then there are $x$ and $y$ such that $ax+my=1$. This makes $ax\equiv 1\pmod m$. Take $x'\equiv x\pmod m$ such that $1\leq x'<m$. Then $ax'\equiv ax\equiv 1\pmod m$.

Now, we can describe the RSA System.

Let $p$ and $q$ be distinct primes. Put $\phi=(p-1)(q-1)$ and $n=pq$. Choose $e$ with $1<e<\phi$ and $\text{gcd}(e,\phi)=1$. Also take $d$ with $1<d<\phi$ and $de\equiv 1\pmod\phi$. Now, announce $(e,n)$ as the public key, while keep $d$ secret. A message is an $m$ with $1\leq m<n$ and $\text{gcd}(m,n)=1$. The cipher for $m$ is $c\equiv m^e\pmod n$ and $1\leq c<n$.

Claim. If $m$ and $n$ are coprime, and $c\equiv m^e\pmod n$. Then $c^d\equiv m\pmod n$.

Proof. Assume the $m$ and $n$ are coprime and let $c\equiv m^e\pmod n$. From $\text{gcd}(m,n)=1$, we have $p$ and $q$ do not divide $m$, and so $p$ does not divide $m^{q-1}$ and $q$ does not divide $m^{p-1}$. By Fermat's Little Theorem, one gets $m^\phi=(m^{p-1})^{q-1}\equiv 1\pmod q$ and $m^\phi=(m^{q-1})^{p-1}\equiv1\pmod p$. As $p$ and $q$ are distinct primes, we have $m^\phi\equiv 1\pmod n$. From $de\equiv 1\pmod\phi$, we write $de=k\phi+1$ for some $k$. Therefore, $c^d=m^{de}=m^{k\phi+1}=m\cdot m^{k\phi}\equiv m \pmod n$ as claimed. $\Box$

Note. Among the numbers from $1$ to $n=pq$, there are $\phi$ of them comprime to $n$. Thus, the chance to pick up one that is not comprime to $n$ is $1-\frac{\phi}{n}=1-\big(1-\frac1p\big)\big(1-\frac1q\big)=\frac1p+\frac1q-\frac1{pq}$. When $p$ and $q$ are large, this is very small.