Матрица МДС - MDS matrix

An Матрица МДС (Максимальное разделяемое расстояние) это матрица представляющая функцию с определенным распространение свойства, которые имеют полезное применение в криптография. Технически матрица A размера m × n над конечное поле K - матрица MDS, если это матрица матрица преобразования из линейное преобразование f (x) = Ax из K^п к K^м такое, что никакие два различных (m + n) -наборов вида (x, f (x)) не совпадают по n или более компонентам. Эквивалентно, множество всех (m + n) -наборов (x, f (x) ) является Код MDS, т.е. линейный код что достигает Граница синглтона.

Позволять ${\displaystyle {\tilde {A}}=\left({\begin{array}{c}{\rm {Id}}_{n}\\\hline {\rm {A}}\end{array}}\right)}$ - матрица, полученная сшивкой единичная матрица Идентификатор_п в A. Тогда необходимое и достаточное условие того, чтобы матрица A была MDS, состоит в том, что все возможные n × n подматрица получается удалением m строк из ${\displaystyle {\tilde {A}}}$ является неособый. Это также эквивалентно следующему: все подопределители матрицы A ненулевые. Тогда двоичная матрица A (а именно над полем с двумя элементами) никогда не будет MDS, если она не имеет только одну строку или только один столбец со всеми компонентами 1.

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

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

Матрицы MDS используются для диффузии в таких блочные шифры в качестве AES, АКУЛА, Квадрат, Twofish, Анубис, ХАЗАД, Манта, Иерокрипт, Калина и Камелия, а в потоковый шифр MUGI и криптографическая хеш-функция Водоворот.

Рекомендации

• Серж Воденэ (16 ноября 1994 г.). О необходимости множественных перестановок: криптоанализ MD4 и SAFER (PDF /PostScript ). 2-й Международный семинар по Быстрое программное шифрование (FSE '94). Leuven: Springer-Verlag. стр. 286–297. Получено 2007-03-05.

• Винсент Реймен, Джоан Дэмен, Барт Пренил, Антун Босселаерс, Эрик Де Вин (февраль 1996 г.). Шифр АКУЛА (PDF / PostScript). 3-й Международный семинар по быстрому программному шифрованию (FSE '96). Кембридж: Springer-Verlag. стр. 99–111. Получено 2007-03-06.

• Брюс Шнайер, Джон Келси, Дуг Уайтинг, Давид Вагнер, Крис Холл, Нильс Фергюсон (15 июня 1998 г.). «Алгоритм шифрования Twofish» (PDF / PostScript). Получено 2007-03-04.