How was the MDS matrix used in AES chosen?

Question

$$\begin{pmatrix}2&3&1&1\\ 1&2&3&1\\ 1&1&2&3\\ 3&1&1&2\end{pmatrix}$$ In the above MDS matrix used in AES encryption, why are the numbers $2$,$3$ and $1$ chosen? Why not any other number?

Answer 1

They were chosen because they are the smallest non zero elements possible that make the matrix MDS and circulant. With an MDS matrix, if a single input changes, all the outputs change.

When multiplying the matrix by a value, you need to multiply the input bytes by the values of the matrix in a finite field. These multiplications have a computational cost associated with them that is related to how large the matrix values are, therefore keeping them as small as possible is a design criteria for efficiency.

Multiplication by 1 is obvious, but in the finite field used by AES, multiplication by anything else is different, since you are treating the values as polynomials.

When implemented, multiplication by 2 is a left shift with a conditional XOR, multiplication by 3 is multiplication by 2 plus XOR against the original value. Other larger numbers require more operations. Having the matrix be circulant also allows efficient operation, since you only need to perform a single multiplication per input element, and the rest is all XOR.

Multiplication can also be done in advance then use a table lookup, but that is not good for devices with very low RAM and ROM. Having the elements be small keeps the performance good for when a table lookup implementation is neither optimal nor possible.

A similar circulant MDS matrix with values 1,1,7,4 is used in the Fugue hash function which requires 2 multiplications per input element. Twofish uses 1,91,239 in a non-circulant matrix.