3-17 Public Key Cryptography

Announcements

• Exam results are available. Papers can be picked up from the office immediately after class or on Wednesday.

• Undergraduate student performance will not be discussed due to the small sample size.

• Graduate student class average: $60\%$, highest score: $80\%$, lowest score: $42\%$.

• The instructor was hoping for a class average closer to $75\%$.

• Drop deadline is next week on Thursday.

• Assignment 2 will be returned before the end of the week.

• The instructor will attempt to return Assignment 3 (theory part) before the drop deadline but cannot guarantee it.

• Due to low performance, curving may be considered but will be marginal.

• Assignment 4 was given out last week and is due two weeks from today. It is expected to be relatively easy, especially the programming part, as it is a known plaintext attack.

Transition to Public Key Cryptography

• The course will now focus on public key cryptography after the spring break.

• Assignments will involve implementation rather than breaking cryptosystems.

Private Key Cryptography

• Private key cryptography involves two parties (Alice and Bob) sharing a secret key $k$ in advance.

• Alice uses $k$ to encrypt the message, and Bob uses the same key $k$ to decrypt.

• The security relies on keeping $k$ secret.

• The cryptography system is assumed to be known to the opponent, only the key $k$ is private.

• From "year minus infinity to $1976$," all cryptosystems were private key systems, despite varying methods and principles.

• Knowing the key means knowing both encryption and decryption methods.

Examples of Private Key Cryptosystems:

• Shift Cipher:

  • Encryption: $Y = X + K$

  • Decryption: $X = Y - K$

• Affine Cipher:

  • Key: $(a, b)$

  • Encryption: $Y = aX + b$

  • Decryption: $X = a^{-1}(Y - b)$

• Hill Cipher:

  • Key: Matrix $K$

  • Encryption: Multiply plaintext by matrix $K$

  • Decryption: Multiply by $K^{-1}$

• DES (Data Encryption Standard):

  • Encryption involves $16$ rounds using keys $K<em>1$ to $K</em>{16}$, deterministically generated from a master key.

  • Decryption also involves $16$ rounds but uses the keys in reverse order: $K<em>{16}$ to $K</em>1$.

• Crucial Point: Knowing the encryption key implies knowing all round keys, thus enabling decryption.

New Directions: The Advent of Public Key Cryptography

• In $1976$, Diffie and Hellman introduced the idea of public key cryptography in their paper "New Directions in Cryptography."

• They proposed the possibility of making the encryption rule public while keeping the decryption rule private.

• The core concept: Anyone can encrypt a message, but only the intended recipient can decrypt it.

• This was a drastic paradigm shift, breaking the age-old tradition that knowing how to encrypt also meant knowing how to decrypt.

Public Key Cryptosystem Concept

• Encryption rule $E<em>{k}$ can be made public, but the decryption rule $D</em>{k}$ remains private.

• This is the fundamental concept of public key cryptography.

Main Advantages of Public Key Cryptosystems

• Eliminates the need for prior secret key exchange between communicating parties.

• Enables secure communication with strangers, opening up e-commerce possibilities.

Analogy:

• Private Key Model: Box with a padlock; Alice locks and sends the box to Bob, who uses the same key to unlock it. The bad guy intercepts the box but cannot open it because he doesn't have the key. In this model, Alice and Bob must exchange a copy of the same key before communicating.

• Public Key Model: Number lock where anyone can lock the lock without knowing the combination, but only the owner (Bob) knows the combination to open it. This achieves separation between encryption and decryption operations.

Public Key Cryptosystem: Keys

• Every user has a pair of keys: a public key and a private key.

• Public Key: Used for encryption and known to everyone ($E<em>{A}$, $E</em>{B}$, $E_{C}$, etc.).

• Private Key: Used for decryption and kept secret ($D<em>{A}$, $D</em>{B}$, $D_{C}$, etc.).

• If Alice wants to send a message $X$ to Bob, she encrypts it using Bob's public key ($E<em>{B}$), creating ciphertext $Y</em>{1}$.

• If Alice wants to send the same message $X$ to Charlie, she uses Charlie's public key ($E<em>{C}$), creating ciphertext $Y</em>{2}$.

• A public directory contains everyone's names and public keys.

• The key idea is to separate this encryption from the decryption.

Important Distinction

• Simply having two separate keys (encryption key, decryption key) is not enough.

