|
Математические методы криптографии
Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода
М. Д. Сапегина Национальный исследовательский ядерный университет "МИФИ", г. Москва
Аннотация:
Развивается разработанный В. М. Фомичевым матрично-графовый подход к оценке характеристик нелинейности преобразований векторных пространств с помощью троичных матриц над мультипликативной полугруппой $\{0,1,2\}$ или орграфов, дуги которых помечены числами из $\{0,1,2\}$. Орграф $\Gamma$ с множеством вершин $\{1,\ldots ,n\}$ называется $\langle2\rangle$-примитивным, если при некотором натуральном $t$ для любых $i,j\in\{1,\ldots ,n\}$ найдётся путь из $i$ в $j$ длины $t$, проходящий через дугу с меткой $«2»$, наименьшее такое $t$ называется $\langle2\rangle$-экспонентом орграфа $\Gamma$ (обозначается $\langle2\rangle$-$\exp\Gamma$).
Преобразованию $g(x_1,\ldots ,x_n)$ множества $V_n$ с координатными функциями $g_1(x_1,\ldots ,x_n),\ldots ,g_n(x_1,\ldots ,x_n)$ соответствует $n$-вершинный орграф $\Gamma_\Theta(g)$, где дуга $(i,j)$ помечена числом $0$, $1$ или $2$ тогда и только тогда, когда $g_j$ зависит от $x_i$ соответственно фиктивно, линейно или нелинейно, $1\le i,j\le n$. Преобразование $g$ называют вполне нелинейным, если метка каждой дуги орграфа есть $«2»$. Преобразование $g$ называется $\langle2\rangle$-перфективным, если при некотором натуральном $t$ все дуги орграфа $\Gamma_\Theta(g^t)$ помечены числом $«2»$, наименьшее такое $t$ называется показателем полной нелинейности преобразования $g$ (обозначается $\langle2\rangle$-$nlg$).
Доказано: если в помеченном примитивном орграфе $\Gamma$ метка каждого простого контура содержит число $«2»$ и $\exp\Gamma=n$, то орграф $\Gamma$ является $\langle2\rangle$-примитивным и $\langle2\rangle$-$\exp\Gamma=\exp\Gamma$. Получена оценка $\langle2\rangle$-экспонента матрицы нелинейности $M$ порядка $2n$ раундовой функции блочных алгоритмов на основе сети Фейстеля с помощью $\langle2\rangle$-экспонента матрицы нелинейности $\Phi$ порядка $n$ функции усложнения: $\langle2\rangle$-$\exp M\le\langle2\rangle$-$\exp\Phi+2$. Эти результаты позволяют снизить сложность вычисления показателя полной нелинейности для некоторых преобразований $g$.
Представлены алгоритмы распознавания полной нелинейности преобразования $g$ и оценки показателя $\langle2\rangle$-$nlg$. Для случайных преобразований средняя сложность не превышает $2\gamma(\gamma+1)\log8n$, где $\langle2\rangle$-$nlg=\gamma$ и элементарная операция есть вычисление любой функции на любом входном наборе. Алгоритм применён для получения точных значений $\langle2\rangle$-$nlg$ раундовых подстановок $g$ алгоритмов DES и Магма, получены значения $5$ и $6$ соответственно.
Ключевые слова:
матрица нелинейности отображения, $\langle2\rangle$-примитивная матрица (орграф), $\langle2\rangle$-экспонент матрицы (орграфа), показатель полной нелинейности.
Образец цитирования:
М. Д. Сапегина, “Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода”, ПДМ. Приложение, 2019, № 12, 126–129
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma452 https://www.mathnet.ru/rus/pdma/y2019/i12/p126
|
Статистика просмотров: |
Страница аннотации: | 118 | PDF полного текста: | 39 | Список литературы: | 10 |
|