The Mathematical Basis of RSA Key-Pair Generation
- Find P and Q, two large (e.g., 1024-bit)
prime numbers.
- Choose E such that E and
(P-1)(Q-1) are relatively prime, which means
they have no prime factors in common. E does not have
to be prime, but it must be odd. (P-1)(Q-1) can't be
prime because it's an even number.
- Compute D such that (DE - 1) is evenly
divisible by (P-1)(Q-1). Mathematicians write this as
DE = 1 mod (P-1)(Q-1), and they call D the
multiplicative inverse of E.
- The encryption function is encrypt(T) = TE mod PQ,
where T is the plaintext (a positive integer).
- The decryption function is decrypt(C) = CD mod PQ,
where C is the ciphertext (a positive integer).
Your public key is the pair (PQ, E). Your
private key is the number D (reveal it to no one). The
product PQ is the modulus. E is the
public exponent. D is the secret exponent.
You can publish your public key freely, because there are no known easy methods
of calculating D, P, or Q given only
(PQ, E) (your public key). If P and
Q are each 1024 bits long, the sun will burn out before the most
powerful computers presently in existence can factor your modulus into
P and Q.
Caveats
- It is not yet rigorously proven that no easy methods of factoring exist.
- It is not yet rigorously proven that the only way to crack RSA is to
factor the modulus.