AES MixColumns() Procedure Algorithm

A detailed description of the MixColumns() procedure algorithm is provided. The MixColumns() procedure performs a matrix multiplication of a given 'state' with a static matrix. The MixColumns() procedure is used in the AES encryption process.

The MixColumns() - The MixColumns() procedure performs a matrix multiplication of a given 'state' with a static matrix. The MixColumns() procedure is key procedure used in the AES encryption process.

Here is the algorithm that the MixColumns() procedure should follow:

```Procedure Name:
MixColumns(state)

Input:
state: A 4x4 byte array

Algorithm:
|     |   |0x02 0x03 0x01 0x01|   |     |
|     |   |0x01 0x02 0x03 0x01|   |     |
|state| = |0x01 0x01 0x02 0x03| ● |state|
|     |   |0x03 0x01 0x01 0x02|   |     |

Note that "●" represents a matrix multiplication defined as:
|a1|   |0x02 0x03 0x01 0x01|   |b1|
|a2|   |0x01 0x02 0x03 0x01|   |b2|
|a3| = |0x01 0x01 0x02 0x03| ● |b3|
|a4|   |0x03 0x01 0x01 0x02|   |b4|

is equivalent to:
a1 = 0x02●b1 ⊕ 0x03●b2 ⊕ 0x01●b3 ⊕ 0x01●b4
a2 = 0x01●b1 ⊕ 0x02●b2 ⊕ 0x03●b3 ⊕ 0x01●b4
a3 = 0x01●b1 ⊕ 0x01●b2 ⊕ 0x02●b3 ⊕ 0x03●b4
a4 = 0x03●b1 ⊕ 0x01●b2 ⊕ 0x01●b3 ⊕ 0x02●b4

where "⊕" is the binary XOR operation,
and "●" is Rijndael's GF (Galois Field) multiplication.
```

Rijndael's GF multiplication used above can be defined as:

```If we express bytes "a" and "b" in a polynomial form:
a = 2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0
b = 2^7*b7⊕2^6*b6⊕2^5*b5⊕2^4*b4⊕2^3*b3⊕2^2*b2⊕2^1*b1⊕2^0*b0
then:
c = a ● b =
((2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^7*b7
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^6*b6
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^5*b5
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^4*b4
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^3*b3
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^2*b2
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^1*b1
⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^0*b0
) ⓜ 0x011b
```

Now we have only one last operation to understand, the GF modulo, "", which can be defined as:

```If we say:
c = a ⓜ b
then should have:
a = b●d ⊕ c
c < b
```

Here is an example of Rijndael's GF multiplication:

```   0x57 ● 0x83
= (2^6 ⊕ 2^4 ⊕ 2^2 ⊕ 2^1 ⊕ 2^0) ● (2^7 ⊕ 2^1 ⊕ 2^0)
= ((2^13 ⊕ 2^11 ⊕ 2^9 ⊕ 2^8 ⊕ 2^7)
⊕  (2^7 ⊕ 2^5 ⊕ 2^3 ⊕ 2^2 ⊕ 2^1)
⊕  (2^6 ⊕ 2^4 ⊕ 2^2 ⊕ 2^1 ⊕ 2^0)
) ⓜ 0x011b
= ((2^13 ⊕ 2^11 ⊕ 2^9 ⊕ 2^8 ⊕ 2^6 ⊕ 2^5 ⊕ 2^4 ⊕ 2^3 ⊕ 2^0)
) ⓜ 0x011b
= 0x2b79 ⓜ 0x011b
= 0xc1

The last step can approved by:
0x2b79
= 0x011b●0x28 ⊕ 0xc1
= (2^8 ⊕ 2^4 ⊕ 2^3 ⊕ 2^1 ⊕ 2^0)●(2^5 ⊕ 2^3) ⊕ (2^7 ⊕ 2^6 ⊕ 2^1)
= (2^13 ⊕ 2^9 ⊕ 2^8 ⊕ 2^6 ⊕ 2^5) ⊕ (2^11 ⊕ 2^7 ⊕ 2^6 ⊕ 2^4 ⊕ 2^3)
⊕ (2^7 ⊕ 2^6 ⊕ 2^0)
= 2^13 ⊕ 2^11 ⊕ 2^9 ⊕ 2^8 ⊕ 2^6 ⊕ 2^5 ⊕ 2^4 ⊕ 2^3 ⊕ 2^0
= 0x2b79
```

Here is a demonstration on how to calculate 0x2b79 0x011b manually in binary mode:

```Express the dividend in binary format:
0x2b79 = 0b10101101111001

Express the divisor in binary format:
0x011b = 0b100011011

Do the manual calculation:
101000 <- quotient
divisor  ----------------
100011011 | 10101101111001 <- dividend
⊕ 100011011
----------------
100000011001
⊕ 100011011
--------------
11000001 <- remainder

Convert the remainder to hexadecimal format:
0b11000001 = 0xc1

We get the result:
0x2b79 ⓜ 0x011b = 0xc1
```

Table of Contents