# AES mixcolumn stage

I'm studying AES, and am having problems with the "mixcolumn" stage. I read about finite fields, but I still don't know.

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 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 mix-column stage?

### 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$.

• please show me how do you multiply 01010011 * 11001010 ? i need a practical example more than a theoretical example . – Melvin Jan 13 '14 at 2:35
• Written out a shorter example, but there may well be errors (hopefully if anyone sees them they'll edit it out but who knows) – Cryptographeur Jan 13 '14 at 3:47
• 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)? – Melvin Jan 15 '14 at 15:01
• 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 – Cryptographeur Jan 15 '14 at 15:07