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

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

Solution 2:

mapping elements from the extension field $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. Here are the givens:

$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^2 + x + 1$, with primitive element: α(x) to be determined.

A trial and error brute force search can be done for any primitive element α(x) that will result in isomorphic mapping between the two fields. The search process uses a trial value for α(x) and the given β(x) to construct a mapping matrix as explained below, and tests to see if the mapping works or fails. The search will find that the mapping works with $α(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 values correspond to powers of α(x): logα(x){80 40 20 10 08 04 02 01} = {64 c3 23 82 e1 41 a0 00}, or α(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

and it's inverse to map back is:

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