Understanding how AES encryption works
&gt; It involves multiplication operations in a finite field, hence this step is a bit tough to describe. See Wikipedia for more details.<p>Woah woah woah!!!! MixColumns is incredibly important to understanding AES! I don&#x27;t think it should be glossed over, or just pointed to Wikipedia (which is... sub-par IMO... as an explanation source).<p>Lets break things down:<p>1. Galois Fields &#x2F; Finite Fields are a special number system. Instead of &quot;choosing better numbers&quot;, Mathematicians &quot;choose better addition&#x2F;multiplies&quot;. That&#x27;s right, you change the definition of addition &#x2F; multiply to better suit your mathematical needs.<p>2. All operations in a finite-field self-feed back into the same finite-field... I joke that its a &quot;human centipede&quot; 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 &quot;numbers&quot;, usually labeled 0 through 255) is chosen. No matter how crazy the math gets, you always return to the finite-field at every step.<p>2.5 -- Technically, they&#x27;re not actually numbers... they&#x27;re polynomials. But because they&#x27;re represented by 0x00 through 0xFF, you can think of them as numbers with weird add&#x2F;multiply rules.<p>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&#x27;re having issues thinking about &quot;GF polynomials are pretending to be numbers&quot;, just think about normal numbers, which always have a polynomial representation. The radix-point &#x2F; decimal-point is just where the 10^0 is located, and then 10^-1, 10^-2 (etc. etc) move forward. Then, instead of having &quot;10&quot; as a specified radix, the radix is now &quot;x&quot; (the polynomial&#x27;s variable).<p>3. Finite Field division is very, very similar to &quot;normal&quot; division. As you may remember from elementary school, division &quot;mixes up the numbers real good&quot;. Well, in Finite Field arithmetic, all divisions can be optimized to a multiplication. This matches your elementary-school level thinking: 5&#x2F;7 is &quot;5 divided by 7&quot;, but ALSO &quot;5 times 1&#x2F;7th&quot; in normal math. The same is true in Finite Fields, EXCEPT 5&#x2F;7th is actually a number (erm... polynomial) in the 0x00 to 0xFF space. Also 5&#x2F;7 == 5 * (1&#x2F;7) == 5 * 7^-1.<p>3.5 -- The magic of making 5&#x2F;7 == 5 * 1&#x2F;7 == 5 * 7^1 is WHY cryptographers use Galois Fields. When the math &#x2F; arithmetic becomes more important than the numbers themselves, its very natural to just switch to GF-field representation.<p>4. Well... hold on. We have GF(2^8) &quot;numbers&quot; (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 &quot;XOR&quot; to be the efficient add, and then a lookup table for multiply&#x2F;divide).<p>4.5 Because we&#x27;re stuck with GF(2^8) (because it&#x27;s the mid 90s and GF-instructions don&#x27;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).<p>5. Instead of just doing one or two multiply &#x2F; divide operations per element, lets &quot;mix up the numbers real good&quot; with a Matrix-multiplication.<p>6. As you may remember from linear algebra class: the inverse of a matrix doesn&#x27;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.<p>6.5 Assume we were using &quot;normal 8-bit integers&quot; 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&#x2F;2 in integer math? Well, it doesn&#x27;t exist (0.5, or &quot;one half&quot; is NOT an integer), so you run into problems pretty quickly. GF(2^8) has a definition for 1&#x2F;2, because all addition&#x2F;subtraction&#x2F;multiplication&#x2F;division&#x2F;logarithms&#x2F;exponents&#x2F;square-roots&#x2F;etc.etc. have a precise solution.