AES' Galois field

Rijndael (a.k.a AES) uses what is known as a galois field to perform a good deal of its mathematics. This is a special mathematical construct where addition, subtraction, multiplication, and division are redefined, and where there are a limited number of integers in the field.

In more detail, Rijndael's galois field only allows an 8 bit number (a number from 0 to 255) to fit in it. All mathematical operations defined in the field result in an 8-bit number. The rest of this document will describe how various mathematical operations are performed.

Addition and subtraction

Addition and subtraction are performed by the exclusive or operation. The two operations are the same; there is no difference between addition and subtraction.

Example

unsigned char gadd(unsigned char a, unsigned char b) {
	return a ^ b;
}

unsigned char gsub(unsigned char a, unsigned char b) {
	return a ^ b;
}

Multiplication

Multiplication in Rijndael's galois field is a little more complicated. The procedure is as follows:

Take two eight-bit numbers, a and b, and an eight-bit product p
Set the product to zero.
Make a copy of a and b, which we will simply call a and b in the rest of this algorithm
Run the following loop eight times:
1. If the low bit of b is set, exclusive or the product p by the value of a
2. Keep track of whether the high (eighth from left) bit of a is set to one
3. Rotate a one bit to the left, discarding the high bit, and making the low bit have a value of zero
4. If a's hi bit had a value of one prior to this rotation, exclusive or a with the hexadecimal number 0x1b
5. Rotate b one bit to the right, discarding the low bit, and making the high (eighth from left) bit have a value of zero.
The product p now has the product of a and b

Clear as mud? OK, let me go over a simple example, where I multiply seven by three:

Product is made zero
a is seven
b is three
1. - Low bit of b is one. Product is made seven as a result
  - a, which is seven, is rotated one bit to the left. This makes a have a value of 14
  - The high bit of a is not set (a is below 128), so a is not xored with 0x1b (27)
  - b is rotated one bit to the right. b now has a value of one
2. - Low bit of b is one. Product, which was seven, is made 7 xor 14, which has a value of nine.
  - a, which is 14, is rotate one bit to the left. This makes a have a value of 28
  - The high bit of a is not set (a is below 128), so a is not xored with 0x1b (27)
  - b is rotated one bit to the right. b now has a value of zero
While there are six more steps, none of them will affect the product b, so I will discard them in this example. Note that, if this method of multiplying two numbers together is used in the real world, the six steps should be performed in order to protect key information from being leaked via a timing attack.
The final product, nine, is returned

Here is some code which multiplies a by b:

unsigned char gmul(unsigned char a, unsigned char b) {
	unsigned char p = 0;
	unsigned char counter;
	unsigned char hi_bit_set;
	for(counter = 0; counter < 8; counter++) {
		if((b & 1) == 1) 
			p ^= a;
		hi_bit_set = (a & 0x80);
		a <<= 1;
		if(hi_bit_set == 0x80) 
			a ^= 0x1b;		
		b >>= 1;
	}
	return p;
}

Exponents and logarithms

Exponentiation is done by repeated multiplication of the same number. With some, but not all, numbers in Rijndael's galois field, it is possible to traverse all possible values in the galois field except zero via exponentiation. Numbers for which this is possible are called generators. Rijndael's galois field has the following generators:

3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 78 79 82 84 86 87 88 89 90 91 95 100 101 104 105 109 110 112 113 118 119 121 122 123 126 129 132 134 135 136 138 142 143 144 147 149 150 152 153 155 157 160 164 165 166 167 169 170 172 173 178 180 183 184 185 186 190 191 192 193 196 200 201 206 207 208 214 215 218 220 221 222 226 227 229 230 231 233 234 235 238 240 241 244 245 246 248 251 253 254 255

These same numbers can also be expressed in hexadecimal:

