Том 27, номер 4, 2020 г., Стр. 131-151

УДК 519.17
Фомичёв В. М.
Оценка характеристик нелинейности итеративных преобразований векторного пространства

Аннотация:
Представлены теоретические основы матрично-графового подхода (МГП) к оценке характеристик множеств существенных и нелинейных переменных композиции преобразований $n$-мерного векторного пространства над полем. Преобразованию соответствует троичная матрица нелинейности, где в $i$-й строке и $j$-м столбце матрицы записано число 0, 1 или 2 тогда и только тогда, когда $j$-я координатная функция преобразования зависит от $i$-й переменной фиктивно, линейно или нелинейно соответственно, $0 \le i$, $j < n$. Основой МГП является неравенство, согласно которому матрица нелинейности произведения преобразований не больше (неравенство поэлементное) произведения матриц нелинейности тех же преобразований.
Определена операция умножения троичных матриц. Исследованы свойства мультипликативного моноида всех троичных матриц порядка $n$ без нулевых строк и столбцов и биективно соответствующего ему моноида $\mathbb {\Gamma}_n$ всех $n$-вершинных орграфов с дугами, помеченными числами 0, 1, 2, где каждая вершина имеет ненулевые полустепени захода и исхода. С помощью МГП оценена глубина итерации (число умножаемых) преобразований, при которой могут быть достигнуты 4 вида нелинейности преобразований, при которых каждая или некоторые координатные функции произведения преобразований могут зависеть нелинейно от всех или хотя бы от некоторых переменных.
Представлены результаты исследования нелинейности итераций раундовых подстановок блочных шифров DES и «Магма».
Библиогр. 18.

Ключевые слова: матрица (орграф) нелинейности преобразования, $\left \langle \alpha \right \rangle$-примитивная матрица (орграф), $\left \langle \alpha \right \rangle$-экспонент матрицы (орграфа), $\left \langle \alpha \right \rangle$-перфективное преобразование.

DOI: 10.33048/daio.2020.27.686

Фомичёв Владимир Михайлович ^1,2,3
1. Финансовый университет при Правительстве Российской Федерации,
Ленинградский пр., 49, 125993 Москва, Россия
2. Национальный исследовательский ядерный университет «МИФИ»,
Каширское ш., 31, 115409 Москва, Россия
3. Институт проблем информатики ФИЦ «Информатика и управление» РАН,
ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
е-mail: fomichev.2016@yandex.ru

Статья поступила 5 мая 2020 г.
После доработки — 28 мая 2020 г.
Принята к публикации 2 июня 2020 г.

Литература

[1] Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. 448 с.

[2] Фомичёв В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010. 424 с.

[3] Фомичёв В. М., Мельников Д. А. Криптографические методы защиты информации. Ч. 1. Математические аспекты. М.: ЮРАЙТ, 2016. 209 с.

[4] Фомичёв В. М., Авезова Я. Э., Коренева А. М., Кяжин С. Н. Примитивность и локальная примитивность орграфов и неотрицательных матриц // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 95–125.

[5] Frobenius G. Über Matrizen aus nicht negativen Elementen // Berl. Ber. 1912. P. 456–477. [German].

[6] Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Z. 1950. Bd. 52. S. 642–648. [German].

[7] Perkins P. A theorem on regular graphs // Pac. J. Math. 1961. Vol. 2. P. 1529–1533.

[8] Dulmage A. L., Mendelsohn N. S. The exponent of a primitive matrix // Can. Math. Bull. 1962. Vol. 5, No. 3. P. 241–244.

[9] Dulmage A. L., Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Ill. J. Math. 1964. Vol. 8, No. 4. P. 642–656.

[10] Brualdi R. A., Liu B. Generalized exponents of primitive directed graphs // J. Graph Theory. 1990. Vol. 14, No. 4. P. 483–499.

[11] Neufeld S. W. A diameter bound on the exponent of a primitive directed graph // Linear Algebra Appl. 1996. Vol. 245. P. 27–47.

[12] Liu B. Generalized exponents of Boolean matrices // Linear Algebra Appl. 2003. Vol. 373. P. 169–182.

[13] Nyberg K. Generalized Feistel networks // Advances in Cryptology — ASIACRYPT’96. Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. (Kyongju, Korea, Nov. 3–7, 1996). Heidelberg: Springer, 1996. P. 91–104. (Lect. Notes Comput. Sci.; Vol. 1163).

[14] Suzaki T., Minematsu K. Improving the generalized Feistel // Fast Software Encryption. Proc. 17th Int. Workshop (Seoul, Korea, Feb. 7–10, 2010). Heidelberg: Springer, 2010. P. 19–39. (Lect. Notes Comput. Sci.; Vol. 6147).

[15] Berger T., Francq J., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput // IEEE Trans. Comput. 2016. Vol. 65, No. 7. P. 2074–2089.

[16] Berger T., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation // Selected Areas in Cryptography — SAC 2013. Proc. 20th Int. Conf. (Burnaby, Canada, Aug. 14–16, 2013). Heidelberg: Springer, 2014. P. 289–305. (Lect. Notes Comput. Sci.; Vol. 8282).

[17] Fomichev V. M., Koreneva A. M., Miftakhutdinova A. R., Zadorozhny D. I. Evaluation of the maximum performance of block encryption algorithms // Мат. вопр. криптогр. 2019. Т. 10, № 2. P. 181–190.

[18] Fomichev V. M., Koreneva A. M. Encryption performance and security of certain wide block ciphers // J. Comput. Virol. Hack. Tech. 2020. Available at https://link.springer.com/article/10.1007/s11416-020-00351-1 (accessed June 5, 2020).