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.
AES takes key length as a parameter.
Keys can be: 128, 192, or 256 bits.
The number of rounds depends on the key length:
Longer key modes are more secure both because of longer key and more rounds.
Unlike DES, AES uses a technique called key whitening.
This fancy term means:
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 of AES consists of four "layers"
Unlike DES which operated on bits, AES operates on bytes. This is convenient for software implementations.
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.
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:
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.
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.
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.
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".
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)$.
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:
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.
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:
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$.
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:
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
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:
Examples:
$5 + (-5) = 0$
$5 \cdot 5^{-1} = 1$
$f(f^{-1}(x)) = f^{-1}(f(x)) = x$
$\mathbb{Z}_3 = \{0,1,2\}$, addition is modulo 3
$-0 \equiv 0 \mod 3$
$-1 \equiv 3-1 \equiv 2 \mod 3$
$-2 \equiv 3-2 \equiv 1 \mod 3$
$\mathbb{Z}_5^* = \{1,2,3,4\}$, multiplication is modulo 5
$1^{-1} \equiv 1 \mod 5$
$2^{-1} \equiv 3 \mod 5$
$3^{-1} \equiv 2 \mod 5$
$4^{-1} \equiv 4 \mod 5$
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).
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)
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:
These are all fields:
What about finite fields?
What goes wrong?
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.
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.
We now have infinitely many examples of finite fields:
Are these all the finite fields?
Not quite...
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.
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.
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)$.
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.
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.