Matrice MDS - Wikiwand

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

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^{[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 $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^[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

$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 » ^[10]^,^[11].

Notes et références

Notes

↑ C'est-à-dire qu'il atteint la borne de Singleton.

Références

↑ Nora El Amrani, Codes additifs et matrices MDS pour la cryptographie, Université de Limoges, 24 février 2016 (lire en ligne)
↑ (en) H. M. Heys et S. E. Tavares, « The design of substitution-permutation networks resistant to differential and linear cryptanalysis », CCS '94 Proceedings of the 2nd ACM Conference on Computer and communications security, ACM,‎ 2 novembre 1994, p. 148–155 (ISBN 0897917324, DOI 10.1145/191177.191206, lire en ligne, consulté le 11 août 2018)
↑ (en) H.M. Heys et S.E. Tavares, « Avalanche characteristics of substitution-permutation encryption networks », IEEE Transactions on Computers, vol. 44, n^o 9,‎ 1995, p. 1131–1139 (ISSN 0018-9340, DOI 10.1109/12.464391, lire en ligne, consulté le 11 août 2018)
↑ (en) Anne Canteaut et Joëlle Roué, « Differential Attacks Against SPN: A Thorough Analysis », dans Lecture Notes in Computer Science, Springer International Publishing, 2015 (ISBN 9783319186801, DOI 10.1007/978-3-319-18681-8_4, lire en ligne), p. 45–62
↑ (en) Vincent Rijmen, Joan Daemen, Bart Preneel et Antoon Bosselaers, « The cipher SHARK », dans Fast Software Encryption, Springer Berlin Heidelberg, 1996 (ISBN 9783540608653, DOI 10.1007/3-540-60865-6_47, lire en ligne), p. 99–111
↑ (en) Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall et Niels Ferguson, « Twofish: A 128-Bit Block Cipher - Schneier on Security », sur www.schneier.com, 15 juin 1998 (consulté le 10 août 2018)
↑ (en) Daniel Augot et Matthieu Finiasz, « Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions », 2013 IEEE International Symposium on Information Theory, IEEE,‎ juillet 2013 (ISBN 9781479904464, DOI 10.1109/isit.2013.6620487, lire en ligne, consulté le 11 août 2018)
↑ (en) Siang Meng Sim, Khoongming Khoo, Frédérique Oggier et Thomas Peyrin, « Lightweight MDS Involution Matrices », dans Fast Software Encryption, Springer Berlin Heidelberg, 2015 (ISBN 9783662481158, DOI 10.1007/978-3-662-48116-5_23, lire en ligne), p. 471–493
↑ (en) Kishan Chand Gupta, Sumit Kumar Pandey et Ayineedi Venkateswarlu, « On the direct construction of recursive MDS matrices », Designs, Codes and Cryptography, vol. 82, n^os 1-2,‎ 14 juin 2016, p. 77–94 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-016-0233-4, lire en ligne, consulté le 11 août 2018)
↑ (en) Joan Daemen et Vincent Rijmen, « Security of a Wide Trail Design », dans Progress in Cryptology — INDOCRYPT 2002, Springer Berlin Heidelberg, 2002 (ISBN 9783540002635, DOI 10.1007/3-540-36231-2_1, lire en ligne), p. 1–11
↑ (en) Carlos Cid, Sean Murphy et Matthew Robshaw, Algebraic Aspects of the Advanced Encryption Standard, 2006 (DOI 10.1007/978-0-387-36842-9, lire en ligne)

Portail de la cryptologie

Portail des mathématiques

À partir de codes MDS

Recherche exhaustive

Notes

Références

Related Articles