What is the intuition behind mapping of elements from $GF(2^8)$ to $GF(((2^2)^2)^2)$?

Question

I'm finding it very difficult to understand the concept of mapping elements from the extension field $GF(2^8)$, to $((GF(2)^2)^2)^2 $. I realize that the elements of the field, $GF(2^8)$, that I want to split into simpler fields, can be represented as polynomials of maximum degree, 7, and addition is simply an XOR, multiplication and inversion is done modulo the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$, but being a beginner I have no idea whatsoever to map the elements to the composite fields. I understand that, the mapping is possible, because of field isomorphisms. In essence, I'm having trouble visualizing how the math holds together. My main motivation to understand about this, is because, this technique is used for implementing a compact version of the AES sbox. Almost, every source, I can find on the internet, speaks complicated language!

A good source, and every help and advice will be greatly appreciated!

Answer 1

This is not an answer just a very long comment.

I don't think you quite understand what is going on. (Forgive me if I am misunderstanding you.) We are NOT going to split the big field into smaller fields, that isn't possible, but we are going to split the additive structure of the big field into copies of the additive structure of the smaller field: the multiplication still mixes everything up.

I think it's best to start off thinking about the complex numbers $\mathbb{C}$ and the real numbers $\mathbb{R}$. When we first construct $\mathbb{C}$ we take $\mathbb{R}$ and a "new" element $i$, and we look at all the $a+bi$ with $a,b\in\mathbb{R}$: we even draw a picture with all the $a$ along the real $x$-axis, and all the $bi$ along the $y$-axis. We add these in the "obvious" way, and so at least additively we have $\mathbb{C}$ just looks like $\mathbb{R}^2$. But multiplication is different: we say "oh, let's have $i^2=-1$"; and so the multiplication tangles together the copies of $\mathbb{R}$. More formally we can manufacture $\mathbb{C}$ in this way: we let it be the set of all polynomials with real coefficients, where after we add and multiply them we reduce them all modulo the (irreducible) $X^2+1$.

We can play the same trick whenever we have a field $\mathbb{k}$ and an irreducible polynomial $\phi(X)$ of degree $d$. We can make a big field $\mathbb{K}$ by taking the set of all polynomials with coefficients in $\mathbb{k}$, using the usual addition and multiplication except that we reduce everything modulo $\phi(X)$. In this way we'll see that the additive structure of $\mathbb{K}$ is just like the additive structure of $\mathbb{k}^d$; but the multiplication tangles it all together. [It is a reasonably big theorem that this process gives a field.]

The simplest example is to start with $GF(2)=\{0,1\}$. The only irreducible quadratic is $X^2+X+1$. So we can get a field with $4$ elements by taking $GF(4)=\{0,1,\omega,1+\omega\}$ and using addition modulo $2$, and for multiplication remembering that $\omega^2+\omega+1=0$. [Note that just as we used $i$ as the new element for the complex numbers to remind ourselves to work modulo $i^2+1$, here I have used $\omega$ to remind myself to reduce modulo the irreducible.]

Final comment. There is a theorem that for each $p^n$ ($p$ prime) there is, up to field isomorphism exactly one field of order $p^n$.

Answer 2

mapping elements from $GF(2^8)$ to $GF(((2^2)^2)^2)$.

All fields with the same number of elements are isomorphic in addition and multiplication. However, I have yet to find any article that explains how to map elements from one field to another so that map(a + b) = map(a) + map(b) and that map(a b) = map(a) map(b). Generally the articles just include a mapping matrix with no explanation for the values in the matrix or how the matrix was derived.

For your specific question, what is typically done is the polynomials and primitive elements related to $GF(((2^2)^2)^2)$ are chosen to minimize gate count in hardware. For AES, the irreducible polynomial is also fixed. The only variable is finding any primitive (generating) element of GF(2^8) that can be used to generate a mapping matrix to provide isomorphic mapping between the two fields. I used this article about AES S-Box optimization as a basis for isomorphic mapping I show in this answer:

https://link.springer.com/content/pdf/10.1007/3-540-45682-1_15.pdf

Note the mapping matrices used in that article have the least significant bit in the upper left corner, while the mapping matrices shown below have the most significant bit in the upper left corner, but otherwise they're the same matrices.

$GF(2^2) : x^2 + x + 1$ , with primitive element: x (hex 2)

$GF((2^2)^2) : x^2 + x + 10_2$ , with primitive element: x (hex 4)

$GF(((2^2)^2)^2) : x^2 + x + 1100_2$, with primitive element: β(x) = x (hex 10)

$GF(2^8) : x^8 + x^4 + x^3 + x + 1$, with primitive element: α(x) to be determined.

The article linked to above mentions doing a search for both $α(x)$ and $β(x)$, but $β(x)$ can be defined as $β(x) = x$, so only a search for $α(x)$ is needed, and 8 of the 128 primitive elements for $GF(2^8)$ will result in isomorphic mapping between the two fields. To produce the mapping matrices used in the article above, $α(x) = x^4 + x^3 + x^2 + x + 1$.

