Matthew van Eerde's web log
I am a Software Development Engineer in Test working for the Windows Sound team. You can contact me via email: mateer at microsoft dot com
Friend key: 28904932216450_59cd9d55374be03d8167d37c8ff4196b
I'm reading Joan Daemen and Vincent Rijmen's book The Design of Rijndael and I'm giving myself a refresher course on group theory.
Key to the encryption standard is the Galois field on 256 elements GF(2^{8}). A multiplication table of 256 elements by 256 elements quickly becomes a wall of text, so let's reason by analogy and look at GF(2^{2}).
There are a number of ways to represent elements of the field; we'll start by representing them as polynomials with degree at most 1, and with integer coefficients modulo 2. There are four such polynomials: {0, 1, x, x + 1}.
Here are the addition and multiplication tables:
Hold on. What's that funny-looking m?
It's a "reduction polynomial" which brings the product back down to degree 1 or less. It has to be a polynomial of degree 2. There are four such polynomials: let's try each and see what we get.
Note that the first three polynomials all factor into products of lower-degree polynomials: x^{2} = x(x), x^{2} + 1 = (x + 1)(x + 1), x^{2} + x = x(x + 1). Only x^{2} + x + 1 is prime; and this prime reduction polynomial generates a complete multiplication table with no 0s. This is a necessary condition to be a field. Our final tables are:
We can also write our elements in binary form: 0 => 00, 1 => 01, x => 10, and x + 1 => 11. In this notation our tables become:
Rijndael works in GF(2^{8}) and uses a reduction polynomial of x^{8} + x^{4} + x^{3} + x + 1. They say this is prime. I sure hope so.
Note that the + table for the binary notation is just XOR.
you suck!
Sorry I upset you; can you elaborate?
how to do that multiplication operation?
There are many ways to check that m(x) = x^8 + x^4 + x^3 + x + 1 is irreducible (prime). The one that is probably easiest to understand is as follows: every polynomial is a product of irreducible polynomials, so it suffices to produce a list of irreducible polynomials of degrees 1 up to 4 and to check by polynomial division that none of them divides m(x) without remainder. These polynomials are x, x+1, x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1, x^4 + x + 1, x^4 + x^3 + 1 and x^4 + x^3 + x^2 + x + 1. To verify this list, just write all the polynomials up to degree 4 down and check which ones are divisible by a polynomial of smaller degree.
Anyone can tell me
How we Construct a Multiplication table of GF(2^3)
@Muhammad Sami
(This comment is best viewed in a fixed-width font)
GF(2^3)
Addition is easy, as it is just XOR:
000 001 010 011 100 101 110 111
001 000 011 010 101 100 111 110
010 011 000 001 110 111 100 101
011 010 001 000 111 110 101 100
100 101 110 111 000 001 011 011
101 100 111 110 001 000 011 010
110 111 100 101 010 011 000 001
111 110 101 100 011 010 001 000
Multiplication: we need to find a reduction polynomial. See this post for using sieving to find all the monic prime polynomials for GF(p^n):
blogs.msdn.com/.../sieving-irreducible-monic-polynomials-over-a-finite-field.aspx
As it turns out, there are two possible reduction polynomials, which are those monic prime polynomials of degree n:
x^3 + x + 1
x^3 + x^2 + 1
We'll choose the smaller of the too: x^3 + x + 1. This induces the following multiplication table:
001 010 011 100 101 110 111
010 100 110 011 001 111 101
011 110 101 111 100 001 010
100 011 111 110 010 101 001
101 001 100 010 111 011 110
110 111 001 101 011 010 100
111 101 010 001 110 100 011
As an example, here's the calculation of the 100 * 100 = 110 entry:
x + 0 R x^2 + x + 0
+--------------
x^3 + 0x^2 + x + 1|x^4
x^4 + 0x^3 + x^2 + x + 0
0x^3 + x^2 + x + 0
Check:
x^4 =? x(x^3 + x + 1) + (x^2 + x + 0)
=? (x^4 + x^2 + x) + (x^2 + x)
= x^4
Yup.
If we had chosen x^3 + x^2 + 1, we would have gotten a different multiplication table, but the uniqueness of GF(p^n) implies that this is just a relabeling of the same eight elements.