Матрица МДС

Матрица MDS ( разделяемая на максимальное расстояние ) — это матрица, представляющая функцию с определенными диффузионными свойствами, которые имеют полезные приложения в криптографии . Технически, $m\times n$ матрица $A$ над конечным полем $K$ является матрицей MDS, если это матрица преобразования линейного преобразования $f(x)=Ax$ от $K^{n}$ к $K^{m}$ такой, что нет двух разных $(m+n)$ -кортежи вида $(x,f(x))$ совпадают в $n$ или более компонентов.Аналогично, совокупность всех $(m+n)$ -кортежи $(x,f(x))$ является MDS-кодом , т. е. линейным кодом , достигающим границы Синглтона .

Позволять ${\tilde {A}}={\begin{pmatrix}\mathrm {I} _{n}\\\hline \mathrm {A} \end{pmatrix}}$ быть матрицей, полученной путем объединения единичной матрицы $\mathrm {I} _{n}$ к $A$ . Тогда необходимое и достаточное условие для матрицы $A$ быть MDS - это то, что все возможно $n\times n$ подматрица, полученная удалением $m$ строки из ${\tilde {A}}$ является несингулярным . Это также эквивалентно следующему: все субопределители матрицы $A$ ненулевые. Тогда двоичная матрица $A$ (а именно над полем с двумя элементами) никогда не является MDS, если в нем нет только одной строки или только одного столбца со всеми компонентами. $1$ .

Коды Рида-Соломона обладают свойством MDS и часто используются для получения матриц MDS, используемых в криптографических алгоритмах.

Серж Водене предложил использовать матрицы MDS в криптографических примитивах для создания того, что он назвал мультиперестановками , — необязательно линейных функций с тем же свойством. ^[1] Эти функции имеют то, что он назвал идеальной диффузией : изменение $t$ входов меняется как минимум $m-t+1$ выходов. Он показал, как использовать несовершенную диффузию для криптоанализа функций, не являющихся множественными перестановками.

Матрицы MDS используются для диффузии в таких блочных шифрах , как AES , SHARK , Square , Twofish , Anubis , KHAZAD , Manta , Hierocrypt , Kalyna , Camellia и HADESMiMC , а также в поточном шифре MUGI и криптографической хеш-функции Whirlpool , Poseidon .

Ссылки

^ Водене, Серж (1995), Пренел, Барт (ред.), «О необходимости множественных перестановок: криптоанализ MD4 и SAFER» , Fast Software Encryption , vol. 1008, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 286–297, doi : 10.1007/3-540-60590-8_22 , ISBN 978-3-540-60590-4 , получено 17 июля 2023 г.

Винсент Реймен ; Джоан Дэмен ; Барт Пренил ; Антон Босселерс; Эрик Де Вин (февраль 1996 г.). Шифрованная АКУЛА (PDF/PostScript) . 3-й международный семинар по быстрому программному шифрованию (FSE '96). Кембридж : Springer-Verlag. стр. 99–111 . Проверено 6 марта 2007 г.
Брюс Шнайер ; Джон Келси ; Дуг Уайтинг; Дэвид Вагнер ; Крис Холл; Нильс Фергюсон (15 июня 1998 г.). «Алгоритм шифрования Twofish» (PDF/PostScript) . Проверено 4 марта 2007 г.

Эта статья, посвященная криптографии, незавершена . Вы можете помочь Википедии, расширив ее .

[1] Водене, Серж (1995), Пренел, Барт (ред.), «О необходимости множественных перестановок: криптоанализ MD4 и SAFER» , Fast Software Encryption , vol. 1008, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 286–297, doi : 10.1007/3-540-60590-8_22 , ISBN 978-3-540-60590-4 , получено 17 июля 2023 г.

[1]