In AES-256, what exactly forms the extension field $GF(2^8)$?

Question

My question is a little difficult to describe, so let me first start with an analogy

In an elliptic curve over a finite field, there are 2 groups - the first group is a finite field over which the elliptic curve is defined. The 2nd group is the group which is formed by all the points of the elliptic curve. These are the 2 different groups.

---

My actual question:

In AES256 we use a polynomial to represent each byte. The coefficients of the polynomial are from $\operatorname{GF}(2)$ - i.e. it's polynomial ring over $\operatorname{GF}(2)$. The polynomial addition is done mod 2. The multiplication is done in 2 steps. First the 2 polynomials are multiplied mod 2. Then they are reduced mod the irreducible polynomial

So I am confused as to where exactly the $\operatorname{GF}(2^8)$ comes into the picture?

I am guessing that each byte which is a represented by a polynomial is a member of field $\operatorname{GF}(2^8)$ - i.e. $\operatorname{GF}(2^8)$ is a field of bytes.

And just like for elliptic curves we arbitrarily define addition using the tangent & chord method, here we arbitrarily define the addition & multiplication of the field elements (the bytes) as

• addition of 2 elements of the field $\operatorname{GF}(2^8)$ - add coefficients mod 2.

• multiplication of 2 elements of the field $\operatorname{GF}(2^8)$ - multiply the coefficients mod 2 & then reduce it mod the irreducible polynomial.

Is my interpretation correct or am I totally missing the field abstraction & operations here?

If it is correct, then my next question is about the concept of extension fields here - $\operatorname{GF}(2^8)$ is an extension field of $\operatorname{GF}(2)$ - what exactly does does it mean here - does it just mean that each byte contains 8 bits (each bit being an element of $\operatorname{GF}(2)$). Likewise what do the sub-fields $\operatorname{GF}(2^2)$ & $\operatorname{GF}(2^4)$ represent here?

Answer 1

There is no equivalent in AES to the Elliptic Curve group used in Elliptic Curve Cryptography. In particular there is no match for points with coordinates obeying a curve equation, or for a fancy rule to add these.

The parallel with ECC stops at AES using a finite field for bytes as does ECC for each point coordinate. In AES, the field is $\operatorname{GF(q)}$ with $q=2^8=256$. In ECC the field is $\operatorname{GF(q)}$ for some much larger $q$ (typically with hundreds rather than 9 bits).

One can think a finite field as a finite analog of the set of reals $\mathbb R$ (or of the fractions $\mathbb Q$) when it comes to algebra restricted to addition, multiplication, taking the opposite or the inverse, and testing equality (rather than order). A set with $q$ elements can be made a field if and only if $q=p^m$ for $p$ a prime and integer $m>0$. When $m=1$, the field $\operatorname{GF(p)}$ with prime $p$ is the familiar $\mathbb Z/p\mathbb Z$, also noted $\mathbb Z_p$, or equivalently integers in $[0,p)$ with field laws addition and multiplication modulo $p$. Such field is used in ECC for so-called prime curves like secp256k1 (with $p$ a 256-bit prime). But ECC works for any large finite field. E.g. sect283k1 uses field $\operatorname{GF(2^{283})}$, and this Elliptic Curve group uses field $\operatorname{GF}(9767^{19})$.

When $m>1$, including when $p=2$, a field element can be thought as a vector or tuple of $m$ elements of the field $\operatorname{GF(p)}$, or equivalently as the $m$ coefficients of a polynomial $P(x)$ of degree less than $m$ and coefficients in $\operatorname{GF(p)}$. Addition in the field $\operatorname{GF(p^m)}$ is addition of vector/tupple components in the field $\operatorname{GF(p)}$, or polynomial addition. When $p=2$ that reduces to XOR. See this for why the representation as coefficients of a polynomial makes sense to neatly define multiplication.

(In AES) $\operatorname{GF}(2^8)$ is an extension field of $\operatorname{GF}(2)$ (…) Does it just mean that each byte contains 8 bits (each bit being an element of $\operatorname{GF}(2)$) ?

It means that, and $\operatorname{GF}(2^8)$ is fitted with two internal laws (operations) that make it a field: addition that reduces to addition of each of the 8 components in $\operatorname{GF}(2^8)$, and a suitable multiplication.

Likewise what do the sub-fields $\operatorname{GF}(2^2)$ and $\operatorname{GF}(2^4)$ represent here?

They are different fields with 4 and 16 elements rather than 256. Sometime it might be interesting to represent an element of $\operatorname{GF}(2^8)$ as two elements of $\operatorname{GF}(2^4)$ or a four elements of $\operatorname{GF}(2^2)$. For addition such representation works quite directly, but multiplication is a more complicated story. That's not required in a standard implementation or study of AES (I've only seen it used in optimized implementation of the AES S-box).

Answer 2

$GF(2^n)$ elements can indeed be represented by $n$-bit strings, and at the same time can be interpreted as polynomials of degree at most $n-1$ with coefficients from $GF(2)$. The difference between "just a byte" and a $GF(2^8)$ element are the field operations, which satisfy certain properties.

Addition is indeed just coordinate-wise addition of coefficients modulo 2.

Multiplication is defined by multiplying the polynomials, reducing the resulting coefficients modulo 2 and the polynomial itself modulo the field defining polynomial (using polynomial division).