Score:1

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

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?

[A Stick Figure Guide to the Advanced Encryption Standard (AES)](http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html) and AES-Book.
Score:4

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

Score:4

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