Misunderstanding MixColumns step

Question

I'm having an issue understanding the MixColumns step described here.

I know about diffusion and it all makes sense up the the point where it states that each column is treated as a polynomial and multiplied modulo over GF(2^8).

BUT..multiplying in GF(2^8). Although the domain is still the same, it is not reversible due to mod.... and it has to be reversible because that is the entire point of it.

As far as the first bit goes, my approach is taking A,B,C and D as the 4 bytes of a column and A1, A2, ..., A8 as the bits and E,F,G and H as the output bytes. I was going to set

E = A1,B2,C3,D4,A5,B6,C7,D8
F = D1,A2,B3,C4,D5,A6,B7,C8
G = C1,D2,A3,B4,C5,D6,A7,B8
H = B1,C2,D3,A4,B5,C6,D7,A8

And thus it is reversible, one-to-one, linear and distributive

It later states that it can be viewed as a matrix multiplication but as the elements of the matrix must be bytes and output as bytes then each element of the matrix must be modulo 256 and therefore not reversible and non linear.

Have I understood this wrong? I struggle with maths and am trying to understand what needs to be done so that I can convert it into logic.

Answer 1

The multiplication in MixColumns is indeed reversible, and it is not modulo 256. samiam.org/mix-column.html has a good explanation of the MixColumns step, and samiam.org/galois.html does an excellent job of explaining how to do arithmetic in AES's finite field.

Answer 2

MixColumns is probably the hardest part to AES, but it was exciting for me to work out the math and actually see where the numbers came from. I worked out the math of it in detail in my blog post "A Stick Figure Guide to the Advanced Encryption Standard (AES)". Specifically, look at Act 4, Scene 16. I also put the reverse of it on the crib sheet in the next scene (17). If you have any further questions, feel free to leave a comment on that post or here.