Historical Ciphers §

Caesar Ciphers §

“Shift” with wraparound. A function from $\{a, b, \dots, z\} \rightarrow \{A, B, \dots, Z\}$

Attack: Try all twenty-six possible keys

Atbash §

Reflection. $a \leftrightarrow z$, $b \leftrightarrow y$, etc.

Special case of affine cipher.

Encryption and decryption are identical.

Substitution Ciphers §

Each letter is substituted by another (distinct) letter. $26! > {10}^{20}$ ciphers in total.

Attack: frequency analysis

Vigenere Cipher §

Keyword.

Security proportional to keyword length.

Attack:

1. Find the length $k$ of the keyword
   • Kasiski Method: Look for repeated fragments. Occurrences separated by multiples of the key length.
   • Guess the Length
2. Every $k$-th letter will be a caesar cipher

$\textrm{IndCo}(s) = \frac{1}{n(n - 1)} \sum_{i = 0}^{25} F_i (F_i - 1) \approx \frac{1}{n^2} \sum_{i = 0}^{25} {F_i}^2$

$\textrm{MutIndCo}(s, t) = \frac{1}{nm} \sum_{i = 0}^{25} F_i(s) F_i(t)$

• random text: $\textrm{IndCo} \approx 0.0385$
• english text: $\textrm{IndCo} \approx 0.0685$

Modern Cryptography §

Goal: immune to code-breaking without knowing the key

Hard mathematical problems:

• DH: Given $g$ and $g^x \mod (m)$, find $x$ (discrete logarithm)
• RSA: Given $x$ and $g^x \mod (m)$, find $g$ (root extraction)

Mathematical tools:

• modular arithmetic
• extended euclidean algorithm
• fermat’s little theorem

Public-key cryptography:

• public key: anyone can send encrypted messages to Alice
• private key: only Alice can decrypt the messages

Euclid’s Algorithm §

$\gcd(a, b) \cdot lcm(a, b) = ab$

$x = qy + r \implies \gcd(x, y) = \gcd(y, r)$

For all integers $a, b$, there exist integers $x, y$ such that $ax + by = \gcd(a, b)$.

$n$-th prime approx $n \ln n$

number of primes lt $n$ $\frac{n}{\ln n}$

probability that a random number is prime approx $\frac{1}{\ln n}$

Modular arithmetic §

$a = r \mod m \implies a = mq + r$

Equivalence relation (reflexive, transitive).

• associative
• commutative
• distributive

$a = b \mod m \wedge c = d \mod m \implies a \pm c = b \pm d \mod m$

$a = b \mod m \wedge c = d \mod m \implies ac = bd \mod m$

Chinese Remainder Theorem §

Given:

• $M = m_1 \dots m_r$ where $\gcd(m_i, m_j) = 1$
• $a_1, \dots, a_r$ where $0 \leq a_j < m_j$

…there exists a unique integer $a$ such that $a \equiv \mod m_j$ for all $1 \leq j \leq r$, $0 \leq a < M$.

Fermat’s Little Theorem §

When $p$ is prime and $\gcd(n, p) = 1$:

$n^{p - 1} \equiv 1 \mod p$

$n^p \equiv n \mod p$

$n^p - n \equiv 0 \mod p$

RSA §

• choose two large primes $p$ and $q$
• $\lambda = (p - 1)(q - 1)$
• choose $e$ such that $\gcd(e, \lambda) = 1$
• $d = e^{-1} \mod \lambda$
• $e, pq$ is public; $d$ is private.

encryption: $m^e \mod pq$ where $m$ is the message and $0 < m < pq$

decryption: $m \equiv {(m^e)}^d \mod pq$

Diffie-Hellman §

secure 2-way communication. one-to-one.

• choose a large prime $p$ and its primitive root $g$
• $g^x \equiv h \mod p$, $x = \log_g h$ where $0 \leq x < p$

private keys: $a$, $b$

public keys: $A = g^a \mod p$, $B = g^b \mod p$

shared private key: $k = B^a = A^b = g^{ab} \mod p$

encryption: $km = g^{ab} m \mod p$

decryption:

• $k^{-1} = {(g^{ab})}^{-1} \mod p$ (extended euclidean algorithm)
• $m = k^{-1} km$

attacks:

• single decrypted message: $k = (km) m^{-1}$
• many encrypted messages: $km_1, km_2, \dots$. $k = \gcd(km_1, km_2, \dots)$
• MITM: eve replaces $g^a$ and $g^b$ with $g^e$. eve knows the shared private key.

many-to-one.

$k$ ephemeral key (else likely key can be found by calculating the gcd)

$c_1 = g^k \mod p$ and $c_2 = g^{ka} \mod p$

$(c_1, c_2)$

decryption:

• $x = c_1^a = g^{ka} \mod p$
• find $x^{-1} \mod p$ (extended euclidean algorithm)

Primitive Root Theorem: dots

Groups §

$G$ set, $*$ binary op

• identity: $e * g = g * e = g$
• inverse: $g^{-1} * g = g * g^{-1} = e$
• associative: $a * (b * c) = (a * b) * c$
• (optional, abelian) commutative: $a * b = b * a$

theorems:

• if $G$ is a finite group, every element of $G$ has finite order.
• if $g^k = e$, $ord(g) \mid k$
• $ord(g) \mid |G| = ord(G)$

Asymptotic Complexity §

$\lim_{n \rightarrow \infty} \frac{f(x)}{g(x)} < \infty \implies f \in O(g)$

Breaking §

Discrete Logarithm Problem for Arbitrary Groups §

Group $G$, $g \in G$, order of $G$ is $N$.

Brute force: compute $g, g^2, \dots, g^{N - 1}$. $O(N)$ (exponential in the number of bits)

Shank’s Algorithm: $O(\sqrt{N} \log N)$

1. $n = 1 + \lfloor\sqrt(N)\rfloor$
2. Create two lists of size $N$
   • baby steps: $e, g, g^2, \dots, g^n$
   • giant steps: $h, hg^{-n}, hg^{-2n}, \dots, hg^{-n^2}$
3. Find a match between the two lists: $g^i = hg^{-jn}$
4. $x = i + jn$ is a solution to $g^x = h$

Pohlig-Hellman Theorem §

If we have an algorithm that takes $O(S_{q^e})$ steps to solve the DLP $g^x = h$ in a group $G$ for any element with $order(g) = q^e$ where $q$ is prime. We can solve

Miller-Rabin Test §

Polynomials §

Fundamental Theorem of Algebra: every polynomial of degree $n$ has exactly $n$ roots (possibly multiple and complex).

Bezout’s Theorem: suppose two polynomials $F(x, y)$ and $G(x, y)$ of degrees $m$ and $n$ respectively have no trivial factors. Then, $\{F(x, y) = 0\} \cap \{G(x, y) = 0\}$ has exactly $mn$ points.

Homogenization: $P(x, y, w) = \sum_{0 \leq i + j \leq n} a_{i, j} x^i y^j w^{n - i - j}$

Dehomogenization: $P(x, y, 1)$

• $w = 0$: points at infinity
• $w = 1$: affine points

Note: $(0, 0, 0)$ is not a point in the projective space.