Math Basics

• Number Theory
  • Integers
  • Modular Arithmetic
  • GCD
• Abstract Algebra
  • Groups
  • Rings
  • Fields
  • Galois Fields
• Probability and Information Theory
  • Probability
  • Entropy

Number Theory

Integers

• $\mathbb{Z}=\{\dots ,-3,-2,-1,0,1,2,3,\dots \}$
• If $a|b$ and $a|c$ then $a|(bx+cy)$ for all $x,y,\in \mathbb{Z}$
• if $a|b$ and $b|a$ then $a=\pm b$

Modular Arithmetic

• $a\equiv c(\mathrm{mod}n)$ and $b\equiv d(\mathrm{mod}n)$ $⟹$ $a+b\equiv c+d(\mathrm{mod}n)$
• equivalence class: set of all integers congruent to $a(\mathrm{mod}n)$
• residue: the remainder between $0$ and $n-1$

GCD

• Euclidean Division Algorithm:

def gcd(a, b):
  if a < b:
    swap(a, b)
  while a > b:
    r = a % b
    if r == 0:
      break
    else:
      a = b
      b = r
  return b

$$\begin{gathered} a=q.m+r \\ \gcd (a,m)=\gcd (a-q.m,m) \\ =\gcd (r,m) \\ =\gcd (m,r) \end{gathered}$$

• Bezout’s Identity: $\exists x,y\in \mathbb{Z}$ such that $ax+by=\gcd (a,b)$
• Extended Euclidean Algorithm: to find value of $x,y$ in identity above

Abstract Algebra

Groups

group $(G,\ast )$ consists of set $G$ and binary operation $\ast$ on $G$ satisfying three axioms

• (associative) $a\ast (b\ast c)=(a\ast b)\ast c\forall a,b,c,\in G$
• (identity) $1\in G$ such that $a\ast 1=1\ast a=a\forall a\in G$
• (inverse) $a^{-1}\in G$ such that $a\ast a^{-1}=a^{-1}\ast a=1\forall a\in G$

Let $G$ be a group s.t. $(ab{)}^i=a^i{b}^i$ for three consecutive integers $i\in \mathbb{N},\forall a,b\in G$. Show that $G$ is Abelian

Sol:

$$\begin{array}{rl}(ab{)}^i& =a^i{b}^i\\ (ab{)}^{i+1}& =a^{i+1}{b}^{i+1}\\ ⟹a^i{b}^{i}ab& =a^{i+1}{b}^{i+1}\\ \text{multiplying with }(a^{i+1}{)}^{-1}& \\ ⟹b^{i}ab& =a{b}^{i+1}\\ ⟹b^{i}a& =a{b}^i\\ & \\ \text{similarly }& \\ & \\ (ab{)}^{i+1}& =a^{i+1}{b}^{i+1}\\ (ab{)}^{i+2}& =a^{i+2}{b}^{i+2}\\ a^{i+1}{b}^{i+1}ab& =a^{i+2}{b}^{i+2}\\ b^{i+1}ab& =a{b}^{i+2}\\ b^{i+1}a& =a{b}^{i+1}\\ & \\ \text{now}& \\ & \\ ba=ab& \end{array}$$

Rings

ring $(R,+,\times )$

• $(R,+)$ is an abelian group
• (associative) operation $\times$ is associative
• (identity) operation $\times$ has an identity
• (distributive) $\times$ is distributive over $+$. $a\times (b+c)=(a\times b)+(a\times c)$

Fields

Field $(F,+,\times )$

• $(F,+)$ is a group
• $(F\setminus \{0\},\times )$ is a group
• distributivity holds

i.e rings with both additive group and multiplicative group

THEOREM

A field with order $m$ only exists if $m$ is a prime power i.e. $m=p^n$ for some positive integer $n$ and prime integer $p$. $p$ is called the characteristic of the finite field

Galois Fields

Prime Fields

These are fields of prime power

e.g. ${\mathbb{Z}}_m$ is the ring $\{\mathbb{Z},+(\mathrm{mod}m),\times (\mathrm{mod}m)\}$. if $m$ is prime then ${\mathbb{Z}}_m$ is a prime field.

e.g. $GF(2)$ is the smallest finite field = $\{0,1\}$

• Arithmetic is addition modulo 2 $\equiv$ XOR
• Multiplication modulo 2 is just logical AND

Extension Fields

In AES the finite field contains 256 elements $=GF(2^8)$ (prime power)

Clearly this is not a prime field so we can’t directly use XOR and AND.

• We will call this an extension field and represent its elements as polynomials with defined polynomial arithmetic
• coefficients of the polynomials belong to $GF(2)$
• the maximum degree of $GF(2^m)$ is $m-1$ for $m$ coefficients

Addition and Subtraction in $GF(2^m)$

bitwise XOR

• $(x^7+x^6+x^4+1)+(x^4+x^2+1)=(x^7+x^6+x^2)$

NOTE

subtraction of two polynomials gives the same result as addition

Multiplication in $GF(2^m)$

• standard polynomial multiplication
• coefficients mod 2
• reduce since degree probably increased
  • divide by irreducible polynomial (prime number equivalent of a polynomial)

$$C(x)\equiv A(x)\cdot B(x)\mathrm{mod}P(x)$$

where $P(x)$ is an irreducible polynomial

NOTE

for AES the irreducible polynomial $P(x)=x^8+x^4+x^3+x+1$ is used

Inversion in $GF(2^m)$

The main algorithm is the extended euclidean algorithm. AES uses LUTs

Information Theory

Surprise Function

$s(x)={\log }_2(\frac{1}{\mathrm{Pr}[X==x]})$

• $s(x)$ is the information content of a single message
• you want to be more surprised if a “rare” symbol is observed
• logarithm because information should be additive

Shannon Entropy: average information content

$H(x)={\sum }_{x\in X}\mathrm{Pr}[X==x]\cdot {\log }_2\frac{1}{\mathrm{Pr}[X==x]}$

• $0\le H(x)\le {\log }_{2}n$
• sub-additivity: $H(X,Y)\le H(X)+H(Y)$
• chain-rule: $H(X,Y)=H(X|Y)+H(Y)=H(Y|X)+H(X)$
  • conditioning can only decrease uncertainty