RSA Cryptography Explained

Let p and q be two different large primes. A large number p can be tested for primeness by applying Fermat's theorem, which states that if p is prime, then

ap-1 == 1 (mod p)

for every positive integer a not divisible by p. (A double equal sign (==) is used instead of the usual symbol for congruence, which is not supported by all Web browsers.) A number p which passes this test for several hundred randomly selected values of a in the range (1, p-1) is almost surely prime.

Then find two large integers d and e, both less than (p-1)(q-1), such that

de == 1 (mod (p-1)(q-1)).

The easiest way to do this is to choose e at random and use the Euclidean algorithm to find

gcd(e, (p-1)(q-1))

and integers d and s such that

de - s(p-1)(q-1) = gcd(e, (p-1)(q-1)).

If the right member is not 1, try again.

The public key is (e, pq) and private key is (d, pq), or vice-versa. The number e or d is called the exponent, and the number pq is called the modulus, for reasons to be made clear later. The modulus pq is published with the public key, but the separate values of p and q must be kept secret. In fact, they are not used for either encryption or decryption and may be discarded.

Let m be a message in the range [0, pq). It is encrypted to c in the range [0, pq) such that:

c == me (mod pq).

Decryption is similar:

m == cd (mod pq).

We must prove that encryption and decryption are inverse operations, i.e., that

(me)d = (md)e = mde == m (mod pq).

Because of the way d and e were constructed,

de = 1 + s(p-1)(q-1)

for some positive integer s.

If p does not divide m, then by Fermat's theorem

mp-1 == 1 (mod p).

Raising both sides to the s(q-1) power and multiplying by m shows that

mde = m1 + s(p-1)(q-1) == m (mod p),

which is obviously also true if p does divide m.

Similarly,

mde == m (mod q).

Hence both p and q divide mde - m. Since p and q are relatively prime, so does pq. Hence

mde == m (mod pq).