AMS 103 IV: Data Security 🔐🪪

"LAPD! LAPD SWAT! POLICE! GET ON THE GROUND! SHOW ME YOUR HANDS!"

What is cryptography?

The science of secret writing, including methods for encryption and decryption.

Cipher

An algorithm for performing encryption or decryption.

Main goals of cryptography

Privacy, authentication, and tamper detection.

Kerckhoffs’ Principle

A system should remain secure even if everything except the key is public

Why security through obscurity is weak

If the method is discovered, the entire system fails.

Caesar cipher mechanism

Shifts each letter by a fixed number of positions.

Scytale cipher mechanism

Wrap text around a rod; unwrapped text appears scrambled.

Enigma machine key feature

Rotors change position after each keypress, altering the substitution.

Definition of modular arithmetic

Arithmetic where values wrap around a modulus n.

Meaning of a ≡ b (mod n)

a and b leave the same remainder when divided by n.

Compute 37 mod 12

1

Compute 1024 mod 7

2

Modular addition rule

(a + b) mod n = (a mod n + b mod n) mod n

Modular multiplication rule

(a · b) mod n = (a mod n · b mod n) mod n

Definition of gcd(a, b)

The largest integer dividing both a and b.

When are two numbers relatively prime?

When gcd(a, b) = 1.

Euclid’s Algorithm purpose

Computes gcd(a, b) by repeated remainder reduction.

Prime number definition

An integer >1 with no divisors except 1 and itself.

Fundamental Theorem of Arithmetic

Every integer >1 has a unique prime factorization.

Definition of modular exponentiation

Efficient computation of a^b mod n using repeated reduction.

Why modular exponentiation is used in cryptography

It keeps numbers small and avoids computing huge a^b directly.

Definition of discrete logarithm problem

Given g^x mod n, find x.

Why discrete logs are hard

No inverse formula; outputs appear random; must try many possibilities.

Why composite moduli fail for discrete logs

Values cycle early and do not spread uniformly.

Diffie–Hellman public values

g, n, g^a mod n, g^b mod n

Diffie–Hellman shared secret formula

k = g^{ab} mod n

Why Diffie–Hellman is secure

Recovering a or b requires solving a discrete logarithm.

RSA public key components

e and n

RSA private key components

d, p, q

RSA modulus definition

n = p × q

Euler totient for RSA

φ(n) = (p−1)(q−1)

Condition for choosing RSA exponent e

1 < e < φ(n) and gcd(e, φ(n)) = 1

Condition defining RSA private exponent d

ed ≡ 1 mod φ(n)

RSA encryption formula

C = M^e mod n

RSA decryption formula

M = C^d mod n

Why RSA works

Because M^{ed} ≡ M mod n.

Requirement for RSA message M

0 < M < n and gcd(M, n) = 1

How messages are encoded for RSA

Convert text → ASCII → binary → integer M.

Hamming C(7,4) purpose

Detects and corrects a single-bit error.

Hamming C(7,4) parity bit formulas

v5 = v1+v2+v4, v6 = v1+v3+v4, v7 = v2+v3+v4 (mod 2)

Why Hamming C(7,4) corrects one error

Each single-bit error produces a unique parity mismatch pattern.

Addition Principle

If sets are disjoint, total outcomes = r1 + r2 + ... + rm.

Multiplication Principle

If stages are independent, total outcomes = r1 × r2 × ... × rm.

Definition of factorial n!

n! = n(n−1)(n−2)...1

Permutation formula P(n, r)

P(n, r) = n! / (n−r)!

Combination formula C(n, r)

C(n, r) = n! / (r!(n−r)!)

Circular permutation count

(n-1)!

Basic probability formula

P(E) = |E| / |S|

Binary sequences of length n

2^n

Probability a binary sequence of length 8 has 6 ones

C(8, 6) / 2^8