# How are m2 and m3 boxes computed? [duplicate]

I stumbled upon an AES implementation that uses boxes with multiples of 2 and 3 for its MixColumns operation. When inspecting the m2 box, I saw that the first line is :

0x00,0x02,0x04,0x06,0x08,0x0A,0x0C,0x0E,0x10,0x12,0x14,0x16,0x18,0x1A,0x1C,0x1E,


So nothing abnormal, but once we reach 0xFE, the next line is :

0x1B,0x19,0x1F,0x1D,0x13,0x11,0x17,0x15,0x0B,0x09,0x0F,0x0D,0x03,0x01,0x07,0x05,


Why does it become so weird ? How were those boxes computed ?

A byte $$b$$ in AES represents a polyonmial of degree at most $$7$$ where the coefficients are the bits of $$b$$. An example is the byte written in hexadecimal f3 represents $$x^7 + x^6 + x^5 + x^4 + x + 1$$ (with big endian order).
There are two operations with these polynomials: the addition and the multiplication. Given the polynomials $$f(x) = a_7 x^7 + \cdots + a_1 x + a_0$$ and $$g(x) = b_7x^7 + \cdots + b_1 x + b_0$$, then the addition is $$f(x) + g(x) = (a_7 \oplus b_7) x^7 + \cdots + (a_1 \oplus b_1) x + (a_0 \oplus b_0),$$ using a xor between the coefficients of each polynomial, so the resulting polynomial is also of degree at most $$7$$, with binary coefficients. Concerning the multiplication it is necessary to add a reduction in case the degree of the polynomial is greater than $$7$$. Example: $$f(x) \cdot x = a_7 x^8 + \cdots + a_1 x^2 + a_0 x.$$ In particular for AES, it is a modular reduction with the polynomial $$h(x) = x^8 + x^4 + x^3 + x + 1$$. It means that in all the calculcations, we have $$x^8 = x^4 + x^3 + x + 1,$$ so the previous calculation becomes $$\begin{array}{rcl} f(x) \cdot x & = & a_7(x^4 + x^3 + x + 1) + a_6 x^7 + \cdots + a_1 x^2 + x \\ & = & a_6 x^7 + a_5 x^6 + a_4 x^5 + (a_7 \oplus a_3) x^4 + (a_7 \oplus a_2) x^3 \\ & & + a_1 x^2 + (a_7 \oplus a_0) x + a_7 \end{array}$$ Why in particular this polynomial $$h(x)$$ is because it has degree $$8$$ and cannot be written as a product of two (or more) non-trivial polynomials (similar as prime numbers that cannot be written as the product of two or more integers greater than $$1$$).
Now, all that is said above is enough to understand the m2 and m3 boxes that can be encountered in some implementations. The m2 box is only the multiplication by $$x$$ of all polynomials. For polynomials of degree at most $$6$$, it means only a bitwise shift left, but for polynomials of degree $$7$$, a reduction is necessary. $$\begin{array}{ccc} \hline \text{hex} & \text{polynomial} & \text{times } x & \text{hex}\\ \hline \texttt{00} & 0 & 0 \cdot x = 0 & \texttt{00}\\ \texttt{01} & 1 & 1 \cdot x = x & \texttt{02}\\ \vdots \\ \texttt{7F} & x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 & x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x & \texttt{FE} \\ \texttt{80} & x^7 & x^7 \cdot x = x^4 + x^3 + x + 1 & \texttt{1b} \\ \vdots \\ \hline \end{array}$$ The m3 box is the multiplication by $$x + 1$$ and is easily obtained with an addition of the polynonmial $$f$$ with the result of the m2 box since: \begin{align} f(x) \cdot (x + 1) & = f(x) \cdot x + f(x) \cdot 1 \\ & = f(x) \cdot x + f(x) \end{align}