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. Эта оценка позволяет снизить сложность вычисления показателя полной нелинейности.

Скачать электронную версию публикации