Why RSA Works

RSA encryption consists of taking a plaintext $P$ and computing $C = P^e \space \space mod \space \space n$, while decryption is given by $P = C^d \space \space mod \space \space n$. We now explain why these two operations ‘reverse’ one another.

We’ll assume $(n, e)$ is an RSA public key and $d$ is the corresponding private key. Sometimes we’ll use the notation $ab$ to mean $a × b$. We’ll also use a mathematical result attributed to Fermat, which states that for any number $B$ satisfying $gcd(B, n) = 1$, it follows that:

$$B^{(p-1)(q-1)} = 1 \space \space mod \space \space n$$

Now, expressing the RSA decryption formula mathematically, we have:

$$C^{d} = (P^{e})^{d} = P^{ed} \space \space mod \space \space n$$

Remember that because $d$ is the modular inverse of $e$, we have $ed = 1 mod (p – 1)(q – 1)$. This means that there is some positive integer, $k$, for which it’s true that:

$$ed = k(p-1)(q-1)+1$$

By replacing this in our above expression for the decryption function, we get:

$$C^{d} = P^{ed} = P^{k(p-1)(q-1)+1} \space \space mod \space \space n$$

Now, all we do is rewrite this expression by rearranging the powers of $P$. There are no mathematical tricks here. We follow the rules describing how the powers of a number behave, like so:

$$C^{d} =P^{k(p-1)(q-1)+1} \space \space mod \space \space n$$

$$C^{d} =P^{k(p-1)(q-1)} * P\space \space mod \space \space n$$

$$C^{d} =(P^{(p-1)(q-1)})^k * P\space \space mod \space \space n$$

The above-mentioned mathematical result attributed to Fermat can now be used. Writing $P$ instead of $B$, we see that as long as the greatest common divisor of $P$ and $n$ is 1, this result says:

$$P^{(p-1)(q-1)} = 1 \space \space mod \space \space n$$

Therefore, we see that:

$$C^{d} =1^k * P = P\space \space mod \space \space n$$

This is what we hoped decryption would achieve.

The only case we haven’t covered is when $gcd(P, n)$ is not equal to 1. Note that this is an extremely rare case and only happens in the highly unlikely event of either $P = up$, for some $u < q$, or $P = vq$, for some $v < p$. If $P = up$, then $P = 0 \space \space mod \space \space p$ and so $P^{ed} = 0 \space \space mod \space \space p$. In other words, $P^{ed} = P = 0 \space \space mod \space \space p$.

Since $P$ is a multiple of $p$, in this case, it can’t be a multiple of $q$ as well, and so the greatest common divisor of $P$ and $q$ is 1. So we can apply Fermat’s result and the above RSA argument to see that $P^{ed} = P \space \space mod \space \space q$. We have now shown $P^{ed} = P \space \space mod \space \space p$ and $P^{ed} = P \space \space mod \space \space q$. It follows by a simple number theory result that $P^{ed} = P \space \space mod \space \space n$. If $P = vq$, we apply a similar argument to show the same result.