Advanced Encryption Standard (AES)

AES (Advanced Encryption Standard) is a symmetric encryption algorithm, meaning the same key is used for both encryption and decryption of data. It operates on fixed-size blocks of data, typically 128 bits (16 bytes), but supports key sizes of 128, 192, or 256 bits.

AES encryption involves a series of mathematical transformations on blocks of data. Here's a step-by-step breakdown of the AES process and the math behind each operation.

1. State Representation

AES operates on a 4x4 matrix of bytes (called the "state"). If the input data is 128 bits (16 bytes), it is split into 16-byte blocks that fit into this matrix.

Let’s represent the input block (plaintext) as a 4x4 matrix:

$$\text{State} = \begin{pmatrix} P_{00} & P_{01} & P_{02} & P_{03} \\ P_{10} & P_{11} & P_{12} & P_{13} \\ P_{20} & P_{21} & P_{22} & P_{23} \\ P_{30} & P_{31} & P_{32} & P_{33} \end{pmatrix}$$

Where $P_{ij}$ are the bytes from the plaintext.

2. Key Expansion

The 128-bit key is expanded into multiple round keys through a process called key schedule. Each round key is also a 4x4 matrix of bytes. The key schedule uses the original key and applies a series of transformations, including rotation, substitution using an S-box, and XORing with round constants.

The round key for each round is used in the AddRoundKey step.

3. AddRoundKey

In this step, each byte of the state matrix is XORed with the corresponding byte of the round key.

Let’s represent the round key as a 4x4 matrix:

$$\text{Round Key} = \begin{pmatrix} K_{00} & K_{01} & K_{02} & K_{03} \\ K_{10} & K_{11} & K_{12} & K_{13} \\ K_{20} & K_{21} & K_{22} & K_{23} \\ K_{30} & K_{31} & K_{32} & K_{33} \end{pmatrix}$$

The XOR operation is:

$$\text{State}_{\text{new}} = \text{State} \oplus \text{Round Key}$$

Where $\oplus$ represents bitwise XOR.

4. SubBytes (Non-Linear Substitution)

Each byte in the state matrix is replaced by another byte using a substitution box (S-box). The S-box is a precomputed lookup table based on two mathematical operations:

• Multiplicative inverse over the finite field $GF(2^8)$.
• An affine transformation in $GF(2^8)$.

If a byte in the state is $a$, its substitution $S(a)$ is computed as:

1. Find $a^{-1}$ (the multiplicative inverse of $a$ in $GF(2^8)$).
2. Apply an affine transformation:

$$S(a) = M \cdot a^{-1} \oplus c$$

Where $M$ is a fixed matrix and $c$ is a constant vector.

5. ShiftRows

In this step, the rows of the state matrix are cyclically shifted to the left by different offsets:

• Row 0 is not shifted.
• Row 1 is shifted 1 position to the left.
• Row 2 is shifted 2 positions to the left.
• Row 3 is shifted 3 positions to the left.

This step increases diffusion by rearranging the bytes.

6. MixColumns (Matrix Multiplication in $GF(2^8)$)

In MixColumns, each column of the state matrix is multiplied by a fixed 4x4 matrix over the finite field $GF(2^8)$. This operation ensures that each output byte is a function of all four input bytes in the column.

Let’s represent the state matrix column as a vector:

$$\begin{pmatrix} S_{0,j} \\ S_{1,j} \\ S_{2,j} \\ S_{3,j} \end{pmatrix}$$

Each column is multiplied by the matrix:

$$\begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix}$$

The multiplication is done in $GF(2^8)$, using polynomial arithmetic, which involves multiplying the bytes as polynomials modulo the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$.

The result is the new column:

$$\begin{pmatrix} S'_{0,j} \\ S'_{1,j} \\ S'_{2,j} \\ S'_{3,j} \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} S_{0,j} \\ S_{1,j} \\ S_{2,j} \\ S_{3,j} \end{pmatrix}$$

7. Final Round

The final round is the same as the main rounds, except that it skips the MixColumns step. After completing all the rounds, the result is the ciphertext.

Summary of Mathematical Operations:

• Key Expansion: Involves byte-level operations like rotation, substitution (S-box), and XOR.
• AddRoundKey: Bitwise XOR of the state matrix with the round key.
• SubBytes: Non-linear byte substitution using an S-box based on the multiplicative inverse in $GF(2^8)$.
• ShiftRows: Cyclic shifts of the rows in the state matrix.
• MixColumns: Linear transformation using matrix multiplication in $GF(2^8)$.

These operations together provide strong diffusion and confusion, making AES resistant to most forms of cryptographic attacks.