Generator for the Galois field

As I wrote in the previous post, I've been working on cryptography, AES and trying to understand a little about Galois fields.  I found this page on the web terrific (part of a book that I hope to get to).

It remains even though it is marked obsolete (thank you).  One cool thing it contains is a graphic method for carrying out multiplication in the Galois field used for AES.  It makes it much easier to understand the mod operation.

I did some examples by hand and made a lot of mistakes, so I spent the morning writing a Python script to do it.  There isn't anything great about the script, it is really just tedious formatting detail, but I think the ouput is great:

Here is the output for one random run:

> python wagner.py

6,4,3,2 * 7,6,5,2

-----------------

      13    11 10 9                   = 7 * (6,4,3,2)

         12    10 9 8                 = 6 * (6,4,3,2)

            11    9 8 7               = 5 * (6,4,3,2)

                    8   6 5 4         = 2 * (6,4,3,2)

      13 12       9 8 7 6 5 4           XOR

      13 12       9 8 7 6 5 4        

      13          9 8   6 5           = 5 * (8,4,3,1,0)

         12           7     4           XOR

         12         8 7   5 4         = 4 * (8,4,3,1,0)

                    8     5             XOR

                    8       4 3   1 0 = 0 * (8,4,3,1,0)

                          5 4 3   1 0   XOR

[6, 4, 3, 2] 5c

[7, 6, 5, 2] e4

We see that a random number (6,4,3,2) in this system is equal to 0b 0101 1100 which is equal to hex 0x5c, while the other random number (7,6,5,2) is equal to 0b 1110 0100 or hex 0xe4.

I wrote a little script to multiply values input on the command line:

> python multiply.py hex 5c e4

x 92 y 228 p 59 3b

The multiplication is done in decimal, so those values are printed as well, but the hex result is 0x3b.  Check that against (5,4,3,1,0), in binary 0011 1011, and in hex that is indeed 0x3b.

For the other example I took two numbers that I know to be multiplicative inverses in the field:

6,4,1,0 * 7,6,3,1

-----------------

      13    11      8 7               = 7 * (6,4,1,0)

         12    10     7 6             = 6 * (6,4,1,0)

                  9   7     4 3       = 3 * (6,4,1,0)

                      7   5     2 1   = 1 * (6,4,1,0)

      13 12 11 10 9 8   6 5 4 3 2 1     XOR

      13 12 11 10 9 8   6 5 4 3 2 1  

      13          9 8   6 5           = 5 * (8,4,3,1,0)

         12 11 10           4 3 2 1     XOR

         12         8 7   5 4         = 4 * (8,4,3,1,0)

            11 10   8 7   5   3 2 1     XOR

            11        7 6   4 3       = 3 * (8,4,3,1,0)

               10   8   6 5 4   2 1     XOR

               10       6 5   3 2     = 2 * (8,4,3,1,0)

                    8       4 3   1     XOR

                    8       4 3   1 0 = 0 * (8,4,3,1,0)

                                    0   XOR

[6, 4, 1, 0] 53

[7, 6, 3, 1] ca

> python multiply.py hex 53 ca

x 83 y 202 p 1 01

>

We get hex 0x01 for the result, 0x53 and 0xca are indeed multiplicative inverses.

One reason I know they are is here:

It has been great fun getting to know about generators as well as making and using tables of powers, logarithms and multiplicative inverses.

The github repo is here.