AES confused about how ShiftRows() step works

Question

Advanced Encryption Standard has a ShiftRows() operation that cyclically shifts last three rows of 16 byte block as shown here. This process is explained here in further detail.

But same documentation provides test vectors which have confused me a bit:

round[ 1].s_box    63cab7040953d051cd60e0e7ba70e18c
round[ 1].s_row    6353e08c0960e104cd70b751bacad0e7

So after shift row step, the 16-byte block has turned into a hex number labeled as round[1].s_row. Converting into byte representation we have:

round[ 1].s_box  [99, 202, 183, 4, 9, 83, 208, 81, 205, 96, 224, 231, 186, 112, 225, 140]
round[ 1].s_row  [99, 83, 224, 140, 9, 96, 225, 4, 205, 112, 183, 81, 186, 202, 208, 231]

I had assumed that if we turn this 16x1 array into 4x4 matrix, first four elements would act as first row, elements 4..8 as second row and etc. in which case first four bytes [99, 202, 183, 4] should have remained unchanged.

However as we can see only elements at indices 0, 4, 8 and 12 are unchanged. Are definitions of rows and columns different in context of AES?

Here is how my implementation of AES transforms the hex labeled as round[1].s_box: 63cab70453d05109e0e7cd608cba70e1

[99, 202, 183, 4, 83, 208, 81, 9, 224, 231, 205, 96, 140, 186, 112, 225]

Edit: it is obvious that columns are transposed both before applying ShiftRow() and then after the operation is complete. This turned out to be the case for MixColumns() operation as well. Is there any particular reason for this?

Answer 1

The entire AES algorithm uses column-major order. So the first four elements are actually the first column, and not the first row.

Answer 2

it is obvious that columns are transposed both before applying ShiftRow() and then after the operation is complete. This turned out to be the case for MixColumns() operation as well. Is there any particular reason for this?

They're only "transposed" if you hold the view that splitting the one-dimensional array into rows is objectively more reasonable than splitting it into columns, but it's not - the choice is just convention.

Per section 3.5 of the standard:

The four bytes in each column of the State array form 32-bit words, where the row number r provides an index for the four bytes within each word. The state can hence be interpreted as a one-dimensional array of 32 bit words ... where the column number provides an index into this array. Hence, for the example in Fig. 3, the State can be considered as an array of four words, as follows:

w0 = s0,0 s1,0 s2,0 s3,0

w1 = s0,1 s1,1 s2,1 s3,1

w2 = s0,2 s1,2 s2,2 s3,2

w3 = s0,3 s1,3 s2,3 s3,3

showing that the four bytes of the first word are all in column 0, the four bytes of the second word are all in column 1, etc, and the row number is "an index for the four bytes within each word."