RSA Public Key System
Summary of steps to generate the RSA encryption and decryption keys
- Choose two (large) prime integers p and q and form the product m = p*q.
- Calculate the value t = (p-1)*(q-1).
(called the Euler's totient of p*q.)
- A value u is chosen which is relatively prime to the totient t.
- Compute the multiplicative inverse v of u mod t, that is,
(u * v) % t = 1.
(It must exist since u and t are relatively prime).
- Use (u,m) as the public key and (v,m) as the private key; that is,
encrypt a message x (an integer less than m) by:
x^u % m
and decrypt a message y (an integer less than m) by:
y^v % m