03 05 06 09 0b 0e 11 12 13 14 17 18 19 1a 1c 1e 
1f 21 22 23 27 28 2a 2c 30 31 3c 3e 3f 41 45 46 
47 48 49 4b 4c 4e 4f 52 54 56 57 58 59 5a 5b 5f 
64 65 68 69 6d 6e 70 71 76 77 79 7a 7b 7e 81 84 
86 87 88 8a 8e 8f 90 93 95 96 98 99 9b 9d a0 a4 
a5 a6 a7 a9 aa ac ad b2 b4 b7 b8 b9 ba be bf c0 
c1 c4 c8 c9 ce cf d0 d6 d7 da dc dd de e2 e3 e5 
e6 e7 e9 ea eb ee f0 f1 f4 f5 f6 f8 fb fd fe ff

When any of these numbers is exponentiated multiple times, the original number is reached again after 255 exponentiations. For example, here is a chart, in hexadecimal notation, of the number 0xe5 being exponentiated 255 times:

               | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|
            ---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
            00 |01 e5 4c b5 fb 9f fc 12 03 34 d4 c4 16 ba 1f 36| 00
            10 |05 5c 67 57 3a d5 21 5a 0f e4 a9 f9 4e 64 63 ee| 10
            20 |11 37 e0 10 d2 ac a5 29 33 59 3b 30 6d ef f4 7b| 20
            30 |55 eb 4d 50 b7 2a 07 8d ff 26 d7 f0 c2 7e 09 8c| 30
            40 |1a 6a 62 0b 5d 82 1b 8f 2e be a6 1d e7 9d 2d 8a| 40
            50 |72 d9 f1 27 32 bc 77 85 96 70 08 69 56 df 99 94| 50
            60 |a1 90 18 bb fa 7a b0 a7 f8 ab 28 d6 15 8e cb f2| 60
            70 |13 e6 78 61 3f 89 46 0d 35 31 88 a3 41 80 ca 17| 70
            80 |5f 53 83 fe c3 9b 45 39 e1 f5 9e 19 5e b6 cf 4b| 80
            90 |38 04 b9 2b e2 c1 4a dd 48 0c d0 7d 3d 58 de 7c| 90
            a0 |d8 14 6b 87 47 e8 79 84 73 3c bd 92 c9 23 8b 97| a0 
            b0 |95 44 dc ad 40 65 86 a2 a4 cc 7f ec c0 af 91 fd| b0
            c0 |f7 4f 81 2f 5b ea a8 1c 02 d1 98 71 ed 25 e3 24| c0
            d0 |06 68 b3 93 2c 6f 3e 6c 0a b8 ce ae 74 b1 42 b4| d0
            e0 |1e d3 49 e9 9c c8 c6 c7 22 6e db 20 bf 43 51 52| e0
            f0 |66 b2 76 60 da c5 f3 f6 aa cd 9a a0 75 54 0e 01| f0 
            ---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
               | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|

In this chart, numbers are being multiplied left to right. Once the right end of the row is reached, we continue on the next row down.

In this chart, we see that 0x01 multiplied by 0xe5 becomes 0xe5. 0xe5 multiplied by 0xe5 becomes 0x4c. 0x4c multiplied by 0xe5 becomes 0xb5. Eventually, after doing this 15 times, we get 0x36. 0x36 multiplied by 0xe5 becomes 0x05. Much later, 0x0e multiplied by 0xe5 becomes 0x01.

