Public-Key Cryptography


We need to understand the difference between symmetric encryption and asymmetric encryption.


Public-key cryptography separates encryption keys from decryption keys. Each participant B has a decryption key which they hold secretly, and a related encryption key which they share in a public repository of some sort. Even though B’s decryption key and encryption key are mathematically related, it should be computationally infeasible for an eavesdropping adversary to determine B’s decryption key from B’s encryption key. Now, if any user A wishes to send a confidential message M to user B, A would somehow obtain an authentic copy of B’s public encryption key, encrypt M with this public key, and send the resulting ciphertext C to B. Since B is the only person who possesses the private decryption key, only B can decrypt C to recover M.

Diffie-Hellman Key Exchange Protocol See wikipedia article, where it talks about mixing colored paintings.

Modular Exponentiation

RSA Encryption Algorithm

(a) Setting up RSA: To set up the RSA encryption scheme, Bob does the following.

  1. Randomly choose two large, distinct primes and and let .
  2. Select an arbitrary integer e so that and .
  3. Solve the congruence for an integer where
  4. Publish the public key .
  5. Keep secret the private key , and the primes and .

(b) RSA Encryption: To encrypt a message as ciphertext and send securely to Bob, Alice does the following.

  1. Obtain an authentic copy of Bob’s public key .
  2. Construct the plaintext message , an integer such that .
  3. Encrypt as the ciphertext , given by where .
  4. Send to Bob

(c) RSA Decryption: To decrypt the ciphertext received from Alice, Bob does the following.

  1. Use the private key to decrypt the ciphertext as the received message , given by where .
  2. Claim: The received message equals the original plaintext message , i.e., .