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
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
The easiest way to do this is to choose e at random and use the Euclidean algorithm to find
and integers d and s such that
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:
Decryption is similar:
We must prove that encryption and decryption are inverse operations, i.e., that
Because of the way d and e were constructed,
for some positive integer s.
If p does not divide m, then by Fermat's theorem
Raising both sides to the s(q-1) power and multiplying by m shows that
which is obviously also true if p does divide m.
Similarly,
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. Hencemde == m (mod pq).