## The RSA Theorem

Let $p$ and $q$ be distinct primes, and let $e, d$ satisfy $ed=1\pmod{(p-1)(q-1)}$. Then for any $m, $m^{ed}=m\pmod{n}$.

For some reason, even in published works, this important cryptographic result is often only half proved. Here is a full proof.

Proof: We consider two cases: (i) $m$ is relatively prime to both $p$ and $q$ (and hence relatively prime to $n=pq$), and (ii) $m$ is a multiple of one of the primes, say $p$. We note that $m$ can’t be a product of both primes, for then it would be greater than their product, thus violating the statement of the theorem.

(i) By definition, $ed=k(p-1)(q-1)+1$ for some integer $k$. Since $(p-1)(q-1)=\phi(n)$, then by Euler’s theorem

$m^{ed}=m^{k\phi(n)+1}=m(m^{\phi(n)})^k=m\pmod{n}$.

(ii) Clearly

(1) $m^{ed}=m\pmod{p}$

since both sides are equal to $0\pmod{p}$. We can also write $m^{ed}=m^{k(p-1)(q-1)+1}=m.(m^{q-1})^{k(p-1)}$, and since $m$ is relatively prime to $q$, then by Euler’s theorem again $m^{q-1}=1\pmod{q}$ and so

(2) $m^{ed}=m\pmod{q}$

By the Chinese remainder theorem, (1) and (2) together prove $m^{ed}=m\pmod{n}$ as required. $\Box$

The AIM Network

The Australian Independent Media Network