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^[1]. 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^[2],[3] 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^[4]. 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^[5], Square, Twofish^[6], 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 ${\displaystyle K=\mathbb {F} _{q}}$un corps fini, et ${\displaystyle M}$ une matrice ${\displaystyle k\times k}$ à coefficients dans ${\displaystyle K}$. On dit que ${\displaystyle M}$est une « matrice (de diffusion) MDS » si le code de matrice génératrice ${\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}}$, où ${\displaystyle I_{k}}$est la matrice identité, est un code MDS^{[Note 1]}. 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 ${\displaystyle K}$sur le corps ${\displaystyle \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 ${\displaystyle \mathbb {F} _{2^{m}}}$, puis mettre sa matrice génératrice sous forme systématique ${\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}}$.

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

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

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

$${\displaystyle 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 ${\displaystyle \mathbb {F} _{8}}$donnerait des matrices ${\displaystyle M}$et ${\displaystyle 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^[7],[8],[9].

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

$${\displaystyle 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 à ${\displaystyle \mathbb {F} _{256}}$. Cette matrice est un élément clé dans la stratégie de conception de l'AES, dite « wide trail » ^[10],[11].