Field multiplication in AES implementation - xtime
---22 Mar 2024---
This post explains how to implement the field multiplication taking place in the computation of MixColumns. I used to implement it in an ugly way when I was a student :)
# Field and polynomial
In AES, the field \(\mathbb{F}_{2^8}\) is denoted as
\[\mathbb{F}_{2^8} = \mathbb{F}_2[x]/(x^8 \oplus x^4 \oplus x^3 \oplus x \oplus 1).\]An element of this field is represented as a polynomial over \(\mathbb{F}_2\) of degree at most \(7\). In this representation, a byte \(\mathbf{a} = (a_7,\ldots,a_1,a_0)_2\) corresponds to the polynomial \(a(x) = a_7x^7 \oplus \ldots \oplus a_1x \oplus a_0\). The addition and multiplication of two polynomials is done modulo the polynomial \(x^8 \oplus x^4 \oplus x^3 \oplus x \oplus 1\).
# xtime function
Let \(\texttt{01}\) and \(\texttt{02}\) be the hexadecimal representations of two polynomials \(1\) and \(x\). We will show that by using the multiplications \(\texttt{01} \cdot \mathbf{a}\) and \(\texttt{02} \cdot \mathbf{a}\), we can compute the multiplication of \(\mathbf{a}\) with any other byte number. First, we go into details of these two multiplications.
The first one, \(\texttt{01} \cdot \mathbf{a} = \mathbf{a}\). Nothing to say.
The second one, \(\texttt{02} \cdot \mathbf{a}\) is the multiplication of \(a_7x^7 \oplus \ldots \oplus a_1x \oplus a_0\) and \(x\). We first multiply and have the following result:
\[a_7x^8 \oplus a_6x^7 \oplus a_5x^6 \oplus a_4x^5 \oplus a_3x^4 \oplus a_2x^3 \oplus a_1x^2 \oplus a_0x.\]We then take this polynomial and compute modulo \(x^8 \oplus x^4 \oplus x^3 \oplus x \oplus 1\). If we do it right, we should obtain the following reminder, which is the result of our multiplication:
\[a_6x^7 \oplus a_5x^6 \oplus a_4x^5 \oplus (a_3 \oplus a_7)x^4 \oplus (a_2 \oplus a_7)x^3 \oplus a_1x^2 \oplus (a_0 \oplus a_7)x \oplus 1\]For better looking, we write:
\[\texttt{02} \cdot \mathbf{a} = (a_6, a_5, a_4, a_3 \oplus a_7, a_2 \oplus a_7, a_1, a_0 \oplus a_7, a_7)\]This multiplication, \(\texttt{02} \cdot \mathbf{a}\), is usually denoted as \(\texttt{xtime}\) function (see the official documentation of AES). Depending on the value of \(a_7\), we have:
\[\texttt{xtime}(\mathbf{a}) = \texttt{02} \cdot \mathbf{a} = \begin{cases} (a_6, a_5, a_4, a_3, a_2, a_1, a_0, 0) & \text{if } a_7 = 0\\ (a_6, a_5, a_4, a_3, a_2, a_1, a_0, 0) \oplus (0,0,0,1,1,0,1,1) & \text{if } a_7 = 1\\ \end{cases}\]# Implementation
The implementation of \(\texttt{xtime}\) on Python follows the above result:
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
Another approach to implement \(\texttt{xtime}\) (on C) is:
unsigned char xtime(unsigned char x){
return ((x << 1) ^ (((x >> 7) & 1) * 0x1b));
}
# Other multiplications using xtime
For higher powers of \(x\), such as \(x^2\) \((\texttt{04})\), \(x^3\) \((\texttt{08})\), \(x^4\) \((\texttt{10})\), etc., we repeat the application of \(\texttt{xtime}\).
\[\begin{align} \texttt{04} \cdot \mathbf{a} &= x \cdot x \cdot a(x) &&= \texttt{xtime}(\texttt{xtime}(\mathbf{a})) \\ \texttt{08} \cdot \mathbf{a} &= x \cdot x \cdot x \cdot a(x) &&= \texttt{xtime}(\texttt{xtime}(\texttt{xtime}(\mathbf{a}))) \end{align}\]For other multiplications, we decompose them into multiplications of powers of \(x\). In the MixColumns, there is another multiplication, \(\texttt{03}\cdot \mathbf{a}\).
\[\texttt{03}\cdot \mathbf{a} = (x + 1) \cdot \mathbf{a} = \texttt{xtime}(\mathbf{a}) + \mathbf{a}\]In the inverse MixColumns, there are 3 other multiplications:
- Multiply by \(\texttt{09}\):
- Multiply by \(\texttt{11}\):
- Multiply by \(\texttt{13}\):
- Multiply by \(\texttt{14}\):
For implementation, we can reuse the computations in order to avoid recomputing the same thing multiple times. For example, \(\texttt{14}\cdot \mathbf{a}\),
def mul14(a):
u = xtime(a)
v = xtime(u)
t = xtime(v)
return u ^ v ^ t
That’s it! Enjoy coding!