# compact hardware implementation of inversion based 8-bit s-boxes

$\DeclareMathOperator{\GF}{GF}$ I cannot figure out how should I determine the matrix for transmission over $\GF(2^8)$ to $\GF(((2^2)^2)^2)$ in compact hardware implementation of inversion based 8-bit s-boxes.

In https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&ved=0ahUKEwjTrd3xsPzVAhVD5xoKHbHWDVAQFghUMAc&url=https%3A%2F%2Fcore.ac.uk%2Fdownload%2Fpdf%2F36718483.pdf&usg=AFQjCNFhSmTqjJz99DmRt8-19g7S-nXqaw , the author has searched among all potential $\GF(((2^2)^2)^2)$ to find the isomorphism tower field for inversion computation with the least area resources; and in page 24 it is showed that how the transmission matrix should be determined. However, I do not know if my $\GF(2^8)$ is different from AES, how should I build the corresponding matrix.

In fact, I do not know if the values of y, z and w would be different, and how should I determine them in the new $\GF(2^8)$!

I would appreciate if someone help me with this problem?

$\DeclareMathOperator{\GF}{GF}$ You can rebuild the transition matrix by using the fact that it is linear (which is why you make a transition matrix) and that it is a field isomorphism. Also, the solution is not unique: you may find several distinct transition matrices that will ultimately allow you to compute inversions in $\GF(2^8)$, but going through different representations in the tower of fields.

In general, you want to find the mapping of $\GF(2^k)$ within $\GF(2^n)$, for $k$ a divisor of $n$. By field isomorphism, $0$ is $0$, so you now want to consider the non-zero elements. For any $x \neq 0$ in $\GF(2^k)$, you know that $x^{2^k-1} = 1$ (since the non-zero elements in a field form a multiplicative group). But a polynomial equation of degree $2^k-1$ cannot have more than $2^k-1$ solutions. So the elements of $\GF(2^n)$ that actually are the elements of $\GF(2^k)$ are exactly the solutions to $x^{2^k-1} = 1$.

Moreover, the multiplicative group of non-zero elements in a field is cyclic. So, for any $k$ that divides $n$, there exists at least one value $g$ whose order is exactly $2^k-1$. In fact about half of them should be such generators. To find an element of of order exactly $2^k-1$ in $\GF(2^n)$, apply the following:

• Generate a random non-zero element $h$ in $\GF(2^n)$.
• Compute $g = h^{(2^n-1)/(2^k-1)}$.
• Order of $g$ is guaranteed to be a divisor of $2^k-1$. You just have to verify that it is not a strict divisor, by computing $g^e$ for any $e$ that divides $2^k-1$. For an AES S-box with $n = 8$, number of elements is so small that trying all of them is a workable strategy. So simply check that $g^e \neq 1$ for all $e$ from $1$ to $2^k-2$.

Therefore, you can compute your mapping in the following way:

• $0$ maps to $0$.
• Select an element $g$ of order exactly $2^n-1$ in the tower of fields.
• Select an element $g'$ of order exactly $2^n-1$ in the target field ($\GF(2^n)$).
• Define that $g$ maps to $g'$. Thus, for all integers $i$, $g^i$ maps to $g'^i$. By trying all $i$ from $0$ to $2^n-2$, you will cover all non-zero elements.

At that point you have a complete transition map. The corresponding matrix (since that map is linear) is obtained by simply selecting the map elements for $1$, $z$, $z^2$, $z^3$... $z^{n-1}$.

You might also want to have a look at this article by Boyar and Peralta. They built the smallest known so far circuit for computing an AES S-box. Notably, they begin in the same way as Canright, but they don't make a full tower of fields; instead, they stop at $\GF(2^4)$, for which they compute a fast circuit with a heuristic approach, which appears to yield better results than the full tower. They also explore the problem of minimal circuit for a linear transform.