Computer Security :: Lessons :: Public-Key Cryptography
Public-Key Cryptography
Public-key cryptography is a radical departure from the previous cryptographic methods of substitution and permutation. Public-key cryptography relies on mathematical functions, and is asymmetric involving two different keys known as asymmetric keys. One key is used for encryption and a different but related key for decryption. An asymmetric algorithm must make it computationally infeasible to determine the decryption key given knowledge of the algorithm and the encryption key. The following video gives a short example of how a public-key encryption system works.
There are six elements required for public-key encryption:
- Plaintext: The readable message/data that is sent into the encryption algorithm.
- Encryption Algorithm: Performs various transformations on the plaintext.
- Public Key: Used for encryption or decryption by either the sender or receiver.
- Private Key: Known by only one party and used for encryption or decryption.
- Ciphertext: The scrambled message output by the encryption algorithm.
- Decryption Algorithm: Accepts the ciphertext as input and produces the original plaintext.
In conventional cryptography, the key is referred to as the secret key. That is why we use the term private key in asymmetric cryptography. Although the private key is also secret, we want to differentiate it from the key used in conventional cryptography. The table below summarizes the differences between conventional cryptography and public-key encryption.
| Conventional Encryption | Public-Key Encryption |
|---|---|
| Needed to Work: 1. The same algorithm and the same key used for encryption and decryption. 2. The sender and receiver must share the algorithm and key. |
Needed to Work: 1. One algorithm is used for encryption and a related algorithm for decryption with a pair of keys. 2. The sender and receiver must each have one of the matched pair of keys (not the same key). |
| Needed for Security: 1. The key must be kept secret. 2. It must be impossible or impractical to decipher a message if the key is kept secret. 3. Knowledge of the algorithm plus samples of ciphertext must be insufficient to determine the key. |
>Needed for Security: 1. One of the keys must be kept secret. 2. It must be impossible or impractical to decipher a message if one of the keys is kept secret. 3. Knowledge of the algorithm plus one of the keys plus samples of ciphertext must be insufficient to determine the other key. |
The scheme in the following diagram ensures the message can only be decrypted by the intended source. Encryption occurs twice. One encryption uses the sender's private key while the second encryption uses the receiver's public key. This ensures that an interceptor cannot use the receiver's public key to decrypt the message. The receiver uses their own private key to decrypt the message, followed by the sender's public key to generate the original plaintext.
Requirements for Public-Key Cryptography
The following requirements are needed for any asymmetric encryption system based on two related keys. The requirements are difficult to meet given there are only four widely-accepted encryption systems that meet all five requirements.
- It is computationally easy for someone to generate a pair of keys (public PUb and private PRb).
- It is computationally easy for a sender, knowing the public key, to generate corresponding ciphertext.
- It is computationally easy for the receiver to decrypt the resulting ciphertext using the private key to recover the original message.
- It is computationally infeasible for an adversary knowing the public key to determine the private key.
- It is computationally infeasible for an adversary knowing the public key and ciphertext to recover the original message.
The above requirements lay out the need for a trap-door one-way function. A one-way function is a function that creates function values with a unique inverse so the calculation of the value is easy, but the calculation of the inverse is infeasible. A trap-door one-way function is easy to calculate in one direction, but infeasible to calculate in the other direction without certain information.
Applications for Public-Key Cryptography
Public-key cryptosystems can be used for a number of different applications. They can be used for encryption/decryption as we have discussed already. They can also be used to exchange session keys. Finally, they can be used as a digital signature to sign a message using a private key to verify its authenticity. This is a part of public key infrastructure used to generate certificates to verify web traffic as detailed in the below video.
