AES - the math behind it

AES encryption math

All the internal operations of AES are based on finite fields.

The field $GF(2^8)$ is the one that's most important for AES, since that has exactly the number of bytes in it.

The irreducible polynomial used for multiplication is defined in the standard, and is

$$p(x) = x^8 + x^4 + x^3 + x + 1$$

steps of AES

• Initial key whitening: The plaintext is added with the key.

• Then the following steps are looped through, for 9, 11, or 13 rounds:
  • SubBytes: We use the S-Box for substituting each byte with a different one
  • ShiftRows: Transposition where the last three rows are shifted cyclically by a fixed number of steps.
  • MixColumns: You multiply the data matrix by another one to mix the columns up based on a combination of other columns.
  • AddRoundKey: Add the round key to the data (again, galois field addition)

In the last round there's no MixColumns. The individual steps proceed as follows:

SBox

The SBox is a 16 x 16 matrix where each bytes first 4 bits are used for the row and the last 4 bytes are used for the column. The S-Box is actually two mathematical steps, the multiplicative inverse of the byte in the field, and then an affine transformation on the resulting byte treated as a bit vector. The steps are not very relevant, since this can be precomputed and stored, and thus the result is called the S-Box or the substitution box. What the steps do tell, however, is the fact that this has very strong non-identity properties. There are no fixed points and correlation is low later on.

Shift Rows

The 0th row in the 4x4 data matrix is not shifted at all, the first is shifted by one column to the left (wrapping around), second by two, and third by 3.

Mix Columns

We multiply each column by a specific matrix, which has [0x2, 0x3, 0x1, 0x1] and in the subsequent rows is shifted one to the right. The matrix multiplication results in each element being a sum of products, the sum and product here being in the galois field.

AES Key scheduling

This is for AES-128. The other key sizes follow roughly the same mechanism.

First, the 128-bit key is split into 4 32-bit keys. Then, the keys are computed as follows (from 0 to 10):

$$W[4i] = W[4(i - 1)] + g(W[4i - 1])$$

$$W[4i + j] = W[4i + j - 1] + W[4(i - 1) + j]$$

$i$ belongs to 1 to 10, and $j$ belongs to 1 to 3. The initial 4 keys are obtained from splitting the master key, and are used for key-whitening.

$g$ is a messed up function that takes in 4 input bytes, and gives 4 output bytes. It takes the input, rotates it by a byte, performs S-Box, then adds a specific round coefficient.