Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/37

Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода

Развивается разработанный В. М. Фомичевым матрично-графовый подход к оценке характеристик нелинейности преобразований векторных пространств с помощью троичных матриц над мультипликативной полугруппой {0,1,2} или орграфов, дуги которых помечены числами из {0,1,2}. Орграф Г с множеством вершин {1,...,n} называется (2)-примитивным, если при некотором натуральном t для любых i, j Е {1,..., n} найдётся путь из i в j длины t, проходящий через дугу с меткой «2», наименьшее такое t называется (2)-экспонентом орграфа Г (обозначается (2)-expT). Преобразованию g(x1,...,xn) множества Vn с координатными функциями g1(x1,..., xn),..., gn(x1,..., xn) соответствует n-вершинный орграф Г©(д), где дуга (i, j) помечена числом 0, 1 или 2 тогда и только тогда, когда gj зависит от Xi соответственно фиктивно, линейно или нелинейно, 1 ^ i,j ^ n. Преобразование g называют вполне нелинейным, если метка каждой дуги орграфа есть «2». Преобразование g называется (2)-перфективным, если при некотором натуральном t все дуги орграфа Г©(g*) помечены числом «2», наименьшее такое t называется показателем полной нелинейности преобразования g (обозначается (2)-nlg). Доказано: если в помеченном примитивном орграфе Г метка каждого простого контура содержит число «2» и exp Г = n, то орграф Г является (2)-примитивным и (2)-ехрГ = exp Г. Получена оценка (2)-экспонента матрицы нелинейности M порядка 2n раундовой функции блочных алгоритмов на основе сети Фейстеля с помощью (2)-экспонента матрицы нелинейности Ф порядка n функции усложнения: (2)-ехр M ^ (2)-ехрФ + 2. Эти результаты позволяют снизить сложность вычисления показателя полной нелинейности для некоторых преобразований g. Представлены алгоритмы распознавания полной нелинейности преобразования g и оценки показателя (2)-nlg. Для случайных преобразований средняя сложность не превышает 2y(7 + 1) log8n, где (2)-nlg = 7 и элементарная операция есть вычисление любой функции на любом входном наборе. Алгоритм применён для получения точных значений (2)-nlg раундовых подстановок g алгоритмов DES и Магма, получены значения 5 и 6 соответственно.

