|
|
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 = (p-1) * (q-1) = 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 ys = x (mod n).
We have ys = (xr)s = xr*s (mod n).
Now r*s is 1 + some multiple of m:
r*s = L(p-1)(q-1) + 1,
so that: ys = xL(p-1)(q-1)+1 (mod n).
Now Fermat's little theorem tells us that: xp = x (mod p). Multiplying both sides by xp-1, we get xp-1 * xp = xp-1 * x (mod p).
That is, x2(p-1)+1=xp (mod p), and so x2(p-1)+1=x (mod p).
If we again multiply both sides by by xp-1, we shall obtain x3(p-1)+1 = xp=x (mod p).
In fact, xN(p-1)+1=x (mod p) for all N.
Thus
xL(p-1)(q-1)+1 = x (mod p),
since we can set N=L(q-1).
By the same principle (but with q in place of p), we have xM(q-1)+1 = x (mod q) for all x and all M.
Thus
xL(p-1)(q-1)+1 = x (mod q),
since we can set M=L(p-1).
From the last two boldfaced congruences, we know that xL(p-1)(q-1)+1-x is divisible both by p and by q. These are two distinct primes, so xL(p-1)(q-1)+1-x is divisible by pq=n, i.e.,
xL(p-1)(q-1)+1 = x (mod n),
Recall that rs=L(p-1)(q-1)+1, so
xrs = x (mod n),
and since y=xr,
ys = x (mod n).
This explains why the RSA algorithm works.
|