Isomorphism for optimization of GF256 implementation in AES S-Box using intermediary finite fields

Question

I've questions about the implementation of The S-Box in the AES cipher.

In this cipher, the Finite Field GF256 is implemented as a quotient $\mathbb{F}_2[X]/(X^8+X^4+X^3+X+1$). The operations can be done by representing its elements as 8 bits vectors. But depending on the basis one choses, computation could be easier. Indeed, if one chooses a normal basis, some interesting stuff happens... Now my questions are:

1)How do we construct all the isomorphisms $\delta$ which would make a basis change when seeing $\mathbb{F}_{256}$ as an 8 dimensional vector space over $\mathbb{F}_2$?

2)How many different basis are there?

3)How to obtain the matrices of these isomorphisms?

Here's an example of such a matrix found in the reference given below: $$ \begin{pmatrix} 0&0&0&1&0&0&1&0\\ 1&1&1&0&1&0&1&1\\ 1&1&1&0&1&1&0&1\\ 0&1&0&0&0&0&1&0\\ 0&1&1&1&1&1&1&0\\ 1&0&1&1&0&0&1&0\\ 0&0&1&0&0&0&1&0\\ 0&0&0&0&0&1&0&0\\ \end{pmatrix} $$

REF:A Very Compact S-Box for AES by D. Canright (google David Canright publications)

Thank you all !

Answer 1

As far as I can tell the question doesn't actually have anything to do with $GF(256)$ or AES or the S-Box; you're just asking about the automorphisms of $\mathbb F_2^8$.

There are $2^8-1$ different non-zero vectors that you can map the first basis vector to. Then there are $2^8-2$ different vectors that are linearly independent of that vector that you can map the second basis vector to, and so on: In step $k$, $2^{k-1}$ vectors are linear combinations of the basis vectors you already have, so $2^8-2^{k-1}$ aren't, so the total number of different automorphisms is $\prod_{k=1}^8(2^8-2^{k-1})=5348063769211699200$.

The method of counting also suggests how to construct all these automorphisms. (I'm not sure what the difference between your questions 1) and 3) is – how would you represent the automorphisms if not using their bases?)

Answer 2

This does not really answer your explicit questions. I'm just a bit worried that you may heading into a wrong direction in your implementation, because IMHO answering them will not help you much. If you are happy with your implementation, and simply want to understand the underlying theory a bit better, then your intellectual curiosity is to be commended. Anyway, I am listing some alternative approaches together with links to other on-site questions and answers.

There are many (efficient ?) ways of implementing the field $GF(256)$. Addition using any basis is trivially implemented as bitwise XOR. A popular way of implementing multiplicative operations (as well as the inverse) is to use discrete logarithm tables (and an inverse table). Can you spare 512 bytes of memory for such a purpose? See the latter half of this answer for a very simple introduction, and this answer by Dilip Sarwate explains a neat programming trick in the implementation of log-tables.

You can also try using a normal basis, but I really don't know whether that gives significant speed improvements in this case. Correct me if I'm wrong, but I think that AES specifies that the input/output should be represented using a given monomial basis, so conversions at the beginning and at the end will eat some/most/all of the time savings. Admittedly I haven't checked whether $GF(256)$ has a very nice normal basis (or even a so called optimal normal basis).

Yet another alternative is to represent elements of $GF(256)$ as a vector space (w.r.t. either a monomial basis or a normal basis) over a non-trivial subfield, here either $GF(16)$ or $GF(4)$. This question gives you links to relevant papers. My answer to that question seeks to describe the algebra, but is not exactly elegant, as the linked papers left some of the key details unexplained, so I couldn't completely decipher them (at least not without putting more effort into it than I was willing to).

Answer 3

example of such a matrix found in the reference given below

The matrix shown in that article combines mapping from GF(((2^2)^2)^2) back to GF(2^8) named as matrix X with the affine mapping matrix named as M, so the matrix you see in that article is the product of MX.

For the inversion (1/z) part of encoding, a matrix multiply by X^-1 (not shown) is used to map from GF(2^8) to GF(((2^2)^2)^2) (the elements are treated as 8 row by 1 bit matrices). The inversion is done within GF(((2^2)^2)^2), then the inverted GF(((2^2)^2)^2) element is mapped back GF(2^8) and at the same time mapped to affine value using the combined matrix MX. Then a 8 row by 1 bit matrix named b is xor'ed to complete the affine mapping. The process is described in the article, but the matrices X^-1, and X are not shown.

There is also no explanation for how the mapping matrix X^-1 is derived, where the parameters for GF(((2^2)^2)^2) are fixed and chosen to minimize the number of gates, and a brute force trial and error search for any primitive element of GF(2^8) where the mapping results in fields isomorphic in addition and multiplication: map(a+b) = map(a) + map(b) and map(a b) = map(a) map(b) is done.

I explain the derivation of the mapping matrix in this answer (link):

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