4 ms·
> It involves multiplication operations in a finite field, hence this step is a bit tough to describe. See Wikipedia for more details. Woah woah woah!!!! MixCo
by dragontamer 6y ago
> It involves multiplication operations in a finite field, hence this step is a bit tough to describe. See Wikipedia for more details.
Woah woah woah!!!! MixColumns is incredibly important to understanding AES! I don't think it should be glossed over, or just pointed to Wikipedia (which is... sub-par IMO... as an explanation source).
Lets break things down:
1. Galois Fields / Finite Fields are a special number system. Instead of "choosing better numbers", Mathematicians "choose better addition/multiplies". That's right, you change the definition of addition / multiply to better suit your mathematical needs.
2. All operations in a finite-field self-feed back into the same finite-field... I joke that its a "human centipede" of math because you can just keep feeding yourself the same crap! Addition, Subtraction, Multiplication, Division, Logarithm, Exponent, Square-roots, Cube-Roots, etc. etc. All operations are GUARANTEED to return to the finite field specified. In the case of AES, the 2^8 field (256 "numbers", usually labeled 0 through 255) is chosen. No matter how crazy the math gets, you always return to the finite-field at every step.
2.5 -- Technically, they're not actually numbers... they're polynomials. But because they're represented by 0x00 through 0xFF, you can think of them as numbers with weird add/multiply rules.
2.75 -- Knuth notes that real numbers are just polynomials anyway. 525600 == 5 * 10^5 + 2 * 10^4 + 5 * 10^3 + 6 * 10^2. If you're having issues thinking about "GF polynomials are pretending to be numbers", just think about normal numbers, which always have a polynomial representation. The radix-point / decimal-point is just where the 10^0 is located, and then 10^-1, 10^-2 (etc. etc) move forward. Then, instead of having "10" as a specified radix, the radix is now "x" (the polynomial's variable).
3. Finite Field division is very, very similar to "normal" division. As you may remember from elementary school, division "mixes up the numbers real good". Well, in Finite Field arithmetic, all divisions can be optimized to a multiplication. This matches your elementary-school level thinking: 5/7 is "5 divided by 7", but ALSO "5 times 1/7th" in normal math. The same is true in Finite Fields, EXCEPT 5/7th is actually a number (erm... polynomial) in the 0x00 to 0xFF space. Also 5/7 == 5 * (1/7) == 5 * 7^-1.
3.5 -- The magic of making 5/7 == 5 * 1/7 == 5 * 7^1 is WHY cryptographers use Galois Fields. When the math / arithmetic becomes more important than the numbers themselves, its very natural to just switch to GF-field representation.
4. Well... hold on. We have GF(2^8) "numbers" (erm... 8-bit polynomials) but AES is over 128-bits. Well... GF(2^8) is more efficient to implement in software because you only need a lookup table of size 256. (From a software perspective: you can either make addition or multiplication efficient on computers. The other operation needs a lookup table. Most programmers choose "XOR" to be the efficient add, and then a lookup table for multiply/divide).
4.5 Because we're stuck with GF(2^8) (because it's the mid 90s and GF-instructions don't exist on CPUs yet and you want tiny lookup tables that fit inside of tiny L1 caches of tiny 90s computers), we extend the GF(2^8) == 8-bit by making a 4x4 matrix (128-bits total for the full 4x4 matrix, each column a 32-bit integer).
5. Instead of just doing one or two multiply / divide operations per element, lets "mix up the numbers real good" with a Matrix-multiplication.
6. As you may remember from linear algebra class: the inverse of a matrix doesn't necessarily exist. But Galois Fields make it easier to find matrix-inverses. In particular, division is always possible, so its far easier to find an inverse of a matrix.
6.5 Assume we were using "normal 8-bit integers" instead of GF(2^8), and we have a simple [[1 0] [0 2]] 2x2 Matrix. To invert the matrix, you need to divide by 2, but what is 1/2 in integer math? Well, it doesn't exist (0.5, or "one half" is NOT an integer), so you run into problems pretty quickly. GF(2^8) has a definition for 1/2, because all addition/subtraction/multiplication/division/logarithms/exponents/square-roots/etc.etc. have a precise solution.
- some_furry 6y agoAddendum: If anyone's curious about Galois Theory, this looks like a good place to start: https://www.gfuzz.de/AES_1.html https://www.gfuzz.de/AES_1.html
- dragontamer 6y agoI dunno if its just "how I learned it", but experiments over the GF(5) prime field, followed by the GF(2) then GF(2^x) extension fields has always made the most sense in my brain. GF(5) is a prime field and is much easier to think about. You have 0, 1, 2, 3, 4 as your numbers (and they're "true numbers", not yet polynomials). The most natural generator is 2. * 2^0 == 1 mod 5 * 2^1 == 2 mod 5 * 2^2 == 4 mod 5 * 2^3 == 8 mod 5 == 3 * 2^4 == 2^3 * 2 == 3 * 2 == 6 mod 5 == 1 == 2^0 Because 2^4 == 2^0 == 1, you have your loop. All non-zero elements are created by this sequence (because 2 is an appropriate generator). Define multiplication to be consistent with these numbers (and it happens to line up with normal multiplication). For example: * 2^4 * 2^3 == 1 * 3 == 2^7 == 2^4 * 2^3 == 2^0 * 2^3 == 3. ------- Extend the cycle over the negative numbers, and you remain consistent: * 2^0 == 1 mod 5 * 2^-1 == 3 mod 5 * 2^-2 == 4 mod 5 * 2^-3 == 2 mod 5 * 2^-4 == 1 mod 5 == 2^0 By extending into the negative exponents, we've invented division that's 100% consistent with all other math. Notice that 2^-1 == 3, which is 2's inverse. 2^2 == 2^-2, which is its own inverse. Notice that 4 * 4 == 2^2 * 2^2 == 2^4 == 1. Any number times 4 twice equals itself. Remember, GF(5) is just simple mod-5 arithmetic. We've redefined multiplication to the above attributes, but it works out how you'd expect. Lets take some random examples of multiplicative inverses / division in GF(5), but "extended" over normal integers outside of the modular space to show you this really is amazing and it works. * 3 * 2 == 6 mod 5 == 1. * 4 * 2 * 3 == 24 mod 5 == 4 (notice: 2 * 3 is 1, so when 4 * 1 == 4) * 4 * 4 == 16 mod 5 == 1 * 2 * 4 * 4 == 32 mod 5 == 2 (notice: 4 is equal to 1/4. So 2 * 4/4 == 2 * 4 * 4 == 2) ----- A similar exercise can be done over addition. Then a similar exercise can be done over distributive property and even polynomials / quadratic equation / cubics and more! Logarithms, Square Roots. Everything. All the math you ever learned: shrunk down into the exact space of {0, 1, 2, 3, 4} numbers. -------- GF(5) is awkward for computers however. To make this "reasonable" for computers, we need to convert it into bits and bytes. Shrink the space down to GF(2) (0 and 1), then extend the space into GF(2^8). Extension fields (taking a "power" of the prime) are... complicated. Very complicated. An extension field is the GF-version of "complex numbers". You invent a polynomial over "x" (or some indeterminate variable). Complex numbers call it "i", electrical engineers call it "j". In the Complex world, i^4 == 1 (the 4th root of 1 is i). But in GF-version, the variable depends on the size of your field. A GF(2^8) will have x^255 == 1... so you have a much larger "loop" so to speak, but otherwise functions very similar to the Complex i. But hopefully the experiments in GF(5) show why cryptographers love to use GF() fields in general. Its very useful to have all numbers "loop" back into themselves.