Is Finite Field Multiplication Distributive? Moving Affine Transform in AES

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.

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

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.