AES = Advanced Encryption Standard

AES is a block cipher with a block length of 128 bits

Why 128?

There's a tradeoff:

Longer block size: More secure, slower if too big, more overhead for small messages

Shorter block size: Less secure, faster, less overhead for wasted space

The block size of 128 is small enough that AES can be implemented as machine instruction.

Rounds

AES takes key length as a parameter.

Keys can be: 128, 192, or 256 bits.

The number of rounds depends on the key length:

  • $|k| = 128 \rightarrow 10$ rounds
  • $|k| = 192 \rightarrow 12$ rounds
  • $|k| = 256 \rightarrow 14$ rounds

Longer key modes are more secure both because of longer key and more rounds.

Key whitening

Unlike DES, AES uses a technique called key whitening.

This fancy term means:

  1. A subkey gets XORed with the plaintext before the AES rounds begin
  2. A different subkey gets XORed with the plaintext after all rounds are over

This does not affect the difficulty of a brute force attack.

But it does make other attacks harder, because it obscures the internal state of the algorithm during the rounds.

One round

One round of AES consists of four "layers"

round1

Unlike DES which operated on bits, AES operates on bytes. This is convenient for software implementations.

Design Strategy

Unlike DES, AES does not have a Feistel network structure.

But like DES, each round is basically a composition of a permutation and a substitution.

SubBytes obviously substitutes new bytes for old bytes

ShiftRows and MixColumns permute the order of the bytes.

AddRoundKey obscures the internal state of the algorithm by mixing in secret bits.

Sbox magic

Sometimes the SubBytes layer of AES is referred to as the S-box.

Just as S-box design is the "secret sauce" in DES, the SubBytes layer is the most important part of AES.

Some differences from DES:

  1. There is only one S-box which is applied once per layer to the entire 16 byte = 128 bit state. Each byte is replaced with another byte which is looked up in a fixed table.

  2. The S-box is one-to-one (i.e. bijective). In other words you can invert it. The DES S-boxes took 6 bits to 4 bits and so were not invertable.

In DES the function $f$ was conceptualized as a PRNG and wasn't inverted during decryption (just reapplied).

But in AES every layer is invertable.

Non-linearity

Just as in DES, the AES S-box is the only element that introduces non-linearity.

That means that for no bytes $b_1$ and $b_2$ is it the case that

$$S(b_1 \oplus b_2) = S(b_1) \oplus S(b_2).$$

The S-box also has no fixed points, meaning there are no bytes $b$ such that

$$S(b) = b.$$

Nonlinearity stops the cipher from being "solved" using techniques from linear algebra.

SubBytes design

We now take a rather large detour into the design of the S-box.

While the S-box is basically just a subsitution table, the mathematics that motivated its creation is beautiful and interesting.

The S-box operates by regarding each byte as a polynomial mod 2.

These polynomials are in an abstract sense "like numbers": They can be added, subtracted, multiplied and inverted.

We call things like this "fields".

Abstracted thoughts...

We now give some rather airy definitions.

We introduce groups first.

A mathematical group is a set $G$ together with an operation $\circ$ so that $(G,\circ)$ behaves roughly like $(\mathbb{Z},+)$ or $(\mathbb{R}^+,\times)$.

Groups

A group is a set $G$ together with an operation (denoted by $\circ$) on pairs of elements of $G$. A group must satisfy these properties:

  • Closure: $\forall g_1 \in G, \forall g_2 \in G$ we have $g_1 \circ g_2 \in G$

Examples:

The product of any two integers is an integer.

The product of any two complex numbers is a complex number.

The product of any two polynomials is a polynomial.

The composition of any two continuous functions is a continuous function

The product of any two matrixes is a matrix.

Groups

A group is a set $G$ together with an operation (denoted by $\circ$) on pairs of elements of $G$. A group must satisfy these properties:

  • Associativity: $\forall g_1 \in G, \forall g_2 \in G, \forall g_3 \in G$ we have $(g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) $.

Examples:

Multiplication is associative: $(2\cdot 3) \cdot 4 = 2 \cdot (3 \cdot 4)$.

Addition is associative: $(2 + 3) + 4 = 2 + (3 + 4)$.

Function composition is associative

Division is not associative: $(2 / 3) / 4 = \frac{1}{6} \neq 2 / (3 / 4) = \frac{8}{3}$.

Subtraction is not associative: $(2 - 3) - 4 = -5 \neq 2 - (3 - 4) = 3$.

Groups

A group is a set $G$ together with an operation (denoted by $\circ$) on pairs of elements of $G$. A group must satisfy these properties:

  • Identity element: $\exists e \in G \forall g \in G$ we have $e \circ g = g$ and $g \circ e = g$.

Sometimes this is also called the "neutral" element and might be denoted as 0 or 1 depending on the group.

Examples:

Adding zero does nothing

Multiplying by one does nothing

Composing with $f(x)=x$ does nothing

Groups

A group is a set $G$ together with an operation (denoted by $\circ$) on pairs of elements of $G$. A group must satisfy these properties:

  • Inverses: $\forall g_1 \in G, \exists g_2 \in G$ such that $g_1 \circ g_2 = e$ and $g_2 \circ g_1 = e$.

Examples:

$5 + (-5) = 0$

$5 \cdot 5^{-1} = 1$

$f(f^{-1}(x)) = f^{-1}(f(x)) = x$

Exercise: Verify that $(\mathbb{Z}_3, +)$ is a group

