Public Key Encryption (continued) and Digital Signatures

CS 161 Fall 2021 - Lecture 15

Computer Science 161

Popa and Weaver

Popa and Weaver

Announcements

• Start recording
• Homework 3 is due Friday, October 1st, 11:59 PM PT
• The midterm is Thursday, October 7th, 7:00 PM–9:00 PM PT
• Exam logistics and conflict form have been sent out!

2

Computer Science 161

Popa and Weaver

Popa and Weaver

ElGamal Encryption

3

Textbook Chapter 11.4

Computer Science 161

Popa and Weaver

Popa and Weaver

Cryptography Roadmap

• Hash functions
• Pseudorandom number generators
• Public key exchange (e.g. Diffie-Hellman)

4

• Key management (certificates)
• Password management

Computer Science 161

Popa and Weaver

Popa and Weaver

ElGamal Encryption

• Based on the same cryptographic assumption as Diffie-Hellman key exchange
• Assume everyone knows a large prime p (e.g. 2048 bits long) and a generator g

Two cryptographic assumptions:

• Discrete logarithm problem: Given g, p, g^a mod p for random a, it is computationally hard to find a
• Diffie-Hellman assumption: Given g, p, g^a mod p, and g^b mod p for random a, b, no polynomial time attacker can distinguish between a random value R and g^ab mod p.
• Implies the hardness of the discrete logarithm problem
• Sufficient assumption for Diffie-Hellman key exchange and for El Gamal

5

Computer Science 161

Popa and Weaver

Popa and Weaver

ElGamal Encryption: Protocol

• Public parameters: Let p be a large prime (say 2048) and g a generator mod p
• KeyGen():
• Generate private key sk randomly mod p
• Compute public key PK = g^sk mod p
• Enc(PK, M): for 0 < M ≤ p - 1
• Generate a random r mod p and computes g^r mod p
• Compute M × (PK)^r mod p
• Output (C1 = g^r mod p, C2 = M × (PK)^r mod p),
• Dec(sk, (C₁, C₂))
• Compute and output C₂ × (C₁)^-sk mod p
• Correctness: Let’s verify that this is indeed M. If we substitute C₁ and C₂, we obtain:

M × (PK)^r × (g^r mod p)^-sk = M × (g^sk)^r × (g^r )^-sk = M mod p

6

Repeated squaring for efficient exponentiation from CS70

Computer Science 161

Popa and Weaver

Popa and Weaver

ElGamal Encryption: Security

• Recall Diffie-Hellman problem: Given g^a mod p and g^b mod p: g^ab mod p is indistinguishable from random (mod p)
• ElGamal sends these values over the insecure channel
• Public key: g^sk mod p
• Ciphertext: M × (g^sk)^r mod p, g^r mod p
• So (g^sk)^r mod p is indistinguishable from random and so is M × (g^sk)^r mod p

7

Computer Science 161

Popa and Weaver

Popa and Weaver

ElGamal Encryption: Issues

• Is ElGamal encryption semantically secure?
• Yes, for 1<=M<=p-1
• No, if M can be 0 too.

8

Computer Science 161

Popa and Weaver

Popa and Weaver

ElGamal Malleability

• Recall: Enc(g^sk, M) outputs g^r mod p, M × (g^sk)^r mod p
• The adversary can very easily tamper with the message
• The adversary can manipulate C1' = C1, C2' = 2 × C2 = 2 × M × (g^sk)^r to make it look like 2 × M was encrypted
• This does not contradict semantic security, but provides reminder that encryption does not provide integrity
• It can be a feature some times: homomorphic encryption (encryption in which an operation on the ciphertext results in an operation on the underlying plaintext).

​

9

Computer Science 161

Popa and Weaver

Popa and Weaver

Hybrid Encryption

• Issues with public-key encryption
• Notice: We can only encrypt small messages because of the modulo operator
• Notice: There is a lot of math, and computers are slow at math
• Result: We don’t use asymmetric for large messages
• Hybrid encryption: Encrypt data under a randomly generated key K using symmetric encryption, and encrypt K using asymmetric encryption
• Enc_Asym(PK, K); Enc_Sym(K, large message)
• Benefit: Now we can encrypt large amounts of data quickly using symmetric encryption, and we still have the security of asymmetric encryption

10

Computer Science 161

Popa and Weaver

Popa and Weaver

