How to check that AES Matrix is MDS?

I want to understand how can I prove that M matrix in AES is MDS. I know that a matrix is MDS if every determinant of every square submatrix is different from 0.

I don't get this. How much submatrix does it have? If I swap rows or columns, does that change something? Do I have to calculate the determinant in a certain mode?

2 Answers

My answer focuses on the AES matrix only. In general, an $A$ matrix with all submatrices having full rank generates an MDS code when concatenated by an identity matrix of the right size to form $[I|A]$, but that's really a coding theory matter.

As to the specific question, this is basic linear algebra but you need to work over the field that AES is defined over. Let the $k\times k$ matrix (like the AES mixing matrix) be $$A=\left[ \begin{array}{cccc} a_{1,1}&a_{1,2}&\cdots&a_{1,k}\\ \vdots &&& \vdots \\ a_{k,1}&a_{k,2}&\cdots&a_{k,k} \end{array} \right]$$

The $1\times1$ submatrices are all nonzero, they're just the entries of $A.$

The $2\times 2$ submatrices: choose any two rows or columns. you can also use the fact that the matrix is circulant to reduce the cases.

So the matrix $$\left[\begin{array}{cc} a_{1,1}&a_{1,3}\\ a_{2,1}&a_{2,3} \end{array} \right]$$

is the same matrix as $$\left[\begin{array}{cc} a_{2,2}&a_{2,4}\\ a_{3,2}&a_{3,4} \end{array} \right]$$ and thus has the same determinant, etc.

The $4\times$ submatrix is the whole matrix.

Row and column swaps only change the sign of the determinant and can be ignored.

Edit: You need to use the finite field with 256 elements as explained in the link below.

How to use the Extended Euclidean algorithm to invert a finite field element?

This is NOT mod 256 arithmetic.

• thanks a lot. So, for example the only cases that i have to see is 2x2 (36 cases) and 3x3 (16 cases) but i can delete many cases?. AES field is 2^8. The only difference with common determinat math is that i have to calculate in modular 256? – Robert NN Feb 23 '17 at 13:56
• sorry i forgot something. The cases that i enum. Are without row/colums swaps? or in all this cases, that i calculated with the another answer formule, consider swaps?. Sorry i m so new in this topic!!! – Robert NN Feb 23 '17 at 14:07
• see my edit which clarifies this – kodlu Feb 23 '17 at 19:40
• thanks a lot kodlu. but i want to know if i understand en.wikipedia.org/wiki/… i have to define * and xor operationes and then use determinat formule? wich formula i have to use? with + and - or there is another? the mod is the polynomial? – Robert NN Feb 23 '17 at 21:24
• The modulo operation is mod the polynomial as well as mod 2. And since you are operating mod 2, + and - are the same, addition mod 2, which is xor. – kodlu Feb 23 '17 at 21:31

Let $C$ be $[n,k,d]$ code, where $n$,$k$ and $d$ are length of code words, dimension and minimum distance of code, respectively. Codes with $n-k=d-1$ are called MDS codes.

In general case, if a $m\times m$ matrix $M$ is an MDS we can use $[I\mid M]$ as a generator matrix and check if the code produced is MDS code. In this state, produced code $C$ is $[2m,m,d]$ code. So $d$ must be equal to $m+1$.

For a matrix of order $m$, by your mentioned method, you should obtain $\sum_{i=1}^m \, {m \choose i }^2$ determinant to find out that a matrix is MDS or not, but you can easily compute the minimum distance of codes with powerful programs such as MAGMA, for small $m$.

• well, if i want to check all the codes. How can i do that? with one code for example? – Robert NN Feb 23 '17 at 18:30