1
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.