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:

+

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^{2} mod m

x^{2} + x mod m

x + 1

0

x + 1

x^{2} + x mod m

x^{2} + 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.

x^{2}

0

x

x

1

x^{2} + 1

1

x + 1

x + 1

0

x^{2} + x

x

0

0

x + 1

x^{2} + x + 1

x + 1

1

1

x

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:

+

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

## 5 thoughts on “Addition and multiplication table for GF(2²)”