Lecture 4 - Cryptography I

Cryptography definition

Originally meant "hidden writing" (from Greek kryptos + graphein); now refers to encryption that makes message contents inaccessible to outsiders.

Plaintext M

Unencrypted message; the original readable content.

Ciphertext C

Output of encryption; unreadable without the key.

Key k

Critical secret parameter used for encryption/decryption; security depends on secrecy of k.

Cryptography goals

Confidentiality (hide message), Integrity (message unchanged), Authentication (verify sender).

Kerckhoffs' Principle

Cryptosystem must remain secure even if everything except the secret key is public; forbids security-through-obscurity.

Classic vs Modern ciphers

Classic = character-level (transposition/substitution). Modern = bits/integers; symmetric & asymmetric crypto.

Transposition cipher

Reorders characters without changing characters themselves (e.g., Skytale).

Substitution cipher

Replaces characters with other characters according to a rule (e.g., Caesar/affine).

Symmetric cryptography

Uses the *same key* for encryption and decryption.

Asymmetric cryptography

Uses *different keys* (public/private) for encryption and decryption.

Skytale cipher

Military cipher: plaintext = strip wrapped on staff; ciphertext = unwrapped strip; key = staff diameter.

Prime definition

Integer p > 1 whose only divisors are 1 and p.

Composite definition

Integer n > 1 that is not prime.

Greatest Common Divisor

gcd(a, b) = largest integer dividing both a and b.

Least Common Multiple

lcm(a, b) = smallest positive integer divisible by both a and b.

Bézout’s Identity

There exist integers u, v such that ua + vb = gcd(a, b).

FTA (Fundamental Theorem of Arithmetic)

Every integer ≥ 2 factors uniquely into primes (up to ordering).

Factoring method (trial division)

Divide by primes ≤ sqrt(n); record exponents; if remainder > 1, it's prime.

Example factorization: 360

360 = 2^3 * 3^2 * 5.

Example factorization: 1001

1001 = 7 * 11 * 13.

Example factorization: 2310

2310 = 2 * 3 * 5 * 7 * 11.

Example factorization: 8192

8192 = 2^13.

Example factorization: 999

999 = 3^3 * 37.

Example factorization: 5040

5040 = 2^4 * 3^2 * 5 * 7.

Naive GCD method

Factor both numbers; take minimum exponent of each prime; multiply.

GCD/LCM example (360, 168)

gcd = 24; lcm = 2520 (verified by 360*168 = gcd * lcm).

Number-theory functions

n = prime factorization p_i^e_i; τ(n)=Π(e_i+1); φ(n)=Π p_i^(e_i−1)(p_i−1).

Trial division limitations

Fast only for small factors; large primes require modern factoring algorithms (e.g., Pollard rho).

Modular arithmetic definition

Arithmetic performed over finite set {0,…,m−1}; a ≡ r mod m means m divides (a−r).

Remainder non-uniqueness

12 ≡ 3 ≡ 21 ≡ −6 (mod 9); many integers map to same equivalence class.

Equivalent class concept

All integers sharing same remainder mod m form a class; for m = 9, classes 0–8.

Modular exponent example

3^8 mod 7 = 2 (can simplify via partial reductions).

Integer ring Zm

Set {0,…,m−1} with addition and multiplication mod m.

Ring properties

Closed, associative, identity elements, additive inverses, distributive law; multiplicative inverses exist only for some elements.

Multiplicative inverse condition

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

Finding inverse example

In Z26, 15 has inverse (gcd=1) but 14 does not (gcd=2).

Shift cipher definition

Caesar cipher; encrypt with e_k(x)=x+k mod 26; decrypt with d_k(y)=y−k mod 26.

Shift cipher example

HELLO → QNUUX for k = 9-shifted alphabet; ATTACK → key 17 → RKKRTB.

Affine cipher definition

Encrypt e(x)=ax+b mod 26; decrypt d(y)=a^(-1)(y−b) mod 26; requires gcd(a,26)=1.

Invertible a values mod 26

In Z26, valid a values = {1,3,5,7,9,11,15,17,19,21,23,25}.

Finding inverse example (a=3)

3 * 9 ≡ 27 ≡ 1 mod 26 → 3^(-1)=9.

Affine cipher example

k=(a,b)=(9,13); ATTACK → NCCNFZ.

Shift/affine insecurity

Small keyspace, monoalphabetic mapping; vulnerable to brute force & frequency analysis.

Group definition

Set G with operation ∘ satisfying closure, associativity, identity, and inverse.

Abelian group

A group where a∘b = b∘a.

Group examples

(Z,+) is abelian; nonzero integers under multiplication are not a group; complex numbers under multiplication form abelian group.

Multiplicative group Z*_n

Elements of Z_n relatively prime to n under multiplication mod n; forms finite abelian group.

Example Z*_9

Z*_9 = {1,2,4,5,7,8}.

Finite groups

Finite cardinality |G|; e.g., |Z_n| = n, |Z*_n| = φ(n).

Element order definition

Smallest k ≥ 1 such that a^k ≡ 1 mod m.

Element order example

In Z*_11, ord(3)=5.

Cyclic group definition

Has generator α such that ord(α)=|G|; every element is α^i.

Theorem (Z*_p is cyclic)

Multiplicative group mod prime p is cyclic.

Two theorems for finite groups

If G finite and a∈G: (1) a^(|G|)=1. (2) ord(a) divides |G|.

Crypto-relevant algebra

Many cryptosystems rely on Zm, Z*_p, groups, orders, and properties of invertibility.

Cryptography takeaways

Cryptography requires confidentiality, integrity, authentication; Kerckhoffs Principle; number theory underlies modern crypto.