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