Nonlinearity characteristics estimations for function compositions over vector spaces by the matrix-graph approach.pdf Введение Необходимым требованием к свойствам функций, применяемых в алгоритмах защиты данных в информационных системах, является нелинейность, иначе секретный параметр системы может быть раскрыт противником с помощью вычислительно несложного решения системы линейных уравнений [1]. Для решения актуальных задач, направленных на изучение свойства нелинейности композиций отображений векторных пространств, используется оценочный матрично-графовый подход (МГП). В работе представлены результаты, развивающие предложенный В. М. Фомичевым в [2] МГП для оценки характеристик нелинейности отображений на основе свойств троичных матриц над мультипликативной полугруппой {0,1,2}. Этот подход обобщает МГП к исследованию примитивности и экспонентов 0.1-матриц и соответствующих орграфов. 1. Мультипликативный моноид троичных матриц (помеченных орграфов) Пусть G = {0,1, 2} -мультипликативная коммутативная полугруппа с операцией, определяемой равенствами: a0 = 0 для любого a Е G; ab = max{a, b} для любых a, b = 0. Матрица любого размера над G называется троичной матрицей. Троичная матрица называется особенной, если она имеет нулевую строку или нулевой столбец. Умножение троичной матрицы A = (a^j) размера n х m на матрицу B = (bj,j) размера m х r задается следующим образом: AB = C = (cj,j), где C - матрица размера n х r, cj,j = max{aj,1b1,j,''' , aj,mbm,j} для любых допустимых i, j, умножение элементов выполнено в полугруппе G. Неособенная матрица называется 2-матрицей, если каждый элемент матрицы равен 2. При n > 1 троичной матрице M = (mj,j) порядка n биективно соответствует помеченный n-вершинный орграф Г, у которого дуга (i, j) имеет метку mj,j, 0 ^ i, j < n, где метка «0» равносильна отсутствию дуги в орграфе. Матрица M над полугруппой G называется матрицей меток орграфа Г и обозначается M(Г). Помеченный орграф Г с матрицей меток M(Г) = (2)n, где (2)n - матрица, все элементы которой равны 2, называется полным 2-графом. Помеченный орграф Г называется (2)-примитивным, если Г* является полным 2-графом при некотором t Е N, и наименьшее t с таким свойством называется (2)-экспонентом орграфа Г (обозначается (2)-exp Г). Матрица M над G при n = m называется (2)-примитивной, если M* есть 2-матрица при некотором t Е N. Наименьшее t с таким свойством обозначается (2)-exp M и называется (2)-экспонентом матрицы M. Если M* есть 2-матрица при некотором t Е N, то MT есть 2-матрица при любом т > t. Указанное соответствие троичных матриц и помеченных орграфов есть биекция [2], поэтому орграф Г (2)-примитивный, если и только если (2)-примитивна матрица M(Г), и (2)-expT = (2)-exp M. 2. Нелинейные свойства преобразований векторных пространств Приведём необходимые определения [2]. Пусть P - конечное поле. Обозначим {/j(xo,''' , xn-1) : j = 0,''' , m - 1} множество координатных функций отображения ^ : Pn ^ Pm. Функции ^ соответствует троичная матрица M©( 1 - n2-t. Лемма 3. При n > 3 среди всех преобразований множества Vn доля вполне нелинейных преобразований не меньше 1 - n22-2" 11. На основе леммы 1 реализован алгоритм распознавания полной нелинейности различных степеней преобразования g. Для этого для всех i = 1, . . . , n фиксируем вектор ei и генерируем пары случайных векторов (as,bs),s = 1,...,t(i), и при h = 1, 2, 3,... вычисляем = gh(as ф ei) ф gh(as) ф gh(bs ф ei) ф gh(bs). Если при некоторых s ^ t(i) и h Е N (из вероятностных соображений по отношению к случайным функциям взято t(i) = log4n, т.е. s = 1,...,log4n, так как при t = log4n P[I(V(ei,1,..., ем)) = {1,..., n}] > 0,75) выполнено I(V(eh^1,..., e£t(i))) = {1,..., n} для всех i = 1,..., n, то преобразование gh вполне нелинейное и (2)-nlg ^ h. Данный алгоритм позволяет оценить сверху показатель полной нелинейности преобразования g. Оценим вычислительную сложность алгоритма. Элементарной операцией будем считать вычисление значения любой функции на любом входном наборе. Теорема 3. Пусть g есть (2)-перфективное преобразование множества Vn и (2)-n/g = y. Если при случайном независимом и равновероятном выборе из Vn х Vn пар векторов (as,bs) величины ehs, s = 1,''', t, независимы и распределены равномерно, h = 1, 2,''', где ehis = gh(as ф ej) ф gh(as) ф gh(bs ф ej) ф gh(bs), то средняя сложность алгоритма с параметром t = log4n не превышает 2y (y + 1) log8n. С помощью разработанного алгоритма с параметром t = 100 (поскольку тогда P[1 (V(ej,1,''', £j,t)) = {1,''', 64}] ^ 1) определены верхние оценки показателей полной нелинейности раундовых подстановок алгоритмов DES и Магма. Для алгоритма DES она равна 5, для алгоритма Магма - 6. В [5] с помощью МГП на основе свойств троичных матриц получены нижние оценки показателей полной нелинейности для раундовых подстановок алгоритмов DES и Магма. Они совпадают с полученными верхними оценками показателей полной нелинейности. Таким образом, для алгоритма DES наименьшая степень, в которой раун-довая подстановка является вполне нелинейной, равно 5, для алгоритма Магма - 6. Выводы Разработан и реализован алгоритм для вычисления верхней оценки показателя полной нелинейности отображений со сложностью, не превышающей 2y(7 + 1)log8n, где показатель полной нелинейности исследуемого преобразования (2)-n/g = 7 и элементарная операция есть вычисление любой функции на любом входном наборе. Получены точные значения показателей полной нелинейности раундовых подстановок алгоритмов DES и Магма, они равны 5 и 6 соответственно. Доказано достаточное условие равенства (2)-expT = exp Г. Получена оценка (2)-экспонента матрицы нелинейности M порядка 2n раундовой функции блочных алгоритмов на основе сети Фей-стеля с помощью (2)-экспонента матрицы нелинейности Ф порядка n функции усложнения, а именно: (2)-exp M ^ (2)-expФ + 2. Эта оценка позволяет снизить сложность вычисления показателя полной нелинейности.

Ключевые слова

матрица нелинейности отображения, (2)-примитивная матрица (орграф), (2)-экспонент матрицы (орграфа), показатель полной нелинейности, nonlinearity matrix of function, (2) -primitive matrix (digraph), (2)-exponent of the matrix (digraph), total nonlinearity index

Авторы

ФИООрганизацияДополнительноE-mail
Сапегина Марина ДмитриевнаНИЯУ МИФИстудентка кафедры №42 криптологии и кибербезопасностиmdsapegina@gmail.com
Всего: 1

Ссылки

Фомичев В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010.
Фомичев В. М. О производительности некоторых итеративных алгоритмов блочного шифрования из класса WBC // New Trends in Coding Systems and Techniques. LDN: Intech Publishing, 2019. С. 14.
Фомичев В. М. Криптографические методы защиты информации. В 2 ч. Ч. 1. Математические аспекты: учебник для академического бакалавриата. М.: ЮРАЙТ, 2016.
Сапегина М. Д. Оценка характеристик нелинейности раундовых подстановок алгоритмов «DES» и «Магма» // Информационная безопасность в банковско-финансовой сфере. Сб. науч. работ участников Междунар. молодежной науч.-практич. конф. в рамках V Меж-дунар. форума «Как попасть в пятерку?». М.: Прометей, 2018. С. 6.
 Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/37

Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/37