Is Finite Field Multiplication Distributive? Moving Affine Transform in AES

Question

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.

Answer 1

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.