Digital Signatures

11

Textbook Chapter 12

Computer Science 161

Popa and Weaver

Popa and Weaver

Cryptography Roadmap

• Hash functions
• Pseudorandom number generators
• Public key exchange (e.g. Diffie-Hellman)

12

• Key management (certificates)
• Password management

Computer Science 161

Popa and Weaver

Popa and Weaver

Digital Signatures

• Asymmetric cryptography is good because we don’t need to share a secret key
• Digital signatures are the asymmetric way of providing integrity/authenticity to data
• Assume that Alice and Bob can communicate public keys without Mallory interfering

13

Computer Science 161

Popa and Weaver

Popa and Weaver

Digital Signatures: Definition

• Three parts:
• KeyGen() → PK, SK: Generate a public/private keypair, where PK is the verify (public) key, and SK is the signing (secret) key
• Sign(SK, M) → sig: Sign the message M using the signing key SK to produce the signature sig
• Verify(PK, M, sig) → {0, 1}: Verify the signature sig on message M using the verify key PK and output 1 if valid and 0 if invalid
• Properties
• Correctness: Verification should be successful for a signature generated over any message
• Verify(PK, M, Sign(SK, M)) = 1 for all PK, SK ← KeyGen() and M
• Efficiency: Signing/verifying should be fast
• Security: EU-CPA, same as for MACs except that the attacker also receives PK
• Namely, no attacker can forge a signature for a message for which it did not receive a signature

14

Computer Science 161

Popa and Weaver

Popa and Weaver

RSA Signatures

15

Textbook Chapter 12.2–12.4

Computer Science 161

Popa and Weaver

Popa and Weaver

RSA Signature Syntax

• KeyGen():
• Randomly pick two large primes, p and q
• Compute N = pq
• N is usually between 2048 bits and 4096 bits long
• Choose e
• Requirement: e is relatively prime to (p - 1)(q - 1)
• Requirement: 2 < e < (p - 1)(q - 1)
• Compute d = e^-1 mod (p - 1)(q - 1)
• Algorithm: Extended Euclid’s algorithm (CS 70, but out of scope)
• Public key: N and e
• Private key: d

16

Computer Science 161

Popa and Weaver

Popa and Weaver

RSA Signatures Syntax

• Sign(d, M):
• Compute H(M)^d mod N
• Verify(e, N, M, sig)
• Verify that H(M) ≡ sig^e mod N

17

Computer Science 161

Popa and Weaver

Popa and Weaver

RSA Signatures: Correctness

Theorem: sig^e ≡ H(M) mod N

Proof:

• Euler’s theorem: for all a mod p, a^φ(N) ≡ 1 mod N
• φ(N) is the totient function of N = number of elements coprime with N
• For p and q prime, φ(pq) = (p - 1)(q - 1)
• CS 70 knowledge
• Notice: ed ≡ 1 mod (p - 1)(q - 1) so ed ≡ 1 mod φ(N)
• This means that ed = kφ(n) + 1 for some integer k
• sig^e mod N can be written as H(M)^ed ≡ H(M)^{kφ(N) + 1} ≡ H(M) mod N
• H(M)^kφ(N)H(M)¹ ≡ H(M) mod N
• 1H(M)¹ ≡ H(M) mod N
• H(M) ≡ H(M) mod N

18

Computer Science 161

Popa and Weaver

Popa and Weaver

RSA Digital Signatures: Security

Necessary hardness assumptions:

• Factoring hardness assumption: Given N large, it is hard to find primes pq = N
• Discrete logarithm hardness assumption: Given N large, hash, and hash^d mod N, it is hard to find d

The actual sufficient hardness assumption and proof of security are out of scope.

​

19

Computer Science 161

Popa and Weaver

Popa and Weaver

Summary

• Public-key cryptography: Two keys; one undoes the other
• Public-key encryption: One key encrypts, the other decrypts
• Security properties similar to symmetric encryption
• ElGamal: Based on Diffie-Hellman
• The public key is g^b, and C1 is g^r.
• Not IND-CPA secure on its own
• Hybrid encryption: Encrypt a symmetric key, and use the symmetric key to encrypt the message
• Digital signatures: Integrity and authenticity for asymmetric schemes
• RSA: Same as RSA encryption, but encrypt the hash with the private key

20

Computer Science 161

Popa and Weaver

Popa and Weaver