Confusion / S-Boxes are easy enough, but very subtle. The cartoon (purposefully) skips over differential cryptography and the design of S-Boxes. In effect: S-Bo

Confusion / S-Boxes are easy enough, but very subtle. The cartoon (purposefully) skips over differential cryptography and the design of S-Boxes. In effect: S-Boxes may be a simple step, but designing the S-Box is anything but simple. --------- In contrast, the MixColumns step looks difficult and requires a lot of words. But conceptually its much easier to understand (!!!!). I don't like how the cartoon goes over it however, so here's my attempt. Finite Fields / Galois Field arithmetic is a form of mathematics where "addition" and "multiplication" have been redefined for new features. The mechanics are simple, but take a lot of words. Finite Fields have a number of properties: * Addition exists. * Negation exists for all numbers. 1 + (-1) == 0. 2 + (-2) == 0. For all X, the number (-X) exists. * Multiplication exists. * Reciprocals exist for all numbers except 0. That is: 2 * (1/2) == 1. 3 * (1/3) == 1 for all numbers. For all X, the number (1/X) exists... except (1/0), which never exists. * There are a _finite_ number of... numbers. In AES, we use GF(2^8), aka 8-bits, numbers between 0 to 255. GF(2^8) was chosen because 8-bit numbers are common in computers. The number 256 does NOT exist in GF(2^8). * Wait wait wait: how does negation or reciprocals exist? What is -0x53? What is 1/0x53? Apologies, but Imma skip that. This is the part that requires too much text and discussion and I'm already getting to verbose. That being said: -0x53 == 0x53. Every number is its own inverse in addition. 1/0x53 == 0xCA. Don't ask me how I got it, but rest assured that 0x53 * 0xCA == 1, and all the properties of multiplication / reciprocals exist and work how you'd expect. Magically. ------------ Okay, so this multiplication -- and reciprocal thing. This is the important bit. This means that you can "diffuse" and "inverse-diffuse" with the following methodology: Multiply by X to "diffuse" the bits around. When you're decryptiong, Multiply by 1/X to undo the encryption process. ------- That's it. Yeah, I spent a wall of text on this subject, but its really that simple. Multiply by X to perform encryption-diffusion. Multiply by 1/X to undo the step. But it can't be "normal" multiplication or "normal" addition (!!!). After all, 1/5 (that is, 0.2) does NOT exist in the realm of numbers between 0 to 255 (aka: 8-bit numbers). You need to do the "magical" GF(2^8) multiply. In "Magical" GF(2^8) land... the number 1/5 exists and is 0x52. Creation of this multiplication table is kinda difficult, but if you "believe" me, you can just look at the table and see how it works: https://tratliff.webspace.wheatoncollege.edu/2016_Fall/math202/inclass/sep21_inclass.pdf https://tratliff.webspace.wheatoncollege.edu/2016_Fall/math2... -------- One last step: MixColumns actually operates over 32-bit numbers, not 8-bit numbers. But each MixColumns operation is just a GF(2^8) multiplication or addition, or a trivial "movement" of bits. Once you understand the "times X" to encrypt vs "Times 1/X" to decrypt thing, all the steps of MixColumns individually make sense. Wait, what is "X" ?? That's the *key* of course. Data * key == ciphertext. Ciphertext * (1/key) == data. Well, effectively that's what it comes down to. A lot of complicated steps to get there, but that's it.