Now that we have built an exponentiation chart, we can build the corresponding logarithm chart:

               | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|
            ---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
            00 |-- 00 c8 08 91 10 d0 36 5a 3e d8 43 99 77 fe 18| 00
            10 |23 20 07 70 a1 6c 0c 7f 62 8b 40 46 c7 4b e0 0e| 10
            20 |eb 16 e8 ad cf cd 39 53 6a 27 35 93 d4 4e 48 c3| 20
            30 |2b 79 54 28 09 78 0f 21 90 87 14 2a a9 9c d6 74| 30
            40 |b4 7c de ed b1 86 76 a4 98 e2 96 8f 02 32 1c c1| 40
            50 |33 ee ef 81 fd 30 5c 13 9d 29 17 c4 11 44 8c 80| 50
            60 |f3 73 42 1e 1d b5 f0 12 d1 5b 41 a2 d7 2c e9 d5| 60
            70 |59 cb 50 a8 dc fc f2 56 72 a6 65 2f 9f 9b 3d ba| 70
            80 |7d c2 45 82 a7 57 b6 a3 7a 75 4f ae 3f 37 6d 47| 80
            90 |61 be ab d3 5f b0 58 af ca 5e fa 85 e4 4d 8a 05| 90
            a0 |fb 60 b7 7b b8 26 4a 67 c6 1a f8 69 25 b3 db bd| a0
            b0 |66 dd f1 d2 df 03 8d 34 d9 92 0d 63 55 aa 49 ec| b0
            c0 |bc 95 3c 84 0b f5 e6 e7 e5 ac 7e 6e b9 f9 da 8e| c0
            d0 |9a c9 24 e1 0a 15 6b 3a a0 51 f4 ea b2 97 9e 5d| d0
            e0 |22 88 94 ce 19 01 71 4c a5 e3 c5 31 bb cc 1f 2d| e0
            f0 |3b 52 6f f6 2e 89 f7 c0 68 1b 64 04 06 bf 83 38| f0 
            ---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
               | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f|

In this chart, we can see how many times we need to multiply 0xe5 by itself to get any non-zero number in the galois field. Because this is a logarithm chart, the value for 0xe5 will have a value of one, and all other values is the number of times one multiplies 0xe5 by itself to get the desired number, minus one.

To get a number on this chart, add the hex value on the left to the hex value on the top (or bottom). For example, when one looks for 0x02 in the above chart, one sees the number 0xc8. This indicates that when 0xe5 is multiplied by itself 0xc7 (or 199) times, the number 2 is obtained. As you can see, if we go down to the e0 row and over above the number five on the bottom, we get the number 0x01, which corresponds to 0xe5--the generator for this table.

Using the log table to more quickly multiply numbers

Multiplication can be more quickly done with a 256-byte log table and 256-byte exponentiation table. For example, to multiply 0x03 by 0x07 using the above tables, we do the following:

Look up 0x03 on the log table. We get 0x08
Look up 0x07 on the log table. We get 0x36
Add up these two numbers together (using normal, not galois field, addition) mod 255. 0x08 + 0x36 = 0x3e
Look up the sum, 0x3e, on the exponentiation table. We get 0x09.

This method of multiplication requires 512 bytes of memory, but makes multiplication much faster. While this may not be needed for encryption (where the highest number we multiply by is three), it will speed up decryption (where the highest number we multiply by is 15).

Note that, while the galois field has 256 possible values, our log table is only has 255 entries. This is because 0 is a special case; anything multiplied by zero is always zero. The number zero, consequently, does not appear on our log table; there are only 255 entries.

This in mind, if there is an overflow when adding two numbers together on the log table, 255, instead of 256 is subtracted from the result. On eight bit systems, 1 has to be added to the number whenever overflow happens. This can usually be done by using an opcode that sets the carry flag whenever an 8-bit addition overflows, and adding one when the carry bit is set.

On a 6502, this is quite simple as this code snip shows:

	LDX A	; Load the X register with the first number we want to add
	LDY B   ; Load the Y register with the second number we want to add
	LDA #$200,X ; Page two has the log table
	ADC #$200,Y ; Add the second value to it
	ADC #0  ; We add one to the result in case of overflow (see above)
	TAX
	LDY #$300,X ; Page three has the antilog table		
	[We would add code to see if "A" or "B" is zero here]

Here the "ADC #0" means "Add zero to the value". However, if the previous "ADC" instruction ("Add the log of the B number to our sum") overflows, this will set the carry bit, which will add one to whatever we add in the second "ADC" instruction.

