9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Multiplication mod $2^{8}$ does not always have an inverse, so you would not be able to perform the invMixColumns step. If you wanted to use integers, then you would need a prime modulus, but if that were the case then you couldn't use all 8-bit values, since there is no prime where $p-1$ = 0xff. $\endgroup$ – user13741 Jan 7 '17 at 16:32
  • 1
    $\begingroup$ @user13741: actually, there are 4x4 matricies over $Z/256$ that are invertable; that is, you could define an InvMixColumn step that would invert it, and in fact, the values used in the AES MDS matrix just happen to be invertable over $Z/256$ $\endgroup$ – poncho Jan 7 '17 at 16:55
8
$\begingroup$

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...)

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't see how this answers the question; yes, there are noninvertable (nonzero) elements in $Z/256$, however that doesn't prevent nontrivial invertable 4x4 matrices. Yes, you couldn't use $Z/256$ in the ByteSub operation; however the question wasn't about the ByteSub operation. $\endgroup$ – poncho Jan 7 '17 at 20:32
  • $\begingroup$ Well the question seems to infer that working in $GF(2^8)$ is unique to MixColumns, while it is used through all of AES. If you replace all $GF(2^8)$ operations by $\Bbb Z/2^8\Bbb Z$ operations, what you end up with does not make sense. Yes, you can forget about this and only look at MixColumns, and then yes, perhaps you could use an invertible matrix. But is it really worth doing that without having the big picture in mind? $\endgroup$ – CurveEnthusiast Jan 7 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.