4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Understanding multiplication in the AES specification $\endgroup$ – kodlu May 17 '18 at 22:47
  • $\begingroup$ @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. $\endgroup$ – Nilesh May 18 '18 at 4:07
  • $\begingroup$ 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? $\endgroup$ – e-sushi May 19 '18 at 8:59
  • $\begingroup$ @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. $\endgroup$ – Nilesh May 19 '18 at 10:59
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually I got the mathematical part, I mentioned this in the post. I was having trouble with the xor implementation, I am writing code for AES so I want to understand the xor implementation. Please explain that if you can, I'll be grateful for that. Thanks $\endgroup$ – Nilesh May 18 '18 at 14:27
  • 1
    $\begingroup$ @Nilesh When I wanted to implement AES I used Lookup-table method. Recently, I saw this vedio that the author has said in the last slide "Forget the finite field". You can see his article here. I mean, if you want to start the implementation of AES, I strongly recommended to learn the heuristics algorithm to construct lightweight MDS matrices without using XOR. Please be curious to find better results(here) $\endgroup$ – user0410 May 18 '18 at 19:04
  • 1
    $\begingroup$ Sure, it sounds good, I'll check. $\endgroup$ – Nilesh May 19 '18 at 3:49
  • $\begingroup$ @Nilesh The question is edited. $\endgroup$ – user0410 May 19 '18 at 15:18
  • $\begingroup$ Why down vote? Please tell me its reason. Thanks $\endgroup$ – user0410 May 21 '18 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.