Example

/* Log table using 0xe5 (229) as the generator */
unsigned char ltable[256] = {
0x00, 0xff, 0xc8, 0x08, 0x91, 0x10, 0xd0, 0x36, 
0x5a, 0x3e, 0xd8, 0x43, 0x99, 0x77, 0xfe, 0x18, 
0x23, 0x20, 0x07, 0x70, 0xa1, 0x6c, 0x0c, 0x7f, 
0x62, 0x8b, 0x40, 0x46, 0xc7, 0x4b, 0xe0, 0x0e, 
0xeb, 0x16, 0xe8, 0xad, 0xcf, 0xcd, 0x39, 0x53, 
0x6a, 0x27, 0x35, 0x93, 0xd4, 0x4e, 0x48, 0xc3, 
0x2b, 0x79, 0x54, 0x28, 0x09, 0x78, 0x0f, 0x21, 
0x90, 0x87, 0x14, 0x2a, 0xa9, 0x9c, 0xd6, 0x74, 
0xb4, 0x7c, 0xde, 0xed, 0xb1, 0x86, 0x76, 0xa4, 
0x98, 0xe2, 0x96, 0x8f, 0x02, 0x32, 0x1c, 0xc1, 
0x33, 0xee, 0xef, 0x81, 0xfd, 0x30, 0x5c, 0x13, 
0x9d, 0x29, 0x17, 0xc4, 0x11, 0x44, 0x8c, 0x80, 
0xf3, 0x73, 0x42, 0x1e, 0x1d, 0xb5, 0xf0, 0x12, 
0xd1, 0x5b, 0x41, 0xa2, 0xd7, 0x2c, 0xe9, 0xd5, 
0x59, 0xcb, 0x50, 0xa8, 0xdc, 0xfc, 0xf2, 0x56, 
0x72, 0xa6, 0x65, 0x2f, 0x9f, 0x9b, 0x3d, 0xba, 
0x7d, 0xc2, 0x45, 0x82, 0xa7, 0x57, 0xb6, 0xa3, 
0x7a, 0x75, 0x4f, 0xae, 0x3f, 0x37, 0x6d, 0x47, 
0x61, 0xbe, 0xab, 0xd3, 0x5f, 0xb0, 0x58, 0xaf, 
0xca, 0x5e, 0xfa, 0x85, 0xe4, 0x4d, 0x8a, 0x05, 
0xfb, 0x60, 0xb7, 0x7b, 0xb8, 0x26, 0x4a, 0x67, 
0xc6, 0x1a, 0xf8, 0x69, 0x25, 0xb3, 0xdb, 0xbd, 
0x66, 0xdd, 0xf1, 0xd2, 0xdf, 0x03, 0x8d, 0x34, 
0xd9, 0x92, 0x0d, 0x63, 0x55, 0xaa, 0x49, 0xec, 
0xbc, 0x95, 0x3c, 0x84, 0x0b, 0xf5, 0xe6, 0xe7, 
0xe5, 0xac, 0x7e, 0x6e, 0xb9, 0xf9, 0xda, 0x8e, 
0x9a, 0xc9, 0x24, 0xe1, 0x0a, 0x15, 0x6b, 0x3a, 
0xa0, 0x51, 0xf4, 0xea, 0xb2, 0x97, 0x9e, 0x5d, 
0x22, 0x88, 0x94, 0xce, 0x19, 0x01, 0x71, 0x4c, 
0xa5, 0xe3, 0xc5, 0x31, 0xbb, 0xcc, 0x1f, 0x2d, 
0x3b, 0x52, 0x6f, 0xf6, 0x2e, 0x89, 0xf7, 0xc0, 
0x68, 0x1b, 0x64, 0x04, 0x06, 0xbf, 0x83, 0x38 };

