Score:8

On what Galois field AES really works?

tf flag
Tom

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?

Score:11
ng flag

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.

Ruggero avatar
kr flag
Mixcolumns embeds a column of the state as a polynomial in $GF(2^8)[X]$ and performs a multiplication with $'03'X^3+'01'X^2+'01'X+'02'$ modulo $X^4+1$. The notation 'xx' is the hex encoding of the $GF(2^8)$ element. Since $X^4+1$ is not irreducible, that is not a field. However it is coprime with $'03'X^3+'01'X^2+'01'X+'02'$ so Mixcolumns is invertible.
Score:4
sa flag

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:

this

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.

ar flag
This is a good point. In particular, if you think of the elements of ${\rm GF}(2^8)$ as polynomials over ${\rm GF}(2)$, as many people like to do, then AES uses polynomials whose coefficients are _themselves_ polynomials(!).
ar flag
(FWIW, [in my opinion](https://crypto.stackexchange.com/a/2718), while representing the elements ${\rm GF}(p^n)$ as polynomials over ${\rm GF}(p)$ is useful for defining the addition and multiplication rules for those fields, once those rules are defined that _alternative_ representation is best set aside, and the elements viewed just as numbers in a funny kind of arithmetic system, as that's what they really are.)
fgrieu avatar
ng flag
Took the best part of a day, but at least now I get what this answer is talking about, if not exactly where that simplifies things.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.