Shreyas’ Notes

Introduction to Mathematical Cryptography

COMP 323

spring, sophomore year

Historical Ciphers §

Caesar Ciphers §

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

Attack: Try all twenty-six possible keys

Atbash §

Reflection. aza \leftrightarrow z, byb \leftrightarrow y, etc.

Special case of affine cipher.

Encryption and decryption are identical.

Substitution Ciphers §

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

Attack: frequency analysis

Vigenere Cipher §

Keyword.

Security proportional to keyword length.

Attack:

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

IndCo(s)=1n(n1)i=025Fi(Fi1)1n2i=025Fi2\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

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

Modern Cryptography §

Goal: immune to code-breaking without knowing the key

Hard mathematical problems:

Mathematical tools:

Public-key cryptography:

Euclid’s Algorithm §

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

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

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

nn-th prime approx nlnnn \ln n

number of primes lt nn nlnn\frac{n}{\ln n}

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

Modular arithmetic §

a=rmodm    a=mq+ra = r \mod m \implies a = mq + r

Equivalence relation (reflexive, transitive).

a=bmodmc=dmodm    a±c=b±dmodma = b \mod m \wedge c = d \mod m \implies a \pm c = b \pm d \mod m

a=bmodmc=dmodm    ac=bdmodma = b \mod m \wedge c = d \mod m \implies ac = bd \mod m