04 | April | 2008 | Alasdair's musings

Let $p$ and $q$ be distinct primes, and let $e, d$ satisfy $ed=1\pmod{(p-1)(q-1)}$ . Then for any $m<n=pq$ , $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$

Daily Archives: April 4, 2008

The RSA Theorem

Blogroll

Blog Stats

Categories

Follow “Alasdair's musings”