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.

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

- 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:
- If the low bit of
**b**is set, exclusive or the product**p**by the value of**a** - Keep track of whether the high (eighth from left) bit of
**a**is set to one - Rotate
**a**one bit to the left, discarding the high bit, and making the low bit have a value of zero - If
**a**'s hi bit had a value of one prior to this rotation, exclusive or**a**with the hexadecimal number`0x1b` - Rotate
**b**one bit to the right, discarding the low bit, and making the high (eighth from left) bit have a value of zero.

- If the low bit of
- The product
**p**now has the product of**a**and**b**

- Product is made zero
- a is seven
- b is three
- 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

- 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

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; }

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 exponeniated 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

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.

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

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.

/* 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 consistant 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.

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

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)

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