Re: AES operation order

Cryptic <no@spam.please> wrote:
>I would like to change the default AES internal loop body
>structure from the form present in Brian Gladman's paper:
>
> SubBytes(state);
> ShiftRows(state);
> MixColumns(state);
> AddKey(state, key);
>
>to:
>
> ShiftRows(state);
> SubBytes(state);
> AddKey(state, key);
> MixColumns(state);

>because the latter form seems to have much better implementation in hardware
>(less bypass circuits). I can change the first two lines without any
>problem, but
>the last two lines work wrong, i.e. the algorithm returns an incorrect
>result even
>in the first iteration of the loop. But since AddKey(state, key) = state xor
>key
>and
>
>MixColumns(state) = A * state,
>
>where A = [2 3 1 1; 1 2 3 1; 1 1 2 3; 3 1 1 2], if I use A^(-1) * key
>instead of key for all round keys used in the loop, it should become

If you represent the key as a 4x4 matrix K over GF(256), then xor
is the same as addition in the field, and the MixColumns and AddKey
steps can be rearranged as

        A*state + K = A state + A A^(-1) K = A (state + A^(-1) K) .

Which looks exactly like what you have below.

>MixColumns(state xor (A^(-1) * key)) =
>A * (state xor A^(-1) * key) =
>(A * state) xor (A * A^(-1) * key) =
>(A * state) xor key = the original AES result.
>
>But it does not work. Isn't the above correct in GF(2^8)?

-- 
Kristian Gjøsteen