(Solved): 4. Information: Composite fields are among the most efficient ways to implement the S-box in hardwa ...

4. Information: Composite fields are among the most efficient ways to implement the S-box in
hardware (LUTs are good on FPGAs but composite fields are more area-efficient on ASICs). As you
know, inversion in finite field GF(2?) is costly. Thus, it is preferred to perform transformation
from binary field to tower fields in composite fields and after computing the inverse, go back to
binary fields.
Inversion in GF(2?) can be done using a couple of multiplications (below, you need to do a simple
one), a squaring, and one inversion in composite field denoted as GF(2?)². This is the base for
composite fields: To transform, do the arithmetic less-costly there, and go back to binary field.

You only need to do this simple calculation: Show that for inputs a(x)=a3x³+a2x²+a1x+a0 and
b(x)=b3x³+b2x²+b1x+b0 and the multiplication result q(x)=q3x³+q2x²+q1x+q0 in GF(2?) with the
irreducible polynomial p(x)=x?+x+1, we get the following for a(x).b(x) mod p(x). Subexpression
sharing has been done to reduce the complexity as you see. Remember that you do not need to know
details of composite fields for this calculation.

4. Information: Composite fields are among the most efficient ways to implement the S-box in hardware (LUTs are good on FPGAs but composite fields are more area-efficient on ASICS). As you know, inversion in finite field $GF\left(2^8\right)$ is costly. Thus, it is preferred to perform transformation from binary field to tower fields in composite fields and after computing the inverse, go back to binary fields. Inversion in $GF\left(2^8\right)$ can be done using a couple of multiplications (below, you need to do a simple one), a squaring, and one inversion in composite field denoted as $GF{\left(2^4\right)}^2$. This is the base for composite fields: To transform, do the arithmetic less-costly there, and go back to binary field. You only need to do this simple calculation: Show that for inputs $a(x)=a_3{x}^3+a_2{x}^2+a_{1}x+a_0$ and $\mathrm{b}(\mathrm{x})={\mathrm{b}}_3{\mathrm{x}}^3+{\mathrm{b}}_2{\mathrm{x}}^2+{\mathrm{b}}_1\mathrm{x}+{\mathrm{b}}_0$ and the multiplication result $\mathrm{q}(\mathrm{x})={\mathrm{q}}_3{\mathrm{x}}^3+{\mathrm{q}}_2{\mathrm{x}}^2+{\mathrm{q}}_1\mathrm{x}+{\mathrm{q}}_0$ in $\mathrm{GF}\left(2^4\right)$ with the irreducible polynomial $\mathrm{p}(\mathrm{x})={\mathrm{x}}^4+\mathrm{x}+1$, we get the following for $a(x)?b(x)\mathrm{mod}p(x)$. Subexpression sharing has been done to reduce the complexity as you see. Remember that you do not need to know details of composite fields for this calculation. $\begin{array}{c}q(x)=a(x)?b(x)=a(x)?b(x)\mathrm{mod}\mathrm{P}(x),a(x),b(x),q(x)?\mathrm{GF}\left(2^4\right)\\ a_A=a_0?a_3,a_B=a_2?a_3\\ q_0=a_0{b}_0?a_3{b}_1?a_2{b}_2?a_1{b}_3{q}_1=a_1{b}_0?a_A{b}_1?a_B{b}_2?\left(a_1?a_2\right)b_3\\ q_2=a_2{b}_0?a_1{b}_1?a_A{b}_2?a_B{b}_3{q}_3=a_3{b}_0?a_2{b}_1?a_1{b}_2?a_A{b}_3.\end{array}$