Most AES tutorials either wave at the math ("shift left and XOR with 0x1B") or jump straight into ring theory without tying it back to bytes. I wrote up notes from Christof Paar's AES lectures that try to sit in between.
Why ordinary integer math doesn't work
AES needs two things from byte arithmetic. Every result has to be another byte (0x00 to 0xFF), and every nonzero byte needs a multiplicative inverse, because the S-box is built from inverses. Integers mod 256 give you the first but not the second. No even number has an inverse mod 256, since 2·x is always even and so never equals 1.
A field with 256 elements has both properties, and GF(2⁸) is that field.
What GF(2⁸) does with a byte
Each byte is read as a polynomial whose coefficients are its bits. 0x57 = 01010111 is x⁶ + x⁴ + x² + x + 1.
Addition works coefficient by coefficient mod 2, which is just XOR: 0xD1 + 0x15 = 0xC4, with no carries.
Multiplication is polynomial multiplication followed by reduction modulo the AES polynomial x⁸ + x⁴ + x³ + x + 1 (0x11B). This is where xtime comes from. Multiplying by x shifts left one bit, and if a bit falls off the top, x⁸ gets replaced by x⁴ + x³ + x + 1, which means XOR with 0x1B.
To multiply 0x57 by 0x83, you keep doubling 0x57 and XOR in the copies where 0x83 has a 1 bit:
| i | bit i of 0x83 | 0x57 · xⁱ | running XOR |
|---|---|---|---|
| 0 | 1 | 0x57 | 0x57 |
| 1 | 1 | 0xAE | 0xF9 |
| 2 | 0 | 0x15C ⊕ 0x11B = 0x47 | 0xF9 |
| 3 | 0 | 0x8E | 0xF9 |
| 4 | 0 | 0x11C ⊕ 0x11B = 0x07 | 0xF9 |
| 5 | 0 | 0x0E | 0xF9 |
| 6 | 0 | 0x1C | 0xF9 |
| 7 | 1 | 0x38 | 0xC1 |
So 0x57 · 0x83 = 0xC1. The two rows with ⊕ 0x11B are the reductions: the shift pushed a 1 into bit 8, and XORing with 0x11B clears it.
The post has this as an interactive widget. You type any two bytes, then play it or step through one bit at a time, and a bit strip shows each shift, each XOR with 0x11B and each update to the result.
The rest of the post builds groups and fields from scratch. It has GF(7) and GF(2³) tables you can check by hand, the 0x57 · 0x83 long division, extended Euclid for inverses (0x53⁻¹ = 0xCA), and a short Python gf_mul. Part 2 uses all of this to build AES-128 layer by layer and checks it against the FIPS 197 test vector.
Part 1, Galois fields: https://edu.parthsinha.com/posts/galois-fields-for-aes/
Part 2, AES layer by layer: https://edu.parthsinha.com/posts/aes-structure-and-layers/
When you learned AES, which took longer to click: MixColumns or the S-box?
Top comments (0)