Previous | ToC | Next Labs: Cryptography. Part 2. Math Alive

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.

Previous | ToC | Next Last Modified: August 2008