Матрица MDS

Матрица MDS (от англ. Maximum Distance Separable — максимальное расстояние разделимости) — это квадратная матрица над конечным полем, используемая в криптографии и теории кодирования, которая обладает свойством максимального расстояния разделимости. В контексте блочных шифров и хеш-функций матрицы MDS применяются в качестве диффузионных слоёв, обеспечивающих быстрое распространение изменений входных данных на все выходные биты. Математически матрица MDS является порождающей матрицей линейного кода с максимально возможным минимальным расстоянием (кодом Рида — Соломона в частном случае), что гарантирует, что любые два различных входных вектора отличаются не менее чем в определённом числе позиций на выходе.

Математическое определение

Матрица M размера \( n \times n \) над конечным полем \( GF(2^m) \) называется MDS, если она является порождающей матрицей линейного кода \([2n, n, n+1]\) (или, эквивалентно, проверочной матрицей кода с такими параметрами). Это означает, что минимальное расстояние кода равно \( n+1 \), что является максимально возможным для линейного кода с размерностью \( n \) (граница Синглтона). На практике это свойство выражается в том, что любая подматрица размера \( n \times n \), составленная из любых \( n \) столбцов матрицы M, является невырожденной (имеет обратную). Для квадратной матрицы MDS это эквивалентно тому, что все её главные миноры (определители подматриц, образованных строками и столбцами с одинаковыми наборами индексов) ненулевые.

Свойства

• Диффузия: Изменение одного байта на входе приводит к изменению всех \( n \) байтов на выходе (полная диффузия). Это достигается за счёт того, что любая ненулевая разность на входе порождает разность на выходе, имеющую вес Хэмминга не менее \( n \).
• Линейность: Операция умножения на матрицу MDS является линейным преобразованием над полем \( GF(2^m) \). Это позволяет анализировать стойкость шифра методами линейного криптоанализа.
• Обратимость: Матрица MDS всегда обратима, так как её определитель ненулевой. Обратная матрица также является MDS.

Применение в криптографии

Матрицы MDS широко используются в конструкции блочных шифров и хеш-функций, где требуется обеспечить высокую диффузию (распространение изменений) и лавинный эффект. Они применяются как часть сети Фейстеля или подстановочно-перестановочной сети (SPN).

Примеры шифров

• AES (Rijndael): В шифре AES используется матрица MDS размера \( 4 \times 4 \) над полем \( GF(2^8) \), заданная в виде циркулянтной матрицы:

