Introduction to Information Security

Computer Systems Security

Public key cryptography

Insufficiencies with Symmetric Encryption

• Symmetric encryption is not enough to address two key issues
• key distribution – how to have secure communications in general without having to trust a KDC with your key?
• digital signatures – how to verify that a received message really comes from the claimed sender?

Advent of Asymmetric Encryption

• Probably most significant advance in the 3000 year history of cryptography
• Use two keys: a public key and a private key
• Asymmetric since parties are not equal
• Clever application of number theory concepts instead of merely substitution and permutation

How Asymmetric Encryption Works

• Asymmetric encryption uses two keys that are related to each other
• a public key, which may be known to anybody, is used to encrypt messages, and verify signatures
• a private key, known only to the owner, is used to decrypt messages encrypted by the matching public key, and create signatures
• the key used to encrypt messages or verify signatures cannot decrypt messages or create signatures

Public key Encryption

• Alice has a key pair: public and private
• publish the public key such that the key is publicly known
• Alice keeps the private key secret
• Other people use Alice’s public key to encrypt messages for Alice
• Alice uses her private key to decrypt
• Only Alice can decrypt since only Alice has the private key

Message
rfwekfs
Encrypt
Public key
Message
rfwekfs
Decrypt
Private key

• Trick: To compute the private key from the public key is a difficult problem.

Asymmetric Encryption for Confidentiality

Bob
Alice