RSA

RSA is an asymmetric algorithm and is attributed to three people but reading this article will explain who developed the algorithm years earlier. When reading this article, try to understand the section on key generation, encrypting messages, decrypting messages, and signing messages. Most importantly, note the speed of RSA in comparison to DES that was discussed in the section on symmetric key encryption. Also note how attacks such as man-in-the-middle and RSA blinding attacks can be avoided.

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 ).