How is multiplication in field $GF(2^{8})$ done?

Question

I am working on AES and I am stuck on multiplication in $GF(2^{8})$ field.

In terms of polynomial it is easy; I just have to multiply polynomials modulo $(x^{8} + x^{4} + x^{3} + x + 1)$. But I do not understand multiplication with $x$, following an example given in NIST specification:

{57} • {13} = {fe}

solution:

{57} • {02} = xtime({57}) = {ae}
{57} • {04} = xtime({ae}) = {47}
{57} • {08} = xtime({47}) = {8e}
{57} • {10} = xtime({8e}) = {07},

thus

{57} • {13} = {57} • ({01} $XOR$ {02} $XOR$ {10})
= {57} $XOR$ {ae} $XOR$ {07}
= {fe}

I am unable to understand a single step in this, please also explain the x_time() function too.

Also, how is $x^{i}$ calculated? I need this for the $rcon[i]$ matrix.

Edit: this question has been marked as a possible duplicate of Understanding multiplication in the AES specification. I have already read this but the explanation is not sufficient, I am unable to understand the concept hence I have posted this question, because I need a somewhat detailed answer.Thanks.

Answer 1

Consider we want to obtain $\mathtt{0x57} \cdot \mathtt{0x02}$. First we see this one by polynomial method $$ \begin{array}{lcl}\tag{3} \mathtt{0x57} \cdot \mathtt{0x02}&=&(01010111)_2 \cdot (00000010)_2\\ &=&({x}^{6}+{x}^{4}+{x}^{2}+x+1)\cdot x\\ &=&{x}^{7}+{x}^{5}+{x}^{3}+x^2+x \\ &=& (10101110)_2\\ &=& \mathtt{0xAE} \end{array} $$ The relation $(3)$ means that when an element of $\alpha \in\operatorname{GF}(2^8)$ multiplied by an element $\mathtt{0x02}$ we shift the binary mode of $\alpha$ in the left side.

Now, if the first bit (from left) of $\alpha$ is $1$ we should $\operatorname{XOR}$ the results with $\mathtt{0x1B}= (00011011)_2$ since when the first bit is $1$, it means we have $x^7$ in the representation of $\alpha$ and by multiplying by $x$ we get $x^8$ and we use the polynomial $x^4+x^3+x+1$ instead of $x^8$ in our calculation.

We call this operation x_time(). For instance, let we want to get $\mathtt{0x57} \cdot \mathtt{0x04}$. The element $\mathtt{0x04}=(00000100)_2$ is equal to $x^2$. Therefor to obtain $\mathtt{0x57} \cdot \mathtt{0x04}$ we use the function x_time() two times. In $(3)$ we got $\mathtt{0x57} \cdot \mathtt{0x02}=\mathtt{0xAE}$.

In the rest, to obtain $\mathtt{0xAE} \cdot \mathtt{0x02}$, first we shift the binary mode of $\mathtt{0xAE}=(10101110)_2$ in the left side that implying that $$ (10101110)_2 \stackrel{shift\, to\, left}{\Longrightarrow} (01011100)_2 \tag{4} $$ The first bit of $\mathtt{0xAE}=(10101110)_2$ is $1$ and hence we $\operatorname{XOR}$ the result obtained in $(4)$, with $(00011011)_2$ as follows $$ (01011100)_2 \quad \operatorname{XOR}\quad (00011011)_2=(01000111)_2=71=\mathtt{0x47} $$ I suggest you to obtain other cases as an exercise.