$\mathbb{Z}_3 = \{0,1,2\}$, addition is modulo 3

  • Addition table (I'll write this on the board)
  • Closure (inspection of table)
  • Associativity (inherited from $(\mathbb{Z},+)$)
  • Identity: $0=e$.
  • Inverses:

$-0 \equiv 0 \mod 3$

$-1 \equiv 3-1 \equiv 2 \mod 3$

$-2 \equiv 3-2 \equiv 1 \mod 3$

Excercise: Verify that $(\mathbb{Z}_5^*,\times)$ is a group.

$\mathbb{Z}_5^* = \{1,2,3,4\}$, multiplication is modulo 5

  • Multiplication table (I'll write this on the board)
  • Closure (inspection of table)
  • Associativity (inherited from $(\mathbb{Z},\times)$)
  • Identity: 1 = e
  • Inverses:

$1^{-1} \equiv 1 \mod 5$

$2^{-1} \equiv 3 \mod 5$

$3^{-1} \equiv 2 \mod 5$

$4^{-1} \equiv 4 \mod 5$

Rings and Fields

Groups are things that behave like $(\mathbb{Z},+)$.

Rings are things that behave like $(\mathbb{Z},+,\times)$.

There are two operations rather than one.

The two operations interact with each other just like ordinary + and $\times$:

$$a(b+c) = ab + ac$$

You can "distribute in" and "factor out".

Note that $(\mathbb{Z},+)$ is a group, but $(\mathbb{Z},\times)$ is not (no inverses).

Example of a ring

Let $\mathbb{Z}[x]$ denote all polynomials in $x$ with coefficients in $\mathbb{Z}$.

Sample elements: $0,1, x+1, 3x-1,x^2+2x-1,\ldots$.

In this ring $+$ is much like regular $+$ and $\times$ is like ordinary $\times$.

Note that $(\mathbb{Z}[x],+)$ is a group, but $(\mathbb{Z}[x],\times)$ is not. (No inverses)

Fields

A field is a special kind of ring in which you get additive inverses and multiplicative inverses for all nonzero elements. In other words:

A field is a set $F$ together with operations $+$ and $\times$ such that all of the following are true:

  • $(F,+)$ is a group. (Let the identity be denoted 0.)
  • $(F-\{0\},\times)$ is a group. (Let the identity be denoted 1.)
  • For all $a,b,c \in F$, we have $a(b+c) = ab + ac$.

Example of a field

These are all fields:

  • $(\mathbb{Q},+,\times)$
  • $(\mathbb{R},+,\times)$
  • $(\mathbb{C},+,\times)$

What about finite fields?

Exercise: Verify that $(\mathbb{Z}_5,+,\times)$ is a field.

  • $(\mathbb{Z}_5,+)$ is a group with addition mod 5.
  • We showed above that $(\mathbb{Z}_5^*,\times)$ is a group with multiplication mod 5.
  • Multiplication distributes over addition (since it does in $\mathbb{Z}$)

Exercise: Show that $(\mathbb{Z}_4,+,\times)$ is not a field

What goes wrong?

  • $(\mathbb{Z}_4,+)$ is a group.
  • $(\mathbb{Z}_4 - \{0\},\times)$ is not a group.

Why is $(\mathbb{Z}_4 - \{0\},\times)$ is not a group?

$\mathbb{Z}_4 - \{0\} = \{1,2,3\}$.

But this is not closed under multiplication mod 4 (since $2 \times 2 \equiv 0\mod 4$).

Also 2 and 3 do not have inverses.

Prime numbers....

Fact: $(\mathbb{Z}_n-\{0\},\times)$ is a group if and only if $n$ is prime.

Proof: First show that $(\mathbb{Z}_n-\{0\},\times)$ is not a group if $n$ is composite. If $n = ab$ for $a,b \in \mathbb{Z}_n-\{0\}$ then $\mathbb{Z}_n-\{0\}$ is not closed under multiplication mod $n$. Since it is not closed, it is not a group.

Now show that $(\mathbb{Z}_n-\{0\},\times)$ is a group if $n$ is prime. It suffices to show that inverses exist. The inverse of any element can be found using the extended euclidean algorithm. We will discuss this in detail later.

Examples of finite fields

We now have infinitely many examples of finite fields:

  • $(\mathbb{Z}_p,+,\times)$ such that $p$ is a prime number.

Are these all the finite fields?

Not quite...

The order of an algebraic object

The order of a group, ring, or field is the number of elements.

The order of $(\mathbb{Z},+)$ is $\infty$.

The order of $(\mathbb{Z}_5,+)$ is $5$ because the elements are $\{0,1,2,3,4\}$.

The order of $(\mathbb{Z}_5^*,\times)$ is $4$ because the elements are $\{1,2,3,4\}$.

The order of $(\mathbb{Z}_5,+,\times)$ is 5.

Theorem

For every prime power $q$ there are fields of order $q$ and they are all the same up to isomorphism.

There are no other finite fields.

Definition

The characteristic of a finite field $F$ is the prime $p$ such that $|F|=p^k$.

The unique field of order $p^k$ for prime $p$ is denoted $GF(p^k)$.

Wait...what?

So there are fields of order $2,3,5,7,11,\ldots$

and there are fields of order $2^2,2^3,2^4,\ldots$

and there are fields of order $3^2,3^3,3^4,\ldots$

etc.

And once you know the order of a field you know everything about it (each one is basically unique).

There are no other finite fields.

So what are...

What are these fields?

The fields of prime order are just $(\mathbb{Z}_p,+,\times)$ for primes $p$.

The fields of order $p^k$ for $p$ prime and $k>1$ are a little more complicated.

They are not $(\mathbb{Z}_{p^k},+,\times)$ because these are rings not fields.

In [0]: