MixColumns

MixColumns is a transformation used in the Advanced Encryption Standard (AES) as part of the encryption and decryption rounds. It operates on the 4x4 byte state by treating each column as a vector of four bytes and applying the same linear transformation to every column, which spreads information within a column to achieve diffusion.

In encryption, each column of the state is multiplied by a fixed 4x4 matrix over the finite field GF(2^8). The matrix is:

[02 03 01 01;

01 02 03 01;

01 01 02 03;

03 01 01 02]

Here 02, 03, 01, and similar entries are elements of GF(2^8). Multiplication by 02 corresponds to a left-shift with a conditional xor by 0x1b (the xtime operation); multiplication by 03 is xtime(x) xor x.

For decryption, the inverse transformation uses the inverse matrix:

[14 11 13 09;

09 14 11 13;

13 09 14 11;

11 13 09 14]

(14, 11, 13, 9 are hexadecimal 0e, 0b, 0d, 09, respectively). InvMixColumns is applied in the decryption rounds except the final round, depending on the AES round structure.

MixColumns is designed to be linear and invertible, and its computation can be performed independently on each column, enabling high parallelism in both software and hardware implementations. It is a core component of AES diffusion, complementing SubBytes and ShiftRows to ensure changes in plaintext or ciphertext propagate across the state.