7
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Robert NN Feb 23 '17 at 13:56
  • $\begingroup$ 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!!! $\endgroup$ – Robert NN Feb 23 '17 at 14:07
  • $\begingroup$ see my edit which clarifies this $\endgroup$ – kodlu Feb 23 '17 at 19:40
  • $\begingroup$ 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? $\endgroup$ – Robert NN Feb 23 '17 at 21:24
  • $\begingroup$ 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. $\endgroup$ – kodlu Feb 23 '17 at 21:31
1
$\begingroup$

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$.

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

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.