Why RSA Works

Learn the mathematical proof of why RSA works.

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

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

B(p1)(q1)=1  mod  nB^{(p-1)(q-1)} = 1 \space \space mod \space \space n

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

Cd=(Pe)d=Ped  mod  nC^{d} = (P^{e})^{d} = P^{ed} \space \space mod \space \space n

Remember that because dd is the modular inverse of ee, we have ed=1mod(p1)(q1)ed = 1 mod (p – 1)(q – 1). This means that there is some positive integer, kk, for which it’s true that:

ed=k(p1)(q1)+1ed = k(p-1)(q-1)+1

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

Cd=Ped=Pk(p1)(q1)+1  mod  nC^{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 PP. There are no mathematical tricks here. We follow the rules describing how the powers of a number behave, like so:

Cd=Pk(p1)(q1)+1  mod  nC^{d} =P^{k(p-1)(q-1)+1} \space \space mod \space \space n

Cd=Pk(p1)(q1)P  mod  nC^{d} =P^{k(p-1)(q-1)} * P\space \space mod \space \space n

Cd=(P(p1)(q1))kP  mod  nC^{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 PP instead of BB, we see that as long as the greatest common divisor of PP and nn is 1, this result says:

P(p1)(q1)=1  mod  nP^{(p-1)(q-1)} = 1 \space \space mod \space \space n

Therefore, we see that:

Cd=1kP=P  mod  nC^{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)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=upP = up, for some u<qu < q, or P=vqP = vq, for some v<pv < p. If P=upP = up, then P=0  mod  pP = 0 \space \space mod \space \space p and so Ped=0  mod  pP^{ed} = 0 \space \space mod \space \space p. In other words, Ped=P=0  mod  pP^{ed} = P = 0 \space \space mod \space \space p.

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

Get hands-on with 1200+ tech skills courses.