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