/* Anti-log table: */
unsigned char atable[256] = {
0x01, 0xe5, 0x4c, 0xb5, 0xfb, 0x9f, 0xfc, 0x12, 
0x03, 0x34, 0xd4, 0xc4, 0x16, 0xba, 0x1f, 0x36, 
0x05, 0x5c, 0x67, 0x57, 0x3a, 0xd5, 0x21, 0x5a, 
0x0f, 0xe4, 0xa9, 0xf9, 0x4e, 0x64, 0x63, 0xee, 
0x11, 0x37, 0xe0, 0x10, 0xd2, 0xac, 0xa5, 0x29, 
0x33, 0x59, 0x3b, 0x30, 0x6d, 0xef, 0xf4, 0x7b, 
0x55, 0xeb, 0x4d, 0x50, 0xb7, 0x2a, 0x07, 0x8d, 
0xff, 0x26, 0xd7, 0xf0, 0xc2, 0x7e, 0x09, 0x8c, 
0x1a, 0x6a, 0x62, 0x0b, 0x5d, 0x82, 0x1b, 0x8f, 
0x2e, 0xbe, 0xa6, 0x1d, 0xe7, 0x9d, 0x2d, 0x8a, 
0x72, 0xd9, 0xf1, 0x27, 0x32, 0xbc, 0x77, 0x85, 
0x96, 0x70, 0x08, 0x69, 0x56, 0xdf, 0x99, 0x94, 
0xa1, 0x90, 0x18, 0xbb, 0xfa, 0x7a, 0xb0, 0xa7, 
0xf8, 0xab, 0x28, 0xd6, 0x15, 0x8e, 0xcb, 0xf2, 
0x13, 0xe6, 0x78, 0x61, 0x3f, 0x89, 0x46, 0x0d, 
0x35, 0x31, 0x88, 0xa3, 0x41, 0x80, 0xca, 0x17, 
0x5f, 0x53, 0x83, 0xfe, 0xc3, 0x9b, 0x45, 0x39, 
0xe1, 0xf5, 0x9e, 0x19, 0x5e, 0xb6, 0xcf, 0x4b, 
0x38, 0x04, 0xb9, 0x2b, 0xe2, 0xc1, 0x4a, 0xdd, 
0x48, 0x0c, 0xd0, 0x7d, 0x3d, 0x58, 0xde, 0x7c, 
0xd8, 0x14, 0x6b, 0x87, 0x47, 0xe8, 0x79, 0x84, 
0x73, 0x3c, 0xbd, 0x92, 0xc9, 0x23, 0x8b, 0x97, 
0x95, 0x44, 0xdc, 0xad, 0x40, 0x65, 0x86, 0xa2, 
0xa4, 0xcc, 0x7f, 0xec, 0xc0, 0xaf, 0x91, 0xfd, 
0xf7, 0x4f, 0x81, 0x2f, 0x5b, 0xea, 0xa8, 0x1c, 
0x02, 0xd1, 0x98, 0x71, 0xed, 0x25, 0xe3, 0x24, 
0x06, 0x68, 0xb3, 0x93, 0x2c, 0x6f, 0x3e, 0x6c, 
0x0a, 0xb8, 0xce, 0xae, 0x74, 0xb1, 0x42, 0xb4, 
0x1e, 0xd3, 0x49, 0xe9, 0x9c, 0xc8, 0xc6, 0xc7, 
0x22, 0x6e, 0xdb, 0x20, 0xbf, 0x43, 0x51, 0x52, 
0x66, 0xb2, 0x76, 0x60, 0xda, 0xc5, 0xf3, 0xf6, 
0xaa, 0xcd, 0x9a, 0xa0, 0x75, 0x54, 0x0e, 0x01 };

unsigned char gmul(unsigned char a, unsigned char b) {
	int s;
	int q;
	int z = 0;
	s = ltable[a] + ltable[b];
	s %= 255;
	/* Get the antilog */
	s = atable[s];
	/* Now, we have some fancy code that returns 0 if either
           a or b are zero; we write the code this way so that the
           code will (hopefully) run at a constant speed in order to
           minimize the risk of timing attacks */
	q = s;
	if(a == 0) {
		s = z;
	}
	else {
		s = q;
	}
	if(b == 0) {
		s = z;
	} 
	else {
		q = z;
	}
	return s;
}

