3
$\begingroup$

In AES the output of the SubBytes step is equal to:

$a_{0-15} = d*c_{0-15}^{-1}+b$

where $d$ is a constant 8x8 matrix and b is a constant 8x1 matrix both in $GF(2)$. The inversion is done in $GF(2^8)$.

After ShiftRows the output column of each MixColumns can be expressed in terms of four select $a$ values.

$m_0 = 2a_0+ 3a_1 + a_2 + a_3$

$m_1 = a_0 + 2a_1 + 3a_2 + a_3$

$m_2 = a_0 + a_1 + 2a_2 + 3a_3$

$m_3 = 3a_0 + a_1 + a_2 + 2*a_3$

Is there any reason that you can't take $m_0$ for instance and write it as:

$\begin{align*} m_0 =& 2(da_0+b) + 3(da_1+b) + (da_2+b) + (da_3+b)\\ =& 2da_0+2b + 3da_1+3b + da_2+b + da_3+b\\ =& d(2a_0+3a_1+a_2+a_3)+b\\ \end{align*} $

This would be the MixColumns operation followed by the affine transform.

$\endgroup$
  • $\begingroup$ $2(da_0+b)$ is not equal to $2(da_0) + (2b)$ $\endgroup$ – Richie Frame Dec 5 '18 at 2:55
  • $\begingroup$ specifically, $b + b$ = 0, since XOR addition of a polynomial against itself is 0 $\endgroup$ – Richie Frame Dec 5 '18 at 2:58
  • $\begingroup$ @RichieFrame could you take a look at my answer $\endgroup$ – jackana3 Dec 5 '18 at 14:07
  • $\begingroup$ A finite field is a field, so yes, multiplication distributes over addition. $\endgroup$ – Ilmari Karonen Dec 7 '18 at 1:15
1
$\begingroup$

From the above question $m = da_0$

At the bit level:

$m\oplus b = [m_7 \oplus b_7 , m_6 \oplus b_6 , m_5 \oplus b_5 , .... , m_0 \oplus b_0 ]$

$ \begin{align*} 2(m\oplus b) =& \operatorname{xtime}(2(m\oplus b)) = \\ =& [m_6 \oplus b_6 , m_5\oplus b_5 , m_4\oplus b_4, m_3\oplus b_3 \oplus (m_7\oplus b_7), m_2\oplus b_2 \oplus (m_7\oplus b_7) ,\\& m_1\oplus b_1,m_0 \oplus b_0 \oplus (m_7\oplus b_7),m_7\oplus b_7]\\ \end{align*} $

Where the multiplication by $02$ is denoted $\operatorname{xtime}(x)$.

$ \begin{align*} 2m =\;& [m_6 ,m_5,m_4,m_3\oplus m_7,m_2\oplus m_7,m_1,m_0\oplus m_7,m_7]\\ 2b =\;& [b_6 ,b_5,b_4,b_3\oplus b_7,b_2\oplus b_7,b_1,b_0\oplus m_7,m_7]\\ \end{align*} $

It follows that:

$2m\oplus 2b = 2(m\oplus b)$

because they result in the same formula at the bit level. You can see a similar result for multiplication by 3.

However, the question also assumes that it is possible to convert $2da_0 \oplus 3da_1 \oplus da_2 \oplus da_3$ to $d(2a_0\oplus 3da_1 \oplus da_2 \oplus da_3)$ this is not possible because it would require the original to be written as $d2a_0 \oplus d3a_1 \oplus da_2 \oplus da_3$ but matrix multiplication is not commutative.

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