Chapter 7: Public Key Cryptography

Question 1

Why would we need Public Key Cryptography?

Answer 1

• Introduced ciphers and authentication mechanisms require a common, pre-shared, secret key
• Out-of-band sharing is not always an option
• Key exchange needs to be conducted securely
• Symmetric mechanisms require a considerable amount of keys in the system

Question 2

Why would we need PKI?

• Asymmetric Crypto reduces the number of keys in the system :
  Assume n parties, only unique keys and asymmetric crypto:

Answer 2

• Every party has a public key and a private key
• Every party keeps their own private key secret
• Every party publishes their public key
• Amount of secret keys in the system: n ∈ O(n)

Question 3

• Different keys used for en-/decryption:

Answer 3

Question 4

Discussion: Symmetric vs. Asymmetric Encryption

• Benefits of asymmetric encryption mechanisms include
• But what about integrity and authenticity of the exchanged public key?
• Example: Can we just …
• … publish a public key on a website?
• … send a public key via mail to friends?

Answer 4

1 * Number of keys needed in a communication system is reduced
2 * Public keys are not required to be exchanged between participants of the communication system via a secure
channel that guarantees confidentiality of the key

• Certainly not, as the integrity and authenticity of the received key cannot be guaranteed.

Question 5

RSA Cipher Mathematical Background

Answer 5

Question 6

How are they generated? (RSA Cipher)

Answer 6

Question 7

RSA Cipher

Public Key Algorithm

Define encryption and decryption.

Answer 7

Why does RSA Cipher work? ON SLIDES.

Question 8

RSA for confidentiality

What are the assumptions?

Answer 8

• We choose a random x andcompute c = xe mod n
• Then x can not be recovered
• Relation between c and x looks random enough when keys unknown

Question 9

Problems with RSA for confidentiality

In order to achieve confidentiality we need to use a suitable encryption scheme based on RSA! WHY?

Answer 9

Solution: * Employ Padding (“enlarges m”)
* Add random bits (“adds non-determinism”, “avoids 0”)
* Schemes: PKCS, OAEP

Question 10

RSA for Confidentiality

OAEP (Optimal asymmetric encryption padding)

Provide the notation and the output.

Answer 10

Question 11

RSA for Integrity

Observations? Can we do Better?

Answer 11

Yes, we can do better.

• Dedicated signature schemes exist
• Example: RSA-PSS, part of PKCS standards
• RSA-PSS hashes m twice, adds padding and salt
• Result is encrypted with Ksec

Question 12

Hybrid Encryption Scheme

Why do we need it, instead of asymmetric crypto? What’s the idea?

Answer 12

Problems with Asymmetric Crypto:
* Very expensive
* Orders of magnitude slower than symmetric crypto or hashing
* Unsuitable to encrypt larger amounts of data

Idea:
* Hybrid Encryption Scheme
* Use public key cryptography to securely exchange (ephemeral) symmetric key
* Use symmetric cryptography to encrypt the actual payload data

Question 13

Hybrid Encryption Scheme: Key Agreement

How does it work?

Answer 13

New Idea:
* Alice does not decide and send a symmetric key
* A key agreement protocol is used to establish a shared key
* Key agreement protocols usually also
* Authenticate the entities
* Provide additional communication protection
* Well-known example: Diffie-Hellman key exchange protocol