Addition and multiplication table for GF(2²)

Addition and multiplication table for GF(2²)

  • Comments 5

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(28). 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(22).

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:

+ 0 1 x x + 1
0 0 1 x x + 1
1 1 0 x + 1 x
x x x + 1 0 1
x + 1 x + 1 x 1 0
 
0 1 x x + 1
0 0 0 0 0
1 0 1 x x + 1
x 0 x x2 mod m x2 + x mod m
x + 1 0 x + 1 x2 + x mod m x2 + 1 mod m

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.

x2
0 x
x 1
x2 + 1
1 x + 1
x + 1 0
x2 + x
x 0
0 x + 1
x2 + x + 1
x + 1 1
1 x

Note that the first three polynomials all factor into products of lower-degree polynomials: x2 = x(x), x2 + 1 = (x + 1)(x + 1), x2 + x = x(x + 1). Only x2 + 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:

+ 0 1 x x + 1
0 0 1 x x + 1
1 1 0 x + 1 x
x x x + 1 0 1
x + 1 x + 1 x 1 0
 
0 1 x x + 1
0 0 0 0 0
1 0 1 x x + 1
x 0 x x + 1 1
x + 1 0 x + 1 1 x

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:

+ 00 01 10 11
00 00 01 10 11
01 01 00 11 10
10 10 11 00 01
11 11 10 01 00
 
00 01 10 11
00 00 00 00 00
01 00 01 10 11
10 00 10 11 01
11 00 11 01 10

Rijndael works in GF(28) and uses a reduction polynomial of x8 + x4 + x3 + x + 1. They say this is prime. I sure hope so.

Leave a Comment
  • Please add 8 and 4 and type the answer here:
  • Post
  • 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.

Page 1 of 1 (5 items)