As you can see, at the expense of 512 bytes to store tables, we can much more quickly, and at a more consistent speed, multiply two numbers together in Rijndael's galois field.

For people who prefer to use a different generator for the log and antilog tables, Here are tables for all 128 possible generators in Rijndael's galois field (140K text file)

It is also possible to dynamically generate a log and antilog table using three as the generator without needing gmul already defined thusly:

void generate_tables() {
        unsigned char c;
        unsigned char a = 1;
        unsigned char d;
        for(c=0;c<255;c++) {
                atable[c] = a;
                /* Multiply by three */
                d = a & 0x80;
                a <<= 1;
                if(d == 0x80) {
                        a ^= 0x1b;
                }
                a ^= atable[c];
		/* Set the log table value */
                ltable[atable[c]] = c;
        }
        atable[255] = atable[0];
        ltable[0] = 0;
}

This is possible because a multiply by three in Rijndael's Galois field is simply a multiply by two exclusive ored with the value we are multiplying by.

Division

Dividing a by b in Rijndael's galois field is performed by taking the logarithm of a and subtracting the logarithm of b from it, modulo 255.

In particular, when a (the numerator) is one, division is done by taking the logarithm of a, which can be represented as the number 255, and subtracting the logarithm of b from 255.

Multiplicative inverse

One divided by a given number is the multiplicative inverse of that number. To find the multiplicative inverse of the number a:

Find the logarithm for a
Subtract 255 by a's logarithm
Take the anti-log of the resulting number
This is the multiplicative inverse (In other words, 1 / a)

Here is some code which uses the above log and anti-log tables to calculate the multiplicative inverse:

unsigned char gmul_inverse(unsigned char in) {
	/* 0 is self inverting */
	if(in == 0) 
		return 0;
	else
        	return atable[(255 - ltable[in])];
}

Here is a table of all of the multiplicative inverses in Rijndael's Galois field:

   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
00 |-- 01 8d f6 cb 52 7b d1 e8 4f 29 c0 b0 e1 e5 c7 
10 |74 b4 aa 4b 99 2b 60 5f 58 3f fd cc ff 40 ee b2 
20 |3a 6e 5a f1 55 4d a8 c9 c1 0a 98 15 30 44 a2 c2 
30 |2c 45 92 6c f3 39 66 42 f2 35 20 6f 77 bb 59 19 
40 |1d fe 37 67 2d 31 f5 69 a7 64 ab 13 54 25 e9 09 
50 |ed 5c 05 ca 4c 24 87 bf 18 3e 22 f0 51 ec 61 17 
60 |16 5e af d3 49 a6 36 43 f4 47 91 df 33 93 21 3b 
70 |79 b7 97 85 10 b5 ba 3c b6 70 d0 06 a1 fa 81 82 
80 |83 7e 7f 80 96 73 be 56 9b 9e 95 d9 f7 02 b9 a4 
90 |de 6a 32 6d d8 8a 84 72 2a 14 9f 88 f9 dc 89 9a 
a0 |fb 7c 2e c3 8f b8 65 48 26 c8 12 4a ce e7 d2 62 
b0 |0c e0 1f ef 11 75 78 71 a5 8e 76 3d bd bc 86 57 
c0 |0b 28 2f a3 da d4 e4 0f a9 27 53 04 1b fc ac e6 
d0 |7a 07 ae 63 c5 db e2 ea 94 8b c4 d5 9d f8 90 6b 
e0 |b1 0d d6 eb c6 0e cf ad 08 4e d7 e3 5d 50 1e b3 
f0 |5b 23 38 34 68 46 03 8c dd 9c 7d a0 cd 1a 41 1c