
Decryption for RSA
The decryption illustrated on the previous page is possible because r and s have a very special relationship. With p = 29, and q = 37, we compute:
m = (p1) * (q1) = 1008
and then we have chosen r and s so that:
r*s = 25 * 121 = 3025 = 1 (mod m)
Let's see how this explains why y^{s} = x (mod n).
We have y^{s} = (x^{r})^{s} = x^{r*s} (mod n).
Now r*s is 1 + some multiple of m:
r*s = L(p1)(q1) + 1,
so that: y^{s} = x^{L(p1)(q1)+1} (mod n).
Now Fermat's little theorem tells us that: x^{p} = x (mod p). Multiplying both sides by x^{p1}, we get x^{p1} * x^{p} = x^{p1} * x (mod p).
That is, x^{2(p1)+1}=x^{p} (mod p), and so x^{2(p1)+1}=x (mod p).
If we again multiply both sides by by x^{p1}, we shall obtain x^{3(p1)+1} = x^{p}=x (mod p).
In fact, x^{N(p1)+1}=x (mod p) for all N.
Thus
x^{L(p1)(q1)+1} = x (mod p),
since we can set N=L(q1).
By the same principle (but with q in place of p), we have x^{M(q1)+1} = x (mod q) for all x and all M.
Thus
x^{L(p1)(q1)+1} = x (mod q),
since we can set M=L(p1).
From the last two boldfaced congruences, we know that x^{L(p1)(q1)+1}x is divisible both by p and by q. These are two distinct primes, so x^{L(p1)(q1)+1}x is divisible by pq=n, i.e.,
x^{L(p1)(q1)+1} = x (mod n),
Recall that rs=L(p1)(q1)+1, so
x^{rs} = x (mod n),
and since y=x^{r},
y^{s} = x (mod n).
This explains why the RSA algorithm works.
