RSA Cryptography Explained

RSA is an algorithm for public-key encryption.

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).