The mapping matrix is an 8 row by 8 bit matrix constructed based on α(x) and β(x). The indexes of the columns of this matrix correspond to the GF(2^8) hex values {80 40 20 10 08 04 02 01}. Those indexes correspond to powers of α(x): α(x)^{64 c3 23 82 e1 41 a0 00} = {80 40 20 10 08 04 02 01}. The values of the columns of the matrix are β(x) raised to the the same powers: β(x)^{64 c3 23 82 e1 41 a0 00} = {fc 4b b0 46 74 7c 5f 01}. The mapping matrix is:

 1  0  1  0  0  0  0  0
 1  1  0  1  1  1  1  0
 1  0  1  0  1  1  0  0
 1  0  1  0  1  1  1  0
 1  1  0  0  0  1  1  0
 1  0  0  1  1  1  1  0
 0  1  0  1  0  0  1  0
 0  1  0  0  0  0  1  1

fc 4b b0 46 74 7c 5f 01

The indexes of the columns of the inverse of the mapping matrix correspond to powers of β(x): β(x)^{67 bc ab 01 66 bb aa 00} = {80 40 20 10 08 04 02 01}, and the values of the columns are α(x) raised to the same powers: α(x)^{67 bc ab 01 66 bb aa 00} = {84 f1 bb 1f 0c 5d bc 01}:

 1  1  1  0  0  0  1  0
 0  1  0  0  0  1  0  0
 0  1  1  0  0  0  1  0
 0  1  1  1  0  1  1  0
 0  0  1  1  1  1  1  0
 1  0  0  1  1  1  1  0
 0  0  1  1  0  0  0  0
 0  1  1  1  0  1  0  1

84 f1 bb 1f 0c 5d bc 01

I created a pdf file with this information which can be obtained from either of these links:

https://github.com/jeffareid/finite-field/blob/master/Composite%20Field%20Mapping%20Example.pdf

http://rcgldr.net/misc/Composite%20Field%20Mapping%20Example.pdf

---

Mapping is normally used to find the inverse (1/z) in GF(2^8) using the composite field to do the math. Consider the simpler case of mapping from GF(2^8) to GF((2^4)^2) based on polynomial $x^2 + ax + b$, and that the mapping results in a GF((2^4)^2) = cx + d. The goal is to find the inverse (1/(cx+d)) = ex+f, so that (cx+d)(ex+f) % (x^2+ax+b) = 0x+1

(cx+d)(ex+f) = cex^2+(cf+de)x+df

use long hand division for cex^2+(cf+de)x+df%(x^2+ax+b)

                                           ce
             --------------------------------
x^2 + ax + b | ce x^2 +     cf+de x +      df
               ce x^2 + ace       x + bce
                      ----------------------
                        ace+cf+de x + bce+df

this results in two equations with two unknowns, e and f:

ace+cf+de  = 0
bce+df     = 1

(ac+d)e + cf = 0
    bce + df = 1

(ac+d)e = cf
      e = cf/(ac+d)

bc(cf/(ac+d)) + df = 1

((bcc/(ac+d))+d)f = 1
f = 1/((bcc/(ac+d))+d)
f = (ac+d)/(bcc+acd+dd)

(ac+d)e + c((ac+d)/(bcc+acd+dd)) = 0
(ac+d)e = c((ac+d)/(bcc+acd+dd))
e = c/(bcc+acd+dd)

To simplify the hardware based math further still, a GF((2^4)^2) primitive polynomial of the form $x^2 + x + b$ is used (setting the a == 1), so that

e =    c /(bcc+cd+dd)
f = (c+d)/(bcc+cd+dd)

This still requires inversion of a 4 bit number, which could be done with a 16 nibble table (the table could be optimized into a set of gates), but using GF(((2^2)^2)^2) to further split up the two 4 bit fields into four 2 bit fields simplifies the hardware a bit more. The math for inversion of GF((2^2)^2) follows the same logic as inversion of GF((2^4)^2) as shown above, except that inversion in GF(2^2) can be done via squaring: $ (1/z(x)) \mod x^2+x+1 == (z(x)^2) \mod x^2+x+1 $.

---

The above approach uses polynomial basis. For example, each element of $GF((2^2)^2)$ is of the form $(a \ x \ + \ b)$, where $a$ and $b$ are elements of $GF(2^2)$, and $x$ is a variable in $GF((2^2)^2)$.

An alternative approach uses normal basis. For example, each element of $GF((2^2)^2)$ is of the form $(a \ X^m \ + \ b \ X)$, where $a$ and $b$ are elements of $GF(2^2)$, and $X$ is an element of $GF(2^8)$. This is explained here:

Normal basis on tower | composite fields