I'm studying AES, and I'm having problems with the MixColumns step.

I read about finite fields, but I still don't know how it works.

  1. How do I construct $GF(2^8)$?

  2. 01010011 * 11001010 = 10001110 -> This is the original answer which I saw in a text. I multiplied both numbers, then I got 011111101111110. Now I know I should divide it with the irreducible number which is 100011011. But I don't get the real answer!

  3. I don't know how to write code for such a division. Are we actually taking the XOR (according with my knowledge)?

Can anyone explain, with a simple example, the full MixColumns step?


1 Answer 1


What is Rijndael's finite field?

Rijndaels finite field is $F=\mathrm{GF}(2^8)$ with minimal polynomial $f(x)=x^8 + x^4 + x^3 + x + 1$. Formally, we have $F=\mathbb F_2[x] / (f)$ but don't worry about that. So what does this mean?

Well, elements of $F$ should be thought of as polynomials over $\mathbb{F}_2$, with the added fact that the minimal polynomial is zero. Because the coefficients are all elements of $\mathbb F_2$, we have that $1=-1$, and so: $$f(x)=0\iff x^8+x^4+x^3+x+1=0\iff x^8=x^4+x^3+x+1$$ Think of this last fact as a 'rewrite rule', because that's how we're going to implement it. To add or multiply two numbers, you simply add/multiply them as you would normally, then reduce any powers greater than $x^7$ using the rewrite rule, and any coefficients greater than $1$ using $2=0$.

How does this relate to the bytes in my code?

The first representation we learn about when programming is that of an unsigned integer. To view a bytes as an element of $F$, we let the $n^{th}$ bit be the coefficient of $x^n$, numbering from the right. For example, $10010011\mapsto x^7+x^4+x+1$. Now we can do maths with them as we would in the finite field.

So, how do I actually add/subtract two numbers?

Simply take their xor. Addition is the same as subtraction because $1=-1$.

How do I multiply two numbers?

To multiply bytes $a$ and $b$, we first initialize a variable to hold the product. Checking the least significant bit of $b$, if it is $1$ then we add $a$ to our product (this is what you'd do for multiplication as a child). Then, we shift $a$ left (ie we multiply it by $x$) and $b$ right (dividing it by $x$). So, the least significant bit of $b$ is actually the coefficient of $x$ from the original value, but because we've multiplied $a$ by $x$, we'll still get the right answer. However, before we loop, we apply the rewrite rule to make sure $a$ (which is now $ax$) has no powers of $x$ greater than $x^7$.

Below is the example code from wikipedia, with my own comments.

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0;    /* init product value */
    uint8_t counter;  /* init loop counter */
    uint8_t carry;    /* init carry variable for checking if ax has an x^8 term */
    for (counter = 0; counter < 8; counter++) { /* for each of the 8 bits in b */
        if (b & 1) /* if the least significant bit is set */
            p ^= a; /* add a to p */
        carry = a & 0x80;  /* Set carry to the x^7 term of a */
        a <<= 1;           /* Shift a left 1, turning a into a*x */
        if (carry)         /* if ax should have had an x^8 term (x^7*x=x^8) */
                  /* Using rewrite rule, turn x^8 into x^4+x^3+x+1
                                                          =00011011=0x001B  */
            a ^= 0x001B; /* Add this on to a, so a now stores ax */
        b >>= 1;  /* right shift b, so the least significant bit is coef of x */
    }   /* end loop, and since b=b/x, a=ax; loop will now add on a*x if required */
    return p;  /* finally, return the product */

Having just written those comments in, it might be easier to think of the carry variable as ax_has_xxxxxxxx_term

Multiplication worked example: $m=01010011,n=00011010$. Calculate $m*n$

Initialize with $a:=m=01010011$, $b:=n=00011010$ and $p:=0$.

The last bit of $b$ is unset, so we do not add $a$ to $p$.
Now, we set $a:=m*x=10100110$ and $b:=(n>>1)=00001101$. $a$ fits within $8$ bits (there was no carry) so this iteration is finished.

Last bit of $b$ is set, so set $p:=p+a=10100110$.
Set $a:=a*x=m*x^2=01001100$ carry $1$; $b:=(n>>2)=110$.
We had to carry because $mx^2$ had a term in $x^8$. So, we turn this into $x^4+x^3+x+1 =00011011$ with rewrite rule and add it to $a$:
$a := a + 00011011 = 01001100 + 00011011 = 01010111$

Last bit of $b$ is not set, so we don't add.
Set $a:=a*x=m*x^3=(01010111<<1)=10101110$ with no carry; $b=11$. No carry so this iteration is done.

Last bit of $b$ is set, so $p:=p+a=10101110+10100110=00001000$
Set $a:=a*x=(10101110<<1)=01011100$ carry 1; $b:=b>>1=1$.
Was a carry, so using rewrite rule again we have that $a := a + 00011011 = 01011100 + 00011011 = 01000111 = m*x^4$

Last bit of $b$ set, so $p:=p+a=00001000+01000111 = 01001111$ Since $b:=0$ this is the last iteration and we are done.

Solution $p=01001111$.

  • $\begingroup$ please show me how do you multiply 01010011 * 11001010 ? i need a practical example more than a theoretical example . $\endgroup$
    – Melvin
    Commented Jan 13, 2014 at 2:35
  • $\begingroup$ Written out a shorter example, but there may well be errors (hopefully if anyone sees them they'll edit it out but who knows) $\endgroup$ Commented Jan 13, 2014 at 3:47
  • $\begingroup$ i got the idea. now am asking how do we find out the irreducible binary number like 11011 for GF(2^3) ? 2) how will we create multiplication table for GF(2^8)? GF(2^3)? $\endgroup$
    – Melvin
    Commented Jan 15, 2014 at 15:01
  • $\begingroup$ it sounds like we've solved your problem then? if so, remember to mark an accepted answer. your new question of "how do I find a minimal polynomial for $ GF (2^k) $ should be asked as a new question in my opinion $\endgroup$ Commented Jan 15, 2014 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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