• It should not be possible to efficiently compute the decryption key from the knowledge of the encryption key.

• Ability to hide the decryption key from the encryption key is important.

Public Key Distribution

• Two models:

  • Centralized: User generates key pair ($P<em>{k}$, $S</em>{k}$) and sends $P_k$ to a server, which maintains a directory. Bob retrieves Alice's public key from the server.

  • Grassroots: Alice directly gives her public key to anyone she wants to communicate with.

• Assumption: No active adversary modifies the public key during dissemination.

• Attacker knowing $P_{k}$ is not a security problem since it's public. Modification of the key is an issue.

Cryptography Concerns and Solutions

• Two fundamental concerns:

  • Secrecy (Confidentiality)

  • Integrity

Solutions:

• Private Key Setting:

  • Secrecy: Private key encryption.

  • Integrity: Message Authentication Code (MAC).

• Public Key Setting:

  • Secrecy: Public key encryption.

  • Integrity: Digital Signature Scheme.

• The course will now focus on the public key encryption and digital signature schemes.

How Public Key Cryptography Addresses Drawbacks of Private Key

• Drawbacks of Private Key Cryptography:

  • Key distribution problem: Secret agreement on the key is needed.

  • Key management problem: $n$ users require $\binom{n}{2}$ keys.

• Public Key Cryptography Advantages:

  • No key distribution problem: Keys can be distributed publicly.

  • Simplified key management: Linear number of keys instead of quadratic.

  • Enables communication with strangers.

Public Key Cryptography: Stronger than Private Key

• Public key cryptography can do everything that private key cryptography can do.

• Private key cryptosystems cannot provide the ability to communicate without a pre-order agreement.

• However, public key systems are significantly SLOWER than private key ones.

Why Study Private Key Cryptography?

• Speed: Public key systems are much slower (two-three orders of magnitude) than private key systems.

• Communication Overhead: Also need high communication.

• Using Hybrid Encryption: For sending a long message, encrypt the message using a fast private key cryptosystem (DES). Encrypt the DES key using a public key cryptosystem. Send the encrypted key along with the encrypted message.

Public Key Encryption Model

• Alice generates a public key and a private key.

• Alice makes the public key known.

• Bob gets Alice's Public Key.

• Bob sends the ciphertext $C$ to Alice, who uses her private key to decrypt.

Technical Definition of a Public Key Encryption Scheme

• A public key encryption scheme consists of three spaces (plaintext space, ciphertext space, key space) and three algorithms (key generation, encryption, decryption).

• Key Generation Algorithm: Takes $1^{n}$ as input (where $n$ dictates the security level) and outputs a public key $pk$ and a secret key $sk$.

• Encryption Algorithm: Transforms the plaintext into a ciphertext $C$.

• Decryption Algorithm: Takes a ciphertext and outputs a message $m$.

• Correctness: If we take any message encrypted with Alice's public key, and Alice decrypts it with her own secret key, then at any cost we should get the message $M$ back: $D<em>{sk}(E</em>{pk}(m)) = m$.

Impossibility of Unconditional Security in Public Key Cryptography

• Public key cryptosystems cannot provide unconditional security.

• Given a ciphertext, an attacker can encrypt every possible plaintext using the public key until a match is found.

Building a Public Key Cryptosystem: Trapdoor One-Way Functions

• One Way Function: easy to compute in the forward direction, but difficult to compute in the backward direction.

• Given $X$, it should be easy to compute $Y$, the encryption of $X$.

• Given $Y$, it should be difficult to compute $X$.

• A function from plaintext space to ciphertext space $P \to C$.

• Easy to compute means polynomial time computable; difficult to compute means no polynomial time algorithm should exist for backward computation.

• It does not matter if one way function really exists.

Functions

• One Way Function: Real Life: Smashing glass, breaking jigsaw puzzles, building a reputation.

• A one way function is forward easy to compute, backward it's tough to compute—that's what a one way function is.

• This one way function should ideally be polynomial time computable, but determining if something is a one way function remains an open problem, particularly related to the P versus NP problem, which is a significant open problem in computer science.

Trapdoor One-Way Functions are Necessary

• We require that given $Y$, it should be difficult to figure out the $X$.

• However, with trapdoor information (special information only the intended recipient has), $X$ should be easily computable from $Y$—normally it is difficult to compute but with the trapdoor, it becomes easy.