Computer Security Lecture 4

What is cryptography?

It originally meant “hidden writing” (from Greek). Today it is the science of making message contents inaccessible to outsiders.

Main goals of cryptography

Confidentiality, Integrity, Authentication.

Kerckhoffs’ Principle

A system must remain secure even if everything except the secret key is public; no security through obscurity.

Prime number

An integer p > 1 whose only divisors are 1 and p.

Composite number

An integer n > 1 that is not prime.

gcd(a,b)

The greatest integer dividing both a and b.

lcm(a,b)

The 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).

Fundamental Theorem of Arithmetic

Every integer ≥2 has a unique prime factorization (up to order).

Trial division

Factor by dividing n by primes up to √n and recording exponents.

gcd via factorization

Use the minimum prime exponents of a and b.

lcm via factorization

Use the maximum prime exponents of a and b.

Definition of a ≡ b (mod m)

m divides (a − b); a and b are in the same equivalence class modulo m.

Remainders not unique

Numbers like 12, 3, 21, −6 are all ≡ 3 (mod 9).

Equivalent elements in mod arithmetic

You can replace numbers with any congruent representative; computations are unchanged.

Zm

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

When does a have an inverse mod m?

When gcd(a, m) = 1.

Caesar cipher

Encrypt: eₖ(x)=x+k mod 26; Decrypt: dₖ(y)=y−k mod 26.

Affine cipher

Encrypt: e(x)=ax+b mod 26 with gcd(a,26)=1; Decrypt: a⁻¹(y−b) mod 26.

Weakness of classical ciphers

Small keyspace and monoalphabetic substitution → easy to brute-force and frequency-analyze.

Group definition

A set with closure, associativity, identity, and inverses (commutativity if Abelian).

Z*n

The multiplicative group modulo n: all a with gcd(a,n)=1 under multiplication mod n.

Order of an element

The smallest k≥1 such that aᵏ = identity.

Cyclic group

A group generated by one element α with ord(α)=|G|.

Z*p is cyclic

For every prime p, the group of units mod p is cyclic.

Order divides group size

In any finite group, ord(a) divides |G|.