The operation xtime

The multiplications in $\mathbb{F}_{2^{8}}$ necessary to compute the transformation MixColumn are of great importance to our implementation. Therefore we are going to describe them in more detail. First we need to say a few words about the representation of the field $\mathbb{F}_{2^{8}}$. In AES the field $\mathbb{F}_{2^{8}}$ is represented as

$$\mathbb{F}_{2^{8}}=\mathbb{F}_2[x]/(x^8+x^4+x^3+x+1).$$ (2)

That is, elements of $\mathbb{F}_{2^{8}}$ are polynomials over $\mathbb{F}_2$ of degree at most $7$. The addition and multiplication of two polynomials is done modulo the polynomial $x^8+x^4+x^3+x+1$. Since this is an irreducible polynomial over $\mathbb{F}_2$, (2) defines a field. In this representation of $\mathbb{F}_{2^{8}}$ the byte ${\bf a}=(a_7,\ldots, a_1,a_0)$ corresponds to the polynomial $a_7x^7+\cdots a_1 x+a_0$. The multiplication of an element ${\bf a}=(a_7,\ldots, a_1,a_0)$ in $\mathbb{F}_{2^{8}}$ by $01,02$, and $03$ is realized by multiplying the polynomial $a_7x^7+\cdots a_1 x+a_0$ with the polynomials $1, x, x+1$, respectively, and reducing the result modulo $x^8+x^4+x^3+x+1$. Hence

$$01\cdot {\bf a} = {\bf a}$$

$$03\cdot {\bf a} = 02\cdot {\bf a}+{\bf a}.$$

We see that the only non-trivial multiplication needed to multiply a column of a state by the matrix in (1) is the multiplication by $02$. Following the notation in [DR2] we denote the multiplication of byte ${\bf a}$ by $02$ by ${\tt xtime}({\bf a})$. The crucial observation is that ${\tt xtime}({\bf a})$ is simply a shift of byte ${\bf a}$, followed in some cases by an xor of two bytes. More precisely, for ${\bf a}=(a_7,\ldots ,a_0)$

$$\begin{array}{l} {\tt xtime}({\bf a})=\left\{\begin{array}{ll... ... & \\ \quad \textrm{if $a_7=1$} \end{array}\right. \end{array}$$

This finishes our brief description of the AES encryption procedure. In a pure software implementation of the algorithm on an 8051 based $\mu$-controller these transformations are performed one after the other within the CPU using 48 bytes of directly addressable internal RAM, and taking roughly 12000 clock cycles to encrypt a 128 bit data block with a 128-bit key. The decryption algorithm takes about 30% more time than the cipher and requires at least the same bytes of internal RAM resources. This is due to the fact that the software implementation of the inverse MixColumn transformation used for decryption is less efficient than the MixColumn transformation used for encryption.