Yorkville High School Computer Science Department
Yorkville High School Computer Science Department on Facebook  Yorkville High School Computer Science Department Twitter Feed  Yorkville High School Computer Science Department on Instagram

Yorkville High School Computer Science

ASSIGNMENTS: Compiler Part 1 - November 19, 2018 :: Challenges 6 - November 19, 2018 :: Compiler Part 2 - December 3, 2018 >>

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:

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.

Public-Key Encryption

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.

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.

Yorkville High School Computer Science Department on Facebook Yorkville High School Computer Science Department Twitter Feed Yorkville High School Computer Science Department on Instagram