AES operates on a 128-bit block, but almost nothing in its specification is written in terms of 128-bit words. The block is treated as a four-by-four matrix of bytes, and every operation except the key addition is defined on that matrix — a byte substitution applied cell by cell, a rotation applied row by row, a linear transform applied column by column. Understanding the cipher means understanding the indexing, because the indexing is where most implementation bugs live.

Filling the matrix from a byte string

The input is a sequence of 16 bytes, conventionally numbered $a_0$ through $a_{15}$ in the order they appear on the wire. The state is filled column by column:

column 0	column 1	column 2	column 3
$a_0$	$a_4$	$a_8$	$a_{12}$
$a_1$	$a_5$	$a_9$	$a_{13}$
$a_2$	$a_6$	$a_{10}$	$a_{14}$
$a_3$	$a_7$	$a_{11}$	$a_{15}$

so that state cell $(r, c)$ holds byte $a_{4c + r}$. This column-major convention is the single most common source of interoperability defects. An implementation that fills row-major produces a state that is the transpose of the specified one; encryption and decryption remain mutually consistent, so the code round-trips its own output perfectly and only fails against another implementation. Test vectors catch it immediately; self-consistency never will.

The four columns are also called words, each 32 bits. On a big-endian machine a column loaded as a 32-bit word has its first byte in the most significant position; on a little-endian machine the same memory bytes assemble into a word with the byte order reversed. Implementations that operate on 32-bit words therefore have to fix an explicit byte order rather than rely on the platform’s.

ShiftRows moves each row a different distance

ShiftRows rotates row $r$ left by $r$ positions, leaving row 0 in place, moving row 1 by one, row 2 by two, and row 3 by three. It is the only operation in the round that mixes bytes across columns, and the choice of offsets is deliberate: four distinct offsets for four rows means that after the shift, every column contains exactly one byte from each original column.

The operation is byte-oriented and costs almost nothing, but it has an important structural consequence. Combined with MixColumns, a single byte change affects all four columns after two rounds. With a uniform shift of one position for every row, the four bytes of a column would all move to the same column and diffusion would collapse; the distinct offsets are what guarantee that the four bytes separate.

In a 32-bit word implementation, ShiftRows is a rotation of the whole word plus a byte permutation. Since each column is a word, the shift amounts differ per byte position within the word, so the operation is expressed as a rotation by a different count for each of the four words, followed by a fixed rearrangement. Implementations that keep the state in a single 128-bit vector use a byte shuffle instruction instead, which expresses all sixteen movements in one opcode on architectures that provide one.

MixColumns as multiplication in a finite field

MixColumns treats each column as a polynomial of degree below 4 over $\mathrm{GF}(2^8)$ and multiplies it by the fixed polynomial

$$a(x) = 3x^3 + x^2 + x + 2$$

modulo $x^4 + 1$. Written as a matrix acting on the column’s four bytes, the transform is a circulant matrix whose rows are 2, 3, 1, 1 shifted cyclically:

$$ \begin{bmatrix} b_0 \ b_1 \ b_2 \ b_3 \end{bmatrix}

\begin{bmatrix} 2 & 3 & 1 & 1 \ 1 & 2 & 3 & 1 \ 1 & 1 & 2 & 3 \ 3 & 1 & 1 & 2 \end{bmatrix} \begin{bmatrix} a_0 \ a_1 \ a_2 \ a_3 \end{bmatrix} $$

Addition in $\mathrm{GF}(2^8)$ is XOR. Multiplication by 2 is a left shift with a conditional reduction by the AES field polynomial $x^8 + x^4 + x^3 + x + 1$, conventionally written as 0x1b; multiplication by 3 is that result XORed with the original byte. In code the whole column transform is four shifts, four XORs, and a handful of conditional masks:

static uint8_t xtime(uint8_t x)
{
    /* Multiply by x in GF(2^8) mod x^8+x^4+x^3+x+1. */
    return (uint8_t)((x << 1) ^ ((x >> 7) * 0x1b));
}

static void mix_column(uint8_t *c)
{
    uint8_t t = c[0] ^ c[1] ^ c[2] ^ c[3];
    uint8_t u = c[0];
    c[0] ^= t ^ xtime(c[0] ^ c[1]);
    c[1] ^= t ^ xtime(c[1] ^ c[2]);
    c[2] ^= t ^ xtime(c[2] ^ c[3]);
    c[3] ^= t ^ xtime(c[3] ^ u);
}

