Том 26, номер 2, 2019 г., Стр. 115-128

УДК 519.688
Рожков М. И., Малахов С. С.
Экспериментальные методы построения MDS матриц специального вида

Аннотация:
MDS матрицы широко используются в качестве рассеивающего примитива при реализации итеративного метода построения преобразований блочного типа в связи с задачами защиты информации (алгоритмы AES, GOST 34.12-2015 и др.). При этом матрицы с большим числом единичных и малым числом различных элементов вызывают особый интерес с точки зрения эффективной реализации матрично-векторных умножений в условиях ресурсных ограничений. В настоящей работе описывается новый метод проверки признака MDS у матриц над конечным полем и демонстрируется его применение на примере матриц специального вида порядка $(8 \times 8)$, содержащих большое число единиц и малое число различных элементов. Такие матрицы были введены П. Юнодом и С. Воденеем. Для предложенного метода получены теоретические и экспериментальные оценки эффективности. Кроме того, в статье приводится список некоторых MDS матриц указанного вида.
Табл. 7, библиогр. 15.

Ключевые слова: MDS матрица, MDS код.

DOI: 10.33048/daio.2019.26.621

Рожков Михаил Иванович ¹
Малахов Станислав Сергеевич ¹
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Мясницкая, 20, 101000 Москва, Россия
е-mail: mirozhkov@hse.ru, ssmalakhov@edu.hse.ru

Статья поступила 28 мая 2018 г.
После доработки — 28 января 2019 г.
Принята к публикации 29 января 2019 г.

Литература

[1] Анашкин А. В. Полное описание одного класса MDS-матриц над конечным полем характеристики 2 // Мат. вопросы криптографии. 2017. Т. 8, № 4. С. 5–28.

[2] Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988. 820 с.

[3] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1977. 744 с.

[4] Малышев Ф. М. Двойственность разностного и линейного методов в криптографии // Мат. вопросы криптографии. 2014. Т. 5, № 3. С. 35–47.

[5] Малышев Ф. М., Трифонов Д. И. Рассеивающие свойства XSLP-шифров // Мат. вопросы криптографии. 2016. Т. 7, № 3, С. 47–60.

[6] Холл М. Комбинаторика. М.: Мир, 1970. 424 c.

[7] Augot D., Finiasz M. Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions // Proc. IEEE Int. Symp. Information Theory (Istanbul, Turkey, July 7–12, 2013). Piscataway: IEEE, 2013. P. 1551–1555.

[8] Belov A. V., Los A. B., Rozhkov M. I. Some approaches to construct MDS matrices over a finite field // Commun. Appl. Math. Comput. 2017. Vol. 31, No. 2. P. 143–152.

[9] Belov A. V., Los A. B., Rozhkov M. I. Some classes of the MDS matrices over a finite field // Lobachevskii J. Math. 2017. Vol. 38, No. 5. P. 880–883.

[10] Couselo E., González S., Markov V., Nechaev A. Recursive MDS-codes and recursive differentiable quasigroups // Discrete Math. Appl. 1998. Vol. 8, No. 3. P. 217–245.

[11] Couselo E., González S., Markov V., Nechaev A. Parameters of recursive MDS-codes // Discrete Math. Appl. 2000. Vol. 10, No. 5. P. 433–453.

[12] Gupta K. C., Ray I. G. On constructions of MDS matrices from companion matrices for lightweight cryptography // Security Engineering and Intelligence Informatics : Proc. CD-ARES 2013 Workshops (Regensburg, Germany, Sept. 2–6, 2013). Heidelberg: Springer, 2013. P. 29–43 (Lect. Notes Comp. Sci.;
Vol. 8128).

[13] Gupta K. C., Ray I. G. On constructions of circulant MDS matrices for lightweight cryptography // Information Security Practice and Experience : Proc. 10th Int. Conf. (Fuzhou, China, May 5–8, 2014). Cham: Springer, 2014. P. 564–576. (Lect. Notes Comput. Sci.; Vol. 8434).

[14] Junod P., Vaudenay S. Perfect diffusion primitives for block ciphers: building efficient MDS matrices // Rev. Sel. Pap. 11th Int. Conf. Sel. Areas Cryptogr. (Waterloo, Canada, Aug. 9–10, 2004). Heidelberg: Springer, 2005. P. 84–99. (Lect. Notes Comput. Sci.; Vol. 3357).

[15] Matsui M. On correlation between the order of S-boxes and the strength of DES // Advances in Cryptology – EUROCRYPT’94: Proc. Workshop Theory Appl. Cryptogr. Tech. (Perugia, Italy, May 9–12, 1994). Heidelberg: Springer, 1995. P. 366–375. (Lect. Notes Comput. Sci.; Vol. 950).