Ch. 9 Public Key Cryptography and RSA

9.1 Principles of Public-Key Cryptosystems

Use of a key distribution center defeats the purpose of encryption as a means of secret communication
It must be computationally infeasible to determine the decryption key given the algorithm and the encryption key
Some algorithms (such as RSA) allow either key to encrypt and the other decrypt
6 ingredients
- Plaintext
- Encryption Algorithm
- Public and Private Keys
- Ciphertext
- Decryption Algorithm
Essential Steps
- Each user generates a pair of keys
- Each user places one of them in a public file or register. This is the public key
- Bob encrypts a message using Alice’s public key
- When Alice receives the message, she decrypts using her private key. No keys are distributed
Requirements for Public Key Encryption
- It is computationally easy to generate a key pair
- It is easy for a sender, knowing the public key, to generate a ciphertext
- It is easy for the recipient to decrypt the ciphertext using their private key
- It is infeasible for an adversary, knowing the public key, to determine the private key
- It is infeasible for an adversary, knowing the public key and the ciphertext to recover the message
- OPTIONAL: The keys can be applied in either order

Limitations
- One-way trapdoor functions are hard to find and scale poorly with key size
  - Keys need to be large to prevent brute force
  - These make public key encryption slow

9.2 The RSA Algorithm