How are S-box calculated in S-AES?

Question

Read the Reference for Simplified AES ( S-AES )

Q1 Explain how the S- box is constructed taking example $b_0b_1b_2b_3=1010$

What I did

$\begin{bmatrix} 1 &0 &1 &1 \\ 1 & 1& 0&1 \\ 1& 1& 1 & 0\\ 0 &1 & 1& 1 \end{bmatrix} *\begin{bmatrix} b_0\\ b_1\\ b_2\\ b_3 \end{bmatrix}+\begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix}$

$= \begin{bmatrix} 1 &0 &1 &1 \\ 1 & 1& 0&1 \\ 1& 1& 1 & 0\\ 0 &1 & 1& 1 \end{bmatrix} *\begin{bmatrix} 1\\ 0\\ 1\\ 0 \end{bmatrix}+\begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix}$

$= \begin{bmatrix} (1011\times1) \bigoplus (1011\times0)\bigoplus (1011\times1)\bigoplus (1011\times0) \\ (1101\times1) \bigoplus (1101\times0)\bigoplus (1101\times1)\bigoplus (1101\times0)\\ (1110\times1) \bigoplus (1110\times0)\bigoplus (1110\times1)\bigoplus (1110\times0)\\ (0111\times1) \bigoplus (0111\times0)\bigoplus (0111\times1)\bigoplus (0111\times0) \end{bmatrix}+\begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix}$

$=\begin{bmatrix} 1011 \bigoplus 0\bigoplus 1011\bigoplus 0 \\ 1101 \bigoplus 0\bigoplus 1101\bigoplus 0\\ 1110 \bigoplus 0\bigoplus 1110\bigoplus 0\\ 0111 \bigoplus 0\bigoplus 0111\bigoplus 0 \end{bmatrix}+\begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix}$

$= \begin{bmatrix} 1011 \bigoplus1011 \\ 1101 \bigoplus1101\\ 1110 \bigoplus 1110\\ 0111\bigoplus 0111 \end{bmatrix}+\begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix}$

$=\begin{bmatrix} 0 \\ 0\\ 0\\ 0 \end{bmatrix}\bigoplus\begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix}$

Im getting S-box transformation of $1010$ as $1001$ . Where am i doing wrong ?

Q2 Also Explain the meaning of the statement and its relevance in construction of S-Box " The addition and multiplication in the equation above are being done modulo 2 (with XOR), but not in GF(16)

Answer 1

Do the inverse over the field first, then the affine transform on that.

You must first invert $1010 = x^3 + x$ in $\textrm{GF}(16)$, with prime polynomial $x^4 + x + 1$; use the extended Euclidean algorithm for that, and see that $1100 = x^3+x^2$ is the inverse (you can verify this by computing their product and replacing all $x^4$ by $1+x$ an ditto for higher powers $x^5 = x^2+x$, $x^6 = x^3+x^2$ etc.; we are left with $1$, using $x+x=0$ etc.)

You can also make a log table based on the generator $x$:

$$ \begin{matrix} 0 & x^0 & 1 & 0001\\ 1 & x^1 & x & 0010\\ 2 & x^2 & x^2 & 0100\\ 3 & x^3 & x^3 & 1000\\ 4 & x^4 & 1+x & 0011\\ 5 & x^5 & x^2+x & 0110\\ 6 & x^6 & x^3 + x^2 & 1100\\ 7 & x^7 & x^3 + x + 1 & 1011\\ 8 & x^8 & x^2 +1 & 0101\\ 9 & x^9 & x^3+x & 1010\\ 10 & x^{10} & x^2+x+1 & 0111\\ 11 & x^{11} & x^3 + x^2 +x & 1110\\ 12 & x^{12} & x^3 + x^2 +x + 1 & 1111\\ 13 & x^{13} & x^3 + x^2 +1 & 1101\\ 14 & x^{14} & x^3 + 1 & 1001\\ 15 & x^{15} & 1 & 0001 \end{matrix} $$ And note that $1010 = x^9$ so its inverse is $x^6 = 1100$ (as $x^{15} = 1$).

We then apply the affine transform over $F_2$ to $1100$, we get for the matrix multiplication as the sum of the first two columns with result $\begin{bmatrix}1\\1\\1\\0 \end{bmatrix}+ \begin{bmatrix}0\\1\\1\\1 \end{bmatrix}= \begin{bmatrix}1\\0\\0\\1 \end{bmatrix}$

and adding the constant vector $\begin{bmatrix}1\\0\\0\\1 \end{bmatrix}$ to that we get $0000$, as required.

As an aside: $0000$ has no inverse, so we use the convention that its "inverse" is $0000$ and into the affine transform this yields the constant vector $1001$, as the table says. The point of the affine tarnsform is to ensure the $S$-box defined by the (very nonlinear) inverse mapping does not have $0000$ as a fix point. The element $0001$ has $0001$ as its inverse, and then the matrix multiplication gives $1101$ (the last column) and so adding $1001$ gives $0100$ etc.