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 §


Security proportional to keyword length.


  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)lcm(a,b)=ab\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

Chinese Remainder Theorem §


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

Fermat’s Little Theorem §

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

np11modpn^{p - 1} \equiv 1 \mod p

npnmodpn^p \equiv n \mod p

npn0modpn^p - n \equiv 0 \mod p


encryption: memodpqm^e \mod pq where mm is the message and 0<m<pq0 < m < pq

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

Diffie-Hellman §

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

private keys: aa, bb

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

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

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




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

c1=gkmodpc_1 = g^k \mod p and c2=gkamodpc_2 = g^{ka} \mod p

(c1,c2)(c_1, c_2)


Primitive Root Theorem: dots

Groups §

GG set, * binary op


Asymptotic Complexity §

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

Breaking §

Discrete Logarithm Problem for Arbitrary Groups §

Group GG, gGg \in G, order of GG is NN.

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

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

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

Pohlig-Hellman Theorem §

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

Miller-Rabin Test §

Polynomials §

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

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

Homogenization: P(x,y,w)=0i+jnai,jxiyjwnijP(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)P(x, y, 1)

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