Public-Key Encryption

Overview

Public-key encryption uses asymmetric key pairs: a public key for encryption and a private key for decryption.

RSA

Key Generation

Find d, d·e¹ mod P(n)

Public key → (n,e) Private key → d

Encryption & Decryption

Encrypt → c = mᵉ mod n

Decrypt → m = cᵈ mod n

Correctness of RSA (𝒫, 49)

Euler’s Theorem → aᵖ⁽ⁿ⁾ = 1 mod n

• gcd(a,n) = 1
• σ = H(n)ᵈ mod n.

Since pq = n, ed ≡ 1 mod P(n) ← Prove this:

σᵉ ≡ H(m)ᵉᵈ ≡ H(m)¹ᵐᵒᵈᵏ⁽ⁿ⁾⁺¹ ≡ H(m)¹ᵏ⁽ⁿ⁾ᵏ⁺¹ ≡ H(m)ᵏᵖ⁽ⁿ⁾ᵏ · H(m) ≡ H(n) mod n

ECC (Elliptic Curve Cryptography)

Key Pair

public key, private key = (pk, sk) = (a, a·P)

• P = generator
• Example: a = 5, · (5, 5P)
• P: (2,7)

Encryption & Decryption

ciphertext = (u, v)

encrypt:

• u = gᵇ
• v = m·(pk_a)ᵇ = m·gᵃᵇ

Note: mod 𝒫 when doing with generator

decrypt:

• m = v·u⁻ᵃ
• = m·(gᵇᵃ)·(gᵇ)⁻ᵃ
• = m·(pk_a)ᵃ·(gᵇ)⁻ᵃ

Note: mod E(a) when doing encryption/decryption

Functions:

• E(pk = (a, pk), m)
• D(sk, rec(u,v))
• C = (u,v)

ElGamal

Key Pairs

2 pairs = (sk_a, pk_a) = (a,gᵃ), (sk_b, pk_b) = (b,gᵇ)

Encryption & Decryption

Ciphertext = (u,v)

encrypt:

• u = gᵇ
• v = m·(pk_a)ᵇ = m·gᵃᵇ

decrypt:

• m = v·u⁻ᵃ
• = m·(gᵇᵃ)·(gᵇ)⁻ᵃ

Functions:

• E(pk = (g, pk), m)
• D(sk, rec(u,v))
• C = (u,v)

Symmetric Ciphers Diagram

For comparison with public-key systems:

m →|E|→ c →|D|→ m
    ↑k         ↑k

In symmetric: same key k In asymmetric: different keys (public/private)