Matrice MDS

En algèbre et en cryptologie, une matrice MDS est une matrice possédant des propriétés particulières liées aux codes optimaux. Les propriétés de ces matrices sont particulières et bien connues, ce qui participe notamment à l'analyse des algorithmes de chiffrement par bloc qui les utilisent. Plus précisément, dans une série d'articles scientifiques portant sur les propriétés des réseaux de substitution-permutation, Heys et Tavares ont montré que remplacer la couche de permutation par une couche linéaire de diffusion améliorait la résistance aux attaques cryptanalytiques, notamment la cryptanalyse linéaire et différentielle. Pour cette raison, le terme de « matrice de diffusion MDS » est parfois employé.

Du fait de ces propriétés, les matrices MDS sont au cœur de la conception ou de l'analyse des algorithmes modernes de chiffrement par bloc, dont AES, SHARK, Square, Twofish, Anubis, KHAZAD, Manta, Hierocrypt, Kalyna et Camellia. Les matrices MDS interviennent également, quoique de manière moins systématique, dans le design de certains algorithmes de hachage (par exemple Whirlpool).

Définition

Soit $K=\mathbb {F} _{q}$un corps fini, et $M$ une matrice $k\times k$ à coefficients dans $K$. On dit que $M$est une « matrice (de diffusion) MDS » si le code de matrice génératrice ${\begin{pmatrix}I_{k}|M\end{pmatrix}}$, où $I_{k}$est la matrice identité, est un code MDS. Il existe plusieurs définitions équivalentes, qui peuvent être utilisées pour construire de telles matrices explicitement (voir ci-dessous) ; notamment, une matrice est MDS si et seulement si tous ses mineurs sont inversibles.

Par extension, on appelle encore matrice MDS les matrices binaires obtenues via une réalisation du corps $K$sur le corps $\mathbb {F} _{2}$.

Construction

À partir de codes MDS

Une méthode courante pour construire des matrices MDS consiste à générer un code de Reed-Solomon sur $\mathbb {F} _{2^{m}}$, puis mettre sa matrice génératrice sous forme systématique ${\begin{pmatrix}I_{k}|M\end{pmatrix}}$.

Prenons par exemple $K=\mathbb {F} _{8}\simeq \mathbb {F} _{2}[X]/(X^{3}+X+1)$et construisons sur $K$un code de Reed-Solomon de paramères [6, 3, 4], alors on obtient la matrice génératrice sous forme systématique ${\begin{pmatrix}I_{3}|M\end{pmatrix}}$avec

$$M={\begin{pmatrix}1&X&X^{3}\\1&X^{6}&X^{6}\\1&X^{4}&X^{5}\end{pmatrix}}$$

On peut obtenir à partir de $M$une matrice binaire en remplaçant chaque $X^{m}$par la puissance correspondante de la matrice compagnon du polynôme $X^{3}+X+1$ , on obtient alors

$$M_{b}={\begin{pmatrix}{\begin{array}{c|c|c}{\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&0\\0&0&1\\1&1&1\end{array}}&{\begin{array}{ccc}1&1&0\\0&1&1\\1&1&1\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&1\\1&1&1\\1&0&1\end{array}}&{\begin{array}{ccc}1&1&1\\1&0&1\\1&0&0\end{array}}\end{array}}\end{pmatrix}}$$

Utiliser une représentation différente de $\mathbb {F} _{8}$donnerait des matrices $M$et $M_{b}$différentes et non isomorphes.

Recherche exhaustive

Toutes les matrices MDS ne découlent pas de la construction ci-dessus. En particulier, il peut être souhaitable de doter la matrice de propriétés supplémentaires (qu'elle soit circulante, par exemple, afin d'en simplifier l'implémentation). Dans ces cas, il n'est pas rare de procéder à une recherche exhaustive.

Applications

Les matrices MDS sont de bonnes matrices de diffusion et sont utilisées à cette fin dans les algorithmes de chiffrement par bloc. Ainsi, l'étape MixColumns de l'AES/Rijndael peut être vu comme la multiplication par une matrice MDS circulante, à savoir

$$M={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}$$

où les coefficients appartiennent au corps fini AES isomorphe à $\mathbb {F} _{256}$. Cette matrice est un élément clé dans la stratégie de conception de l'AES, dite « wide trail » .