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

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.

• Possible duplicate of Understanding multiplication in the AES specification – kodlu May 17 '18 at 22:47
• @kodlu I've checked this already, the answer you mentioned. But it didn't solved the problem, I can't understand the given explanation. Hence, I posted this question here. – Nilesh May 18 '18 at 4:07
• To clarify: when you say I am unable to understand a single step in this, please also explain the x_time() function too. – do you mean you have general problems with the basic math used there and expect answers to go though it step-by-step, or are you just having problems understanding what x_time() means/does? – e-sushi May 19 '18 at 8:59
• @e-sushi, I'm having problems with both, I can implement x_time() just by it's definition but the question I mentioned in the post, I can't understand the steps, e.g. {57} • {13} = {57} • {13} = {57} • ({01} XOR XOR {02} XOR XOR {10}) how this is inferred from the steps above it. – Nilesh May 19 '18 at 10:59

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.