Advantage of $\operatorname{GF}(2^8)$ over $\mathbb Z/2^8\mathbb Z$ in AES/Rijndael

Question

The Galois Field is used in the mixColumns step of the Rijndael-Algorithm. Over $\operatorname{GF}(2^8)$ (irreducible polynomial: $x^8 + x^4 + x^3 + x + 1$), the first value of a matrix multiplication (all numbers are hex numbers) would be:

$$\begin{bmatrix} \mathtt{1e}\\\mathtt{27}\\\mathtt{98}\\\mathtt{e5}\end{bmatrix}\cdot\begin{bmatrix} 2 & 3 & 1 & 1\\...&...&...&...\end{bmatrix} = \begin{bmatrix} \mathtt{28}\\...\\...\\...\end{bmatrix}$$

If I calculate the same matrix multiplication in the realm of natural numbers the result is:

$$(\mathtt{1e}\cdot2)+(\mathtt{27}\cdot3)+\mathtt{98}+\mathtt{e5} = \mathtt{22e}$$

Okay, $\mathtt{22e}$ is bigger than $2^8-1$, but we can just take $\mathtt{22e} \bmod 2^8 = \mathtt{2e}$ and the result would be well within the boundary of an byte.

As a non-mathematican I wonder what's the advantage of the calculating in the $\operatorname{GF}(2^8)$ over calculating with the natural numbers modulo $2^8$, because both methods seem to be feasible. I have two ideas in my head but did not find any confirmation nor disprove. Is it about efficiency because the $\operatorname{GF}(2^8)$ is perfectly aligned to the byte architecture of a computer? Or does the $\operatorname{GF}(2^8)$ provide better diffusion than the calculation via natural numbers? Or is it something else?

Answer 1

One important property of the mixColumns step is that it is Maximum Distance Separable (MDS). That is, if $M$ is our multiplication matrix, if you take any two distinct input vectors $V$ and $V'$, and compute $M \cdot V$ and $M \cdot V'$, the total number of bytes distinct in $V$ and $V'$ plus the total number of bytes distinct in $M \cdot V$ and $M \cdot V'$ will always be at least 5 (the dimension of the matrix $M$ plus 1).

It turns out that this is an important property used in the proof of security of AES against differential and linear cryptanalysis.

Now, if you replace the $GF(2^8)$ multiplications within the MDS matrix with $Z/256$ multiplications, it turns out that you cannot have the MDS property; neither the matrix used within AES, nor any other matrix has the MDS property.

This is fairly easy to show; to start with, consider $V = \{0,0,0,0\}$ and $V'=\{128,0,0,0\}$; these obviously differ in 1 bytes, and so for the MDS property to hold, all for values of $M \cdot V$ and $M \cdot V'$ must differ. However, if lsbit of $M[0,0]$ is 0, then the first byte of $M \cdot V$ and $M \cdot V'$ will be the same, and hence MDS will not hold, and hence the lsbit of $M[0,0]$ must be a 1. Along the same line, if we consider the other bytes of $M \cdot V$ and $M \cdot V'$, and additionally, $V'=\{0,128,0,0\}, \{0,0,128,0\}, \{0,0,0,128\}$, we find that all bytes of $M$ must have an lsbit of 1. Finally, we consider $V'=\{128,128,128,128\}$. If all the lsbits of $M$ are 1, then $M \cdot V = M \cdot V'$; that is also a violation of the MDS property (as well as making decryption difficult...)

Answer 2

An obvious distinction is that $GF(2^8)$ is a field, whereas $\Bbb Z/2^8\Bbb Z$ is not. That means, for any non-zero element $x\in GF(2^8)$, there exists some element $y\in GF(2^8)$ such that $xy=1$. This is not true for $\Bbb Z/2^8\Bbb Z$, take for instance any even number.

Note that the field is used in other operations, for example in the ByteSub operation. Here $x\in GF(2^8)$ is replaced by $Ax^{-1}+B$ for a matrix $A$ and a vector $B$. This definition would be problematic for $\Bbb Z/2^8\Bbb Z$, where half the elements do not have inverses.