Because every finite field of a given size is equivalent, any field with 256 elements always has the same universal properties. Galois, who died at age 20 in the chaos of post-Napoleon France, blazed the mathematical trail to much of this area, so we call the field with 256 elements GF(2

Weirdly, members of a field of size

Number |
Binary |
GF(2^{8})Polynomial |
Simplified |

0 |
0 |
0 |
0 |

1 |
1 |
1 |
1 |

2 |
10 |
1x+0 |
x |

3 |
11 |
1x+1 |
x+1 |

4 |
100 |
1x^{2}+0x+0 |
x^{2} |

5 |
101 |
1x^{2}+0x+1 |
x^{2}+1 |

8 |
1000 |
1x^{3}+0x^{2}+0x+0 |
x^{3} |

16 |
10000 |
1x^{4}+0x^{3}+0x^{2}+0x+0 |
x^{4} |

21 |
10101 |
1x^{4}+0x^{3}+1x^{2}+0x+1 |
x^{4}+x^{2}+1 |

Luckily, the mathematical structure is just there to compute the values of the substitution tables, or motivate some simple shifting and XOR work--we certainly don't have to "convert numbers to polynomials" at runtime, and we never actually evaluate the polynomials at any x.

1 + 2 = 1+10 = (1)+(1x+0) = 1x+1 = 11 = 3

Yet because we only have single-bit polynomial coefficients,

2 + 2 = 10+10 = (1x+0)+(1x+0) = 2x = 0x = 0

Because of this single-bit binary wraparound, it turns out that in GF(2

Here's an addition table for GF(2

0 1 2 3 4 5 6 7 8 9 a b c d e f 1 0 3 2 5 4 7 6 9 8 b a d c f e 2 3 0 1 6 7 4 5 a b 8 9 e f c d 3 2 1 0 7 6 5 4 b a 9 8 f e d c 4 5 6 7 0 1 2 3 c d e f 8 9 a b 5 4 7 6 1 0 3 2 d c f e 9 8 b a 6 7 4 5 2 3 0 1 e f c d a b 8 9 7 6 5 4 3 2 1 0 f e d c b a 9 8 8 9 a b c d e f 0 1 2 3 4 5 6 7 9 8 b a d c f e 1 0 3 2 5 4 7 6 a b 8 9 e f c d 2 3 0 1 6 7 4 5 b a 9 8 f e d c 3 2 1 0 7 6 5 4 c d e f 8 9 a b 4 5 6 7 0 1 2 3 d c f e 9 8 b a 5 4 7 6 1 0 3 2 e f c d a b 8 9 6 7 4 5 2 3 0 1 f e d c b a 9 8 7 6 5 4 3 2 1 0(Try this in NetRun now!)

Rather like Sudoku, for inverses to exist we need each output to appear in each row and column exactly once.

2*2=10*10= (1x+0)*(1x+0)=x*x=x

This works fine except for the problem of generating polynomial degrees higher than

In this case, we subtract off the reducing polynomial once:

16*16=x

...=x

Note that an even times an even *can* give you an odd this way!

The reduction operation gives multiplication in a finite field a strange flavor. For example, here's the 256-entry hex multiplication table (from Wikipedia) for multiplying by 2 (1x+0) in GF(2

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

Here's a multiplication table for GF(2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 2 4 6 8 a c e 3 1 7 5 b 9 f d 0 3 6 5 c f a 9 b 8 d e 7 4 1 2 0 4 8 c 3 7 b f 6 2 e a 5 1 d 9 0 5 a f 7 2 d 8 e b 4 1 9 c 3 6 0 6 c a b d 7 1 5 3 9 f e 8 2 4 0 7 e 9 f 8 1 6 d a 3 4 2 5 c b 0 8 3 b 6 e 5 d c 4 f 7 a 2 9 1 0 9 1 8 2 b 3 a 4 d 5 c 6 f 7 e 0 a 7 d e 4 9 3 f 5 8 2 1 b 6 c 0 b 5 e a 1 f 4 7 c 2 9 d 6 8 3 0 c b 7 5 9 e 2 a 6 1 d f 3 4 8 0 d 9 4 1 c 8 5 2 f b 6 3 e a 7 0 e f 1 d 3 2 c 9 7 6 8 4 a b 5 0 f d 2 9 6 4 b 1 e c 3 8 7 5 aThis is generated by the following code:

// Bitwise ("peasant") multiplication, using galois addition for (int bit=3;bit>=0;bit--) { if (b&(1<<bit)) c=c^(a<<bit); }For GF(2^8), the AES field, this is the multiplication table:

// Reduce back into galois field (can also be folded into above loop) int irr=0x13; // represents reduction polynomial int high=0x10; // high bit of above for (int bit=3;bit>=0;bit--) { if (c&(high<<bit)) // if that bit is set c=c^(irr<<bit); // galois "subtract" it off }

Note that forward multiplication is just a short algorithm, but it's weirdly nonlinear enough that division in a finite field is hard--typically you build a table of multiplicative inverses, and multiply by the inverse. You can also perform both multiplication and division efficiently by making a table of logarithms and antilogarithms. Tables work for these fields because there are only 256 elements!

- Each byte in the grid is run through an S-box. This consists of a multiplicative inverse, followed by an affine transformation--a series of additions and multiplies by 0 or 1. The affine transformation fixes the problem with 0 (no multiplicative inverse, so by convention 1/0=0), and messes up the mathematics so you can't string multiplicative inverses together.
- ShiftRows shifts each byte horizontally in the 4x4 grid.
Row
*i*is shifted circularly by*i*bytes. - MixColumns computes a linear
transformation on each column. A linear transformation is
just a series of finite field multiplications and additions. The
matrix used is invertible, so there's an inverse
operation. It's also chosen such that every output byte
changes if any single input byte changes.

- Finally, the round keys are added (the same operation as XOR in a finite field) to each byte.

- Numbers stay small--everything in GF(2
^{8}) is always one byte, even after multiplication or division. - Inverses exist for each operation, which makes decryption
possible. This is superior to the simpler modular
arithmetic in a power of two modulus, where multiplying by 2
loses the high bit.

- The mathematics are well understood, dating to the 1830's. This makes it easy for you to pick good mixing functions, and makes it less likely somebody is going to surprise you with a new analysis technique.
- There are enough operations for them to combine in rich ways:
AES combines division in the first half of the S box, a
transpose in the row shift, and matrix operations during
MixColumns and the second half of the S box. Matrix
operations don't commute with each other, and the transpose and
division keeps you from multiplying the matrices together.
By contrast, for example, if you've only got addition, you're a
shift cipher no matter how many operations you do; if you've
only got addition and multiplication, you're a linear cipher no
matter how many operations you do.