How It Works

RSA cryptography is based on the following theorems:

Theorem 1 (Fermat's Little Theorem)   If $p$ is a prime number, and $a$ is an integer such that $(a, p) = 1$, then

$$a^{p-1} = 1 ({\rm mod\ } p).$$

Proof: Consider the numbers $(a\cdot 1)$, $(a\cdot 2)$, ... $(a\cdot (p-1))$, all modulo $p$. They are all different. If any of them were the same, say $a\cdot m = a\cdot n ({\rm mod\ } p)$, then $a\cdot(m-n) = 0 ({\rm mod\ } p)$ so $m-n$ must be a multiple of $p$. But since all $m$ and $n$ are less than $p$, $m=n$.

Thus $a\cdot 1$, $a\cdot 2$, ..., $a\cdot (p-1)$ must be a rearrangement of $1, 2, \ldots, (p-1)$. So modulo $p$, we have:

$$\prod^{p-1}_{i=1} i = \prod^{p-1}_{i=1} a\cdot i = a^{p-1}\prod^{p-1}_{i=1} i,$$

so $a^{p-1} = 1 ({\rm mod\ } p)$.

Theorem 2 (Fermat's Theorem Extension)   If $(a, m) = 1$ then $a^{\phi(m)} = 1 ({\rm mod\ } m)$, where $\phi(m)$ is the number of integers less than $m$ that are relatively prime to $m$.

Proof: Same idea as above. Suppose $\phi(m) = n$. Then suppose that the $n$ numbers less than $m$ that are relatively prime to $m$ are:

$$a_1, a_2, a_3, \ldots, a_n.$$

Then $a\cdot a_1$, $a\cdot a_2$, ..., $a\cdot a_n$ are also relatively prime to $m$, and must all be different, so they must just be a rearrangement of the $a_1$, ..., $a_n$ in some order. Thus:

$$\prod^n_{i=1} a_i = \prod^n_{i=1} a\cdot a_i = a^n \prod^n_{i=1} a_i,$$

modulo $m$, so $a^n=1 ({\rm mod\ } m)$.

Theorem 3 (Chinese Remainder Theorem)   Let $p$ and $q$ be two numbers (not necessarily primes), but such that $(p,q)=1$. Then if $a=b({\rm mod\ }p)$ and $a=b({\rm mod\ }q)$ we have $a=b({\rm mod\ }pq)$.

Proof: If $a=b({\rm mod\ }p)$ then $p$ divides $(a-b)$. Similarly, $q$ divides $(a-b)$. But $p$ and $q$ are relatively prime, so $pq$ divides $(a-b)$. Consequently, $a=b({\rm mod\ }pq)$.

Based on these three theorems, here is why the RSA encryption scheme works.

Let $M$ be the secret message, let $p$ and $q$ be two different (large) prime numbers, let $d$ be a (relatively small) number that is relatively prime to $(p-1)(q-1)$, and let $e$ be a number such that $de = 1 ({\rm mod\ }(p-1)(q-1))$. Let $N=pq$. The encoded message is $C = M^d ({\rm mod\ }N)$, and we need to show that the decoded message is given by $M = C^e ({\rm mod\ }N)$.

Proof: Since $de = 1 ({\rm mod\ }(p-1)(q-1))$, $de = 1 + k(p-1)(q-1)$. Thus:

$$C^e = M^{de} = M^{1+k(p-1)(q-1)} = M\cdot (M^{p-1})^{k(q-1)}.$$

But $M^{p-1} = 1 ({\rm mod\ }p)$, so $M^{de} = M ({\rm mod\ } p)$.

By exactly similar reasoning, $M^{de} = M ({\rm mod\ } q)$, so by the Chinese remainder theorem, $M^{de} = M ({\rm mod\ } pq)$.

Finally, given $d$, to find $e$ such that $de = 1 ({\rm mod\ }(p-1)(q-1))$, we can use the extension of Fermat's theorem to get $d^{\phi((p-1)(q-1))} = 1 ({\rm mod\ }(p-1)(q-1))$, so $d^{\phi((p-1)(q-1))-1} ({\rm mod\ }(p-1)(q-1))$ is a suitable value for $e$.