Addition and multiplication table for GF(2²)

Addition and multiplication table for GF(2²)

  • Comments 7

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 2 and 7 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.

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

Page 1 of 1 (7 items)