AES encryption layers
Byte substitution (SB)
The input is a byte 𝑏. For any byte 𝑏, we will denote the bits as 𝑏 = 𝑏7𝑏6𝑏5𝑏4𝑏3𝑏2𝑏1𝑏0. That is, we number the bits from 7 to 0 starting with the most significant bit.
1. Find the multiplicative inverse of 𝑏 in the Galois
field 𝐺𝐹(28) and call it 𝑦 = 𝑏−1. (We will discuss arithmetic in this field later but think of this as similar to the group Z𝑛 where we defined addition and multiplication. As there, the definition of addition will be easy. The definition of multiplication will be strange. But defining multiplication will allow us to define the inverse of it.)
2. Consider the bits of 𝑦 above as being in a column 𝑦7
𝑦6
𝑦5
𝑦
𝑦2 𝑦1
[𝑦0]
add a fixed vector:
vector:
4 . Left-multiply that with a fixed 8×8 matrix and 𝑦3
10001111 𝑦7 11000111 𝑦6
11100011
1 1 1 1 0 0 0 1 𝑦4
11111000 𝑦3
01111100 𝑦2
1
𝑧7
𝑧6 𝑧5
= 𝑧4 𝑧3
𝑧2 𝑧1
00111110 𝑦1
[0 0 0 1 1 1 1 1][𝑦0] [0] [𝑧0]
So the byte 𝑧 is the output of this SB step. Note that the matrix is the same sequence of bits in each row right- shifted circularly row-by-row. This is to promote diffusion. Note also that multiplication and addition is bit-wise and done modulo 2. This is equivalent to using bit-wise XOR for addition and bit-wise AND for multiplication.
Shift rows (SR)
Left-shift circularly each of the rows of the state table by an amount equal to the row indices: 0,1,2,3.
Mix columns (MC)
Left-multiply each column with a fixed matrix as follows:
0𝑥02 0𝑥03 0𝑥01 0𝑥01 𝑐0 𝑑0 [0𝑥01 0𝑥02 0𝑥03 0𝑥01] [𝑐1 ] = [𝑑1 ] 0𝑥01 0𝑥01 0𝑥02 0𝑥03 𝑐2 𝑑2 0𝑥03 0𝑥01 0𝑥01 0𝑥02 𝑐4 𝑑3
As before, the value 𝑑𝑖 is the dot product of row 𝑖 with the 𝑐- vector. For example:
1 𝑦5 0
+ 0 0
1 1
𝑑0 =0𝑥02⋅𝑐0 ⊕ 0𝑥03⋅𝑐1 ⊕0𝑥01⋅𝑐2 ⊕0𝑥01⋅𝑐3
The arithmetic is done with addition and multiplication operations as defined in 𝐺𝐹(28). As we’ll see, addition in that field is bit-wise XOR. The definition of multiplication is more involved and we’ll discuss it later.
This is another diffusion stage, this time among the values in a column.
Add round key (ARK)
This is simply bit-wise XOR between the 128 bits of the state in column-major order and the 128 bits of the sub-key for each round.