The trick in that function is that the XOR of the whole column is invariant under the transform’s linear part, so each output byte can be computed as the input byte XORed with the column sum XORed with one xtime. That replaces four full matrix rows with a common subexpression.

The polynomial was chosen for two properties. It is invertible modulo $x^4+1$, which is required because decryption must undo the step; its inverse has coefficients 14, 11, 13, 9 and is a denser matrix, so decryption is measurably more expensive than encryption in software. And it has a branch number of 5: the sum of the number of nonzero input bytes and the number of nonzero output bytes is at least 5 for any nonzero input. A column of one nonzero byte produces three nonzero output bytes, and a column of four nonzero bytes produces at least one. The bound is tight and it is what limits a differential characteristic’s weight per round.

The branch number of MixColumns and the row offsets of ShiftRows are two halves of one argument about how fast a difference spreads. Diffusion and branch numbers works through the counting that produces the four-round bound.

Round structure and key addition

A round is SubBytes, ShiftRows, MixColumns, then AddRoundKey, with the byte substitution applied cell by cell through the S-box. The final round omits MixColumns, a detail that looks arbitrary and is not: without the omission, the last round’s linear layer could be commuted past the final key addition by an attacker, who would then face a cipher whose final operation is a key XOR of a linearly transformed state. Removing it makes the last operation a nonlinear substitution on the state after key addition, which is harder to peel off. Decryption mirrors this: the inverse cipher applies InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns in the corresponding order, and the missing final MixColumns becomes a missing initial InvMixColumns.

Key addition XORs the 16-byte round key into the state, column by column. Because XOR is its own inverse and commutes with nothing else in the round, the key schedule must supply a distinct key per round; reusing one would make the cipher trivially vulnerable to a slide-style argument, since two identical rounds in sequence cancel. How those round keys are derived, and why the derivation must itself be nonlinear, is the subject of key schedule design.

Sizes beyond 128 bits

The same structure extends to 192- and 256-bit keys, but not to larger blocks. Rijndael as submitted to the AES competition supported block sizes of 128, 192, and 256 bits, with the state laid out as a four-row matrix whose column count equals the block size divided by 32. AES fixed the block at 128 bits and kept only the key-size variation, so the number of columns is always 4 and the number of rounds is 10, 12, or 14 for 128-, 192-, and 256-bit keys. The row shift offsets for wider states differ from the four-column case; implementations that hard-code the offsets 0, 1, 2, 3 are correct for AES and wrong for Rijndael with a wider block.

That restriction was a deliberate simplification rather than a limitation of the design. Fixing the block size removed a parameter that implementations would otherwise have had to handle, and it removed a class of configuration errors in which two peers agree on a key but not on a block width. It also fixed the width of every table and every word operation, which let implementers write code that assumes sixteen bytes throughout rather than carrying a length variable through every round.

Where the layout surfaces at an API boundary

The column-major mapping matters wherever a flat buffer meets the cipher. A common interface takes a pointer to sixteen input bytes, a pointer to sixteen output bytes, and a key schedule; the mapping from that buffer to the state is fixed by the specification. Implementations that operate on 32-bit words read four bytes at a time, and the choice between a big-endian and a little-endian load changes what the round function sees.

The convention that has settled is a big-endian word load, so the first byte of a column occupies the most significant position of the word. On a little-endian processor that load is a byte swap costing either a dedicated instruction or three shifts and masks; on a big-endian processor it is free. Implementations on little-endian machines often define their own internal state order, run all rounds in that order, and translate only at load and store. Outputs are identical because the round function is a fixed sequence of byte operations applied consistently in whatever order the implementation chose.

The trap is mixing conventions. A key schedule produced under one ordering and consumed under another yields a cipher that round-trips against itself and fails against every other implementation, and because both halves are self-consistent, a test suite that checks only internal consistency passes. Nothing in the round’s algebra detects the mismatch; only a known-answer test does.

The final round and inverse-cipher symmetry

Omitting MixColumns from the final round has a second consequence beyond the attack argument: it makes the inverse cipher’s first round structurally different from its intermediate rounds. A decryption implementation therefore has an initial InvMixColumns, a loop of the standard inverse round, and a final round without InvMixColumns. The equivalent inverse cipher rearranges the operations so that the asymmetry disappears, at the cost of transforming the decryption round keys with InvMixColumns. Both formulations produce identical results; the choice is between a distinctive first round and a more expensive key setup.