RSA Algorithm (Ron Rivest, Adi Shamir, Leonard Adleman)

1. Bob generates two large numbers p and q and chooses a number e prime with (p-1)(q-1) (in practice the value of e is 65337).
2. Bob computes the private key d = e^(-1) mod ((p-1)(q-1)) and the public key (n = p * q , e);
3. Bob sends the public key to Alice;
4. Alice encrypts the message m with Bob's private key: c = m^e mod n and sends the message to Bob;
5. Bob decrypts the message with the private key: m = c^d mod n.

Analysis:

• gets its security from the difficulty of factoring large numbers;
• considered the "de facto" standard in public key encryption;
• patent until Sept. 20, 2000;
• licensed to many companies;