Lecture 5 - Cryptography II

Crypto goals

Cryptography aims for confidentiality, integrity, and authentication over insecure channels.

Kerckhoffs’ Principle

Cryptosystems remain secure even when everything except the key is public; no security through obscurity.

Number theory foundation

Primes, FTA, gcd/lcm, modular arithmetic underpin modern cryptography.

Ring Zm

Arithmetic modulo m forms a ring (addition, multiplication closed mod m).

Multiplicative inverses in Zm

An element a has an inverse mod m iff gcd(a, m) = 1.

Group relevance

Groups (especially Z*_p) structure modern cryptographic algorithms.

Cyclic group definition

A group G is cyclic if it has an element of order |G|; this element is a generator.

Generator α property

Every element g in G can be expressed as α^i for some integer i.

Infinite cyclic group example

(Z, +) is cyclic and infinite, generated by 1 or –1.

Finite cyclic group example

(Z/nZ, +) is cyclic of order n, generated by [1] or any [k] with gcd(k,n)=1.

Non-cyclic example

The multiplicative group modulo 8 (Z*₈ = {1,3,5,7}) has no generator.

Shift & Affine recap

Classic symmetric ciphers good for intuition but insecure in real-world applications.

Symmetric cipher idea

A single shared secret key is used for both encryption and decryption.

Symmetric encryption example

Alice encrypts using the shared key; Bob decrypts with the same key over an insecure medium.

Unconditional security

A cryptosystem is unconditionally secure if it cannot be broken even with infinite computational resources.

OTP definition

One-Time Pad is a symmetric cipher that achieves perfect secrecy.

OTP inventor

Described in 1882 by Frank Miller.

OTP basic idea

Key as long as plaintext, key is truly random, XOR for encryption and decryption.

OTP encryption

C = M ⊕ K (bitwise XOR).

OTP decryption

M = C ⊕ K.

Conditional probability refresher

P(B|A) = P(A ∩ B) / P(A); independence if P(B|A) = P(B).

OTP perfect secrecy definition

A system is perfectly secret if P(M=m | C=c) = P(M=m) for all messages and ciphertexts.

OTP perfect secrecy theorem

If K is chosen uniformly at random from all n-bit strings, OTP is perfectly secret.

Setup for proof

M, K, C are n-bit random variables, K uniformly distributed, M ⊥ K.

Perfect secrecy proof step 1

P(C=c) = 1/|K| since all keys lead to unique plaintext-ciphertext pairs.

Perfect secrecy proof step 2

P(M=m ∧ C=c) = P(M=m)/|K|.

Perfect secrecy proof step 3

Bayes rule gives P(M=m | C=c) = P(M=m); ciphertext gives no new information.

Intuition: ciphertext independence

Every possible plaintext is equally likely given a ciphertext because every key is equally likely.

Key pitfall 1

Assuming C and K independent; incorrect—C depends on K.

Key pitfall 2

Non-uniform keys break perfect secrecy.

Key pitfall 3

Message-key dependence breaks perfect secrecy.

OTP equalities recap

C = M ⊕ K, and for fixed m, only one key k = c ⊕ m produces ciphertext c.

Keyspace requirement theorem

In perfectly secret systems, |K| ≥ |M|; number of keys must be at least number of messages.

Keyspace intuition

Each ciphertext must be able to decrypt to each message using some key; else secrecy fails.

OTP failure mode: key reuse

Reusing a pad leaks structure; XOR of two ciphertexts removes the key → dangerous.

Historical note

Venona project succeeded by exploiting OTP key reuse.

OTP security conditions

(1) Key same size as plaintext; (2) key truly random; (3) key never reused; (4) key fully secret.

OTP impracticality

Storage, distribution, randomness, and non-reuse requirements make OTP rarely usable in practice.

Need for algebraic structures

Desire for addition, subtraction, multiplication, division in one structure motivates fields.

Field definition

Set F with + and × such that (F,+) is an additive group, (F−{0},×) is a multiplicative group, and distributive law holds.

Field example: Reals

R with usual + and × forms a field (additive inverse = –a; multiplicative inverse = 1/a).

Integers not a field

Z has no multiplicative inverse for most elements, e.g., 2 has no inverse in Z.

Finite field (Galois field)

Fields with finitely many elements; order must be a prime power p^n.

Characteristic of a finite field

The prime p such that field order = p^n.

Finite field relevance

Symmetric ciphers and ECC operate in finite fields; structure affects security and efficiency.

In-class field examples

Z/6Z is not a field (6 not prime; zero divisors).

Z/11Z is a field (prime modulus).

Z/256Z is a field (256 = 2^8 = prime power).

Ring that is not field

Z/6Z: fails multiplicative inverses for many nonzero elements.

Orders in Z*₁₁

Size = φ(11)=10; element orders divide 10: possible orders={1,2,5,10}.

Subgroup definition

A subgroup H ≤ G is a subset that forms a group under the same operation.

Cyclic subgroup theorem

Each element generates a cyclic subgroup of size equal to its order.

Lagrange’s theorem

For finite group G, |H| divides |G| for any subgroup H.

Shift cipher revisit

Encryption: e_k(x)=x+k mod n.

Affine cipher revisit

Encryption: e(x)=ax+b mod n where gcd(a,n)=1.

Move to exponentiation

It is natural to consider exponentiation in groups after addition and multiplication.

Discrete Logarithm Problem (DLP)

Given g, h in group G, find x such that g^x = h; computation hard in large cyclic groups.

Discrete logarithm notation

x = log_g(h).

Finite cyclic group requirement

DLP defined only when G is finite cyclic.

DLP complexity

Point: exponentiation is easy, discrete log is hard → one-way function.

DLP group settings

Finite fields, prime-order subgroups, elliptic curve groups.

Key distribution problem

Assumed Alice and Bob share a key — but how? Need explicit method.

Diffie–Hellman (DH) key exchange

Protocol allowing two parties to agree on shared secret over insecure channel.

DH parameters

Public p (prime) and g (generator of Z*_p).

DH Alice step

Picks private a, sends A = g^a mod p.

DH Bob step

Picks private b, sends B = g^b mod p.

DH shared secret

K = g^(ab) mod p, computed as B^a or A^b.

DH toy example

p=13, g=2; Alice a=5 → A=6; Bob b=8 → B=9; both compute K=3.

DH real-world key use

Shared value must be processed via a KDF (key derivation function), not used directly.

DH properties

Key establishment works over insecure medium; no prior shared key needed.

DH limitations

Still need O(n²) keys for n people; slow group operations; vulnerable to Man-in-the-Middle attack.