0
$\begingroup$

Read the Reference for Simplified AES ( S-AES )

enter image description here

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)

$\endgroup$
  • $\begingroup$ Applying the matrix to $1010$ yields the sum of the first and the third column, ergo: $0101$. But you forget the inverse ! $\endgroup$ – Henno Brandsma Sep 26 '17 at 22:45
  • 1
    $\begingroup$ Correct your matrix multiplication please. $\endgroup$ – Henno Brandsma Sep 28 '17 at 7:40
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Oct 3 '17 at 2:53

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.