On what Galois field AES really works?

Question

I'm trying to understand the GF theory, but every time I come across information about AES it all makes no sense.

In my opinion $GF(2^8)$ defines any polynomial of the form:

$a_{7} x^7 + a_{6} x^6 + a_{5} x^5 + a_{4} x^4 + a_{3} x^3 + a_{2} x^2 + a_{1} x^1 + a_{0}$

Where $a_{i}$ can be 0 or 1. And everywhere I come across information that AES works just in $GF(2^8)$. But in AES $a_{i}$ are bytes, right? So $a_{i}$ can be every number from 0 to 7. And this mean that we have here $GF(8^8)$. And it has nothing to do with $GF(2^8)$.

Either I still don't understand the GF or they're all making some kind of simplification that's so far from the truth, that it shouldn't be done. So what Galois field AES really uses?

Answer 1

No, in AES the $a_i$ are not bytes. They are bits. The 8 bits $a_i$ together form a byte, and are considered a single element of the Galois Field ${\operatorname{GF}\left(2^8\right)}$, also noted $\mathbb F_{2^8}$.

The value of that byte can be computed by evaluating the polynomial for integer $x=2$, with ordinary addition and multiplication. In the reverse direction, the bits $a_i$ are the binary representation of the integer value of the byte, over 8 binary digits, with $a_0$ the least significant bit.

There are 16 bytes in an AES plaintext, ciphertext, or round key. These can be viewed as elements of the set ${\left({\operatorname{GF}\left(2^8\right)}^{4}\right)}^{4}$. This accounts for the organization of the 16 bytes as a 4×4 matrix of elements of ${\operatorname{GF}\left(2^8\right)}$. In particular, this set is a group under the extension of the addition law of field ${\operatorname{GF}\left(2^8\right)}$, which when applied to bytes is bitwise eXclusive-OR. That's used in AddRoundKey. It's possible to express ShiftRows, SubBytes, and even MixColumns in this framework.

For MixColumns, there is another possible view, where columns of said 4×4 matrix are the 4 coefficients in ${\operatorname{GF}\left(2^8\right)}$ of a polynomial of degree less than 4. Such polynomials can be multiplied with reduction modulo a reduction polynomial of degree 4. I was not familiar with that, which is the meat of this other answer, and of this comment. My reading is that this view gives an elegant reduction to a vector with 4 elements of ${\operatorname{GF}\left(2^8\right)}$ of the the regular 4×4 matrix in MixColumns, and simplifies the derivation of the invert matrix needed for decryption, but allows no computation shortcut in either encryption or decryption.

Answer 2

You can see an algebraists view of AES at in a document written by H. W. Lenstra.

There is also the more detailed The Design of Rijndael document by the designers at Daemen's homepage. Specifically on page 16, there is:

Maybe this is what is getting you confused, since multiple bytes are viewed as polynomials over $GF(2^8)$ for this part of the representation.