4
$\begingroup$

$$\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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ One other thing to note is that this choice of the matrix makes the inverse matrix not too horrid to compute as well. $\endgroup$ – poncho Jun 1 '15 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.