RSA

Suppose a user Alice wishes to allow Bob to send her a private message over an insecure transmission medium. She takes the following steps to generate a public key and a private key:

1. Choose two large prime numbers p ≠ q randomly and independently of each other. Compute N = p q.
2. Choose an integer 1 < e < N which is coprime to (p-1)(q-1).
3. Compute d such that d e ≡ 1 (mod (p-1)(q-1)).
4. Destroy all records of p and q.

• (Steps 2 and 3 can be performed with the extended Euclidean algorithm; see modular arithmetic. Additionally, solving for either e or d may be performed using the diophantine equation ${\displaystyle ed-k\phi (n)=1}$.)

N and e are the public key, and N and d are the private key. Note that only d is a secret as N is known to the public. Alice transmits the public key to Bob, and keeps the private key secret.

You can generate and examine a real RSA keypair using OpenSSL and some Unix utilities. ( Cryptography/Generate a keypair using OpenSSL ).