1
$\begingroup$

$\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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.