Reducing the output of AES MixColumns to one byte per entry

Question

I am attempting to manually step through the AES algorithm. I have reached the MixColumns step, and am working with the following values:

30 CA 96 24
32 92 09 23
3F CA 43 63
7D 5A F8 96

My output for the first "row" (multiplying the first row of the constant matrix by each of the four columns in the matrix shown above, which was the output from the ShiftRows step) is as follows:

B4 B2 97 D4

With the following logic:

60 X 96 X 3F X 7D = B4
194 x 1B6 X CA X 5A = B2
12C X 1B X 43 X F8 = 18C (MOD 11B) = 97
48 X 69 X 63 X 96 = D4

For the second cell of the second row, I have the following logic: (01 X CA) X (02 X 92) X (03 X CA) X (01 X 5A), with X used here as a symbol denoting the exclusive or operation. The above simplifies to CA X 124 X 25E X 5A, which evaluates to 3EA. 3EA is clearly too large to be a single output value for MixColumns, which outputs a byte array. Thus, we must reduce it, as 18C above, by taking it MOD 11B. However, 3EA (MOD 11B) evaluates to 2F1, which is still too large.

What is the procedure to be used in further reducing 3EA to a valid output byte for the AES MixColumns function?

Answer 1

For the second cell of the second row, I have the following logic: (01 X CA) + (02 X 92) + (03 X CA) + (01 X 5A), with + used here as a symbol denoting the exclusive or operation. The above simplifies to CA + 124 + 25E + 5A, which evaluates to 3EA.

You have a couple of problems here. You're doing all your evaluations of these as integers; the problem is that they're not integers, they're elements of $GF(2^8)$. The field $GF(2^8)$ does have "addition" and "multiplication" operations defined, however they're not the standard integer operations (and in fact, the "addition" operation is the same as exclusive-or'). The standard way of looking at it is that multiplication in $GF(2^8)$ is not integer multiplication followed by an integer modulo operation; one way of implementing it would be a "carryless multiplication" followed a 'binary modulo' operation. You could do the carryless multiplication first, xor all the results, and then do your binary reduction; however a) 03 X CA isn't 25E (this isn't integer multiplication), instead, it's (CA<<1) + CA = 15E, and b) for the modulo operation, you don't subtract 11B, you exclusive or 11B (or 11B shifted left).

However, instead of getting into all that, for your purposes, the three multiplications within the MixCollumn operation can be simplified to:

$$X \times 1 = X$$

$$X \times 2 = \left\{ \begin{array}{rl} x<<1 & \text{if } x < 128,\\ (x<<1) \oplus 11B & \text{if } x \ge 128. \end{array} \right. $$

$$X \times 3 = (X \times 2) \oplus (X \times 1)$$