\[ M = \begin{pmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{pmatrix} \] Эта матрица применяется в операции MixColumns, которая смешивает столбцы состояния. Она гарантирует, что изменение одного байта в столбце приводит к изменению всех четырёх байтов после MixColumns.

• Twofish: Использует MDS-матрицу размера \( 4 \times 4 \) над \( GF(2^8) \) в качестве части функции g, которая применяется к 32-битным словам.
• Anubis: Шифр, основанный на SPN, использует матрицу MDS размера \( 8 \times 8 \) для усиления диффузии.
• Whirlpool: Хеш-функция, основанная на AES-подобной конструкции, применяет MDS-матрицу в своём раундовом преобразовании.

Роль в защите от криптоанализа

Матрицы MDS обеспечивают защиту от дифференциального и линейного криптоанализа. Благодаря свойству максимального расстояния, любая ненулевая входная разность (для дифференциального анализа) или любая ненулевая входная маска (для линейного анализа) приводит к выходу с весом не менее \( n \). Это значительно усложняет построение эффективных дифференциальных или линейных характеристик. В шифрах с MDS-слоем минимальное количество активных S-блоков в раунде обычно равно \( n \), что повышает стойкость.

Построение матриц MDS

Матрицы MDS могут быть построены несколькими способами:

1. Циркулянтные матрицы

Циркулянтные матрицы имеют вид: \[ M = \begin{pmatrix} a_0 & a_1 & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_0 & a_1 & \dots & a_{n-2} \\ a_{n-2} & a_{n-1} & a_0 & \dots & a_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_1 & a_2 & a_3 & \dots & a_0 \end{pmatrix} \] Для того чтобы такая матрица была MDS, необходимо, чтобы все её собственные значения (над полем) были ненулевыми, а также чтобы выполнялись условия на определители подматриц. Примером является матрица из AES.

2. Матрицы Коши

Матрица Коши размера \( n \times n \) над полем \( GF(2^m) \) определяется элементами: \[ M_{ij} = \frac{1}{x_i + y_j} \] где \( x_i \) и \( y_j \) — различные элементы поля, причём \( x_i \neq y_j \) для всех \( i, j \). Такие матрицы всегда являются MDS, если все \( x_i \) различны и все \( y_j \) различны. Они часто используются при проектировании кодов Рида — Соломона.

3. Матрицы Вандермонда

Матрица Вандермонда: \[ M_{ij} = \alpha_i^{j-1} \] где \( \alpha_i \) — различные ненулевые элементы поля. Она является MDS, если \( \alpha_i \) различны. Однако такие матрицы не всегда удобны для реализации, так как требуют вычисления степеней.

4. Результат поиска

Для практических целей часто используется компьютерный поиск матриц MDS с малым весом Хэмминга (количеством ненулевых элементов), чтобы ускорить вычисления. Например, в AES выбрана матрица с коэффициентами 1, 2, 3, что позволяет реализовать умножение на 2 и 3 с помощью простых операций сдвига и XOR.

Характеристики и ограничения

Размерность

Матрицы MDS обычно имеют размер от \( 2 \times 2 \) до \( 16 \times 16 \) над полем \( GF(2^8) \). Размерность выбирается исходя из длины слова в шифре. Например, в AES размер матрицы 4×4 соответствует 32-битному слову (4 байта). Увеличение размера улучшает диффузию, но увеличивает вычислительную сложность.

Сложность реализации

Умножение на матрицу MDS требует \( O(n^2) \) операций в поле. Для \( n=4 \) это 16 умножений и 12 сложений (XOR). Для больших \( n \) (например, 8 или 16) сложность растёт квадратично, что может быть проблемой для аппаратной реализации. Для ускорения применяются методы:

• Табличная реализация: предварительно вычисляются все возможные результаты умножения на каждый элемент матрицы (например, таблицы на 256 байт для каждого коэффициента).
• Использование циркулянтных матриц: умножение на циркулянтную матрицу можно реализовать с помощью циклического сдвига и XOR, что снижает сложность до \( O(n) \).

Криптографические ограничения

• Линейность: MDS-слой является линейным, поэтому он не добавляет нелинейности. Для стойкости шифра требуется комбинация с нелинейными S-блоками.
• Атаки на основе отказов: В некоторых реализациях матрицы MDS могут быть подвержены атакам, если злоумышленник может вносить ошибки в вычисления. Однако это относится скорее к реализации, чем к самому свойству MDS.

Сравнение с другими диффузионными слоями

Матрицы MDS обеспечивают наилучшую диффузию среди линейных преобразований, но за счёт более высокой вычислительной стоимости.

Интересные факты

• Название: Термин «Maximum Distance Separable» происходит из теории кодирования, где коды с таким свойством (например, коды Рида — Соломона) позволяют исправлять максимальное количество ошибок при заданной длине и размерности.
• История: Матрицы MDS впервые были предложены для использования в криптографии в 1990-х годах, в частности, в шифре Square (предшественнике AES). Их применение было формализовано в работах Джоан Даймен и Винсента Рэймена.
• Оптимизация: В AES умножение на 2 и 3 в поле \( GF(2^8) \) реализуется с помощью сдвига и условного XOR, что делает операцию MixColumns очень быстрой на большинстве процессоров.
• Не только квадратные: В некоторых конструкциях (например, в шифре SEA) используются прямоугольные MDS-матрицы, где количество строк не равно количеству столбцов, но свойство максимального расстояния сохраняется.

Источники

• Daemen, J., Rijmen, V. «The Design of Rijndael: AES — The Advanced Encryption Standard». Springer, 2002.
• Menezes, A., van Oorschot, P., Vanstone, S. «Handbook of Applied Cryptography». CRC Press, 1996.
• Schneier, B. «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons, 1996.
• MacWilliams, F. J., Sloane, N. J. A. «The Theory of Error-Correcting Codes». North-Holland, 1977.
• Барабанов, А. В., Глухов, М. М. «Криптографические методы защиты информации». М.: МГТУ им. Н. Э. Баумана, 2018.