Перемешивающие свойства некоторых классов подстановок на Fn21 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/13

Перемешивающие свойства некоторых классов подстановок на Fn21

Рассматриваются два класса подстановок на F^, таких, что каждая их координатная функция существенно зависит ровно от k переменных. Приведены алгоритм вычисления матэкса перемешивающей матрицы функций из данных классов и результаты экспериментального исследования их перемешивающих свойств.

Mixing properties for some classes of permutations on f?.pdf Для n G N обозначим через класс функций F : F^ ^ F^, где F = (f1... /n), таких, что координатные функции / : F^ ^ F2, i = 1,...,n, существенно зависят ровно от k переменных. В [1] описаны два метода построения таких функций. При использовании подстановок в качестве раундовых преобразований в итеративных блочных шифрах важно оценить их «перемешивающие» свойства [2], т.е. распространение существенной зависимости выходных переменных каждого раунда от входов первого раунда. В данной работе рассматриваются перемешивающие свойства функций двух подклассов класса . Под умножением матриц понимается их логическое умножение - с дизъюнкцией и конъюнкцией в качестве операций сложения и умножения соответственно. 1. Основные определения Определение 1 [2]. Перемешивающей матрицей функции F : F^ ^ F^, F(x1,... ,xn) = (/1(x1,... ,xn),..., /n(x1,... ,xn)), называется булева матрица M(F) = = (m^) порядка n, где m^ = 1, если и только если координатная функция / существенно зависит от переменной x^. Определение 2 [3]. Булева матрица M называется положительной (M > 0), если все её элементы равны 1; она называется примитивной, если M* > 0 при некотором t G N; наименьшее t с таким свойством называется экспонентом матрицы M, обозначается exp M; для непримитивной матрицы M будем считать exp M = то. Определение 3 [4]. Пусть M - булева матрица порядка n и i,j G {1,..., n}. Элементарным экспонентом ((i,j)-экспонентом) матрицы M называется наименьшее число y, такое, что для любого t > y элемент mj матрицы MM равен 1; обозначается (i,j)-exp M. Матрица элементарных экспонентов M(M) = ((i,j)-exp M) порядка n называется матэксом матрицы M. Проясним связь степени перемешивающей матрицы функции F и существенной зависимости выходов многораундового шифра от входов первого раунда при исполь- (t) 0 в матрице (M(F))t = "Ч У ' " -J " --- -- j-j",-,- - ^ ^ ,.„ij 1, то не обязательно такая зависимость есть. Таким образом, (i, j)-exp M(F) -это оценка снизу количества раундов, после которых j-й выход зависит от переменной ж., так же как exp M(F) -оценка снизу количества раундов, при котором достигается полное перемешивание (существенная зависимость всех выходов от всех входных переменных). Пример 1. Пусть F(ж1,ж2,ж3) = (ж2 ф ж3,ж1 ф ж3,ж3). Тогда зовании F в качестве раундового преобразования. Если (t)\\ • - + (t) mi/ I, то j-й выход t-го раунда не зависит от переменной ж.; если m. 010 1 0 0 111 100 0 1 0 111 (M(F))2 M(F) (2) 31 m32) = 1, но после второго раунда имеем F(F(ж1 ,ж2,ж3)) = (ж1 ф ж3 ф ж3,ж2 ф Ф ж3 ф ж3,ж3) = (ж1,ж2,ж3) -зависимости первого и второго выходов от ж3 нет. 2. Класс функций Snk В [1, 5] предложен следующий метод построения функций F(ж1,... , жп) = (/1(ж1, • • • , жга) , • • • , /п(ж1, • • • , жп)) Е Fn,k: 1) строим функцию С(жь...,жк) = (g1 (ж1, • • • , жк ),...,gk (ж1,...,жк)) Е Fk,k (например, способом, описанным в [6]); 2) для i = 1,..., k полагаем /г(ж1,..., жп) = ^.(ж1,..., жk), переменные ж^,...,жп фиктивны для /i; 3) для i = k + 1,..., n полагаем /г(ж1,..., жп) = ж. ф ^.(ж1,..., жг-1), где h. - любая функция, существенно зависящая от любых (k - 1) переменных из ж1,... , жг-1. В [5] доказано, что полученная функция F является подстановкой на Fn. Обозначим Sn,k класс функций, которые можно построить таким способом. По построению, каждая координатная функция /i функции F Е Sn,k существенно зависит ровно от k переменных; таким образом, Sn,k С Fn,k. Перемешивающая матрица функции F Е Sn,k имеет следующий вид: m ( k 1 1 1 1 \\ 0 0 0 0 0 1 0 0 0 0 00 10 1 M(F) 11 ... 1 * * ... * ... * * * * Здесь m.j = 1 для всех i, j ^ k; m.j = 0 для всех i ^ k, j > k; m.. = 1 для всех i = = 1,... , n; в позициях, отмеченных «*», могут быть как нули, так и единицы (по k единиц в каждой строке). Таким образом, при всех t Е N для матрицы (M(F))t = ^m-*^ выполняется mj = 0 для всех i ^ k, j > k, поэтому матрица M (F) непримитивная и exp M(F) = то. Оценим элементарные экспоненты матрицы M (F). Из [7] (утверждение 1, а при I = {i}, J = {j}) следует, что если an = 1 или ajj = 1 в матрице A = (aj) и aj = 1 в матрице AY = , причём y - минимальное с таким условием, то (i, j)-exp A = y. В матрице M(F) все диагональные элементы единичные, поэтому при возведении матрицы в степень единицы в ней ведут себя «монотонно»: если m(k) = 1 в матрице (M(F))k, то mj = 1 в матрице (M(F))* для всех t ^ k. Получаем алгоритм 1 вычисления матэкса матрицы M (F), который состоит в возведении матрицы в степень до тех пор, пока в ней не перестанут появляться новые единицы. Алгоритм 1. Вычисление матэкса матрицы с единичной диагональю Вход: M = (mj) - булева матрица порядка n; m^ = 1 для всех i = 1,... , n. Выход: M(M) = (rij). 1: Для i = 1 , . . . , n 2: Для j = 1, . . . , n 1, mj = 1, oo иначе. 3 rij C := M. 4: Для k = 2, 3, . . . 5: B := C; C := BM; D := B 0 C (поэлементно), пусть D = (dij). 6: Если D - нулевая матрица, то выход. 7: Для i = 1 , . . . , n Для j = 1 , . . . , n Если dij = 1, то rij := k. Для M(M(F)) = (rij) обозначим yF = max{rij : rij = то} -максимальный конечi,j ный элементарный экспонент перемешивающей матрицы функции F. Содержательный смысл этой величины следующий: при использовании F в качестве раундового преобразования в итеративном блочном шифре для количества раундов yf достигается максимально возможная «степень перемешивания» - зависимость выходов последнего раунда от входов первого раунда, которая не изменится при увеличении числа раундов. Алгоритм 1 вычисления матэкса и алгоритм генерации случайной функции класса реализованы программно. Эксперименты показали, что yf принимает значения от 2 до 5 для функций F G при n = 4,... , 26; как и ожидалось, yf возрастает с ростом разности n - k, т. е. с увеличением числа нулей в перемешивающей матрице функции F. 3. Класс функций k Если k|n, то можно предложить следующий способ построения функций F = = (/1,...,/n) G . Пусть s = n/k, построим s функций G1,...,Gs G , Gi = = (g(i),... , gfci^ , i = 1,... , s, и положим /tfc+i(xb ... ,xn) = g?+1)(xtfc+1,...,x(t+1)fc), t = 0,... , s - 1, i = 1,..., k. Класс функций, полученных таким способом, будем обозначать . Схема построения функции F приведена на рис. 1, её перемешивающая матрица - на рис. 2. 11. .1 00. . 0 . . 00. .0 11. .1 00. . 0 . . 00. .0 00. .0 11. . 1 . . 00. .0 00. .0 11. . 1 . . 00. .0 00. .0 00. . 0 . . 11. . 1 \\00. .0 00. . 0 . . 11. .. 1 Рис. 2 /1 ^fc ^fc x1 xfc xfc+1 x2fc G1 G2 M(F) -/n-fc+1 xn-fc+1 xn Gs Рис. 1 Видно, что (M(F))* = M(F) для всех t G N, поэтому (i,j)- exp M(F) 1, если mij = 1 , иначе, где M(F) = (mij). Для достижения перемешивающих свойств функции класса можно применять в качестве преобразований замены только в SP-сетях [2, с. 290], чередуя их с преобразованиями перестановки.

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

существенная зависимость функции от переменной, перемешивающие свойства функций, элементарный экспонент, матэкс, essential dependence of a function on a variable, mixing properties of the function, elementary exponent

Авторы

ФИООрганизацияДополнительноE-mail
Карпова Любовь АлександровнаТомский государственный университетстуденткаlubakarpova1135@gmail.com
Панкратова Ирина АнатольевнаТомский государственный университеткандидат физико-математических наук, доцент, заведующая лабораторией компьютерной криптографииpank@isc.tsu.ru
Всего: 2

Ссылки

Agibalov G. P. Substitution block ciphers with functional keys // Прикладная дискретная математика. 2017. №38. С. 57-65.
Фомичев В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010. 424 с.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.
Фомичев В. М. О характеристиках локально примитивных орграфов и матриц // Прикладная дискретная математика. Приложение. 2017. №10. С. 96-99.
Панкратова И. А. Об обратимости векторных булевых функций // Прикладная дискретная математика. Приложение. 2015. №8. С. 35-37.
Pankratova I. A. Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables // Материалы Междунар. науч. конгресса по информатике: Информационные системы и технологии. Республика Беларусь, Минск, 24-27 окт. 2016. Минск: БГУ, 2016. С. 519-521.
Кяжин С. Н., Фомичев В. М. Локальная примитивность графов и неотрицательных матриц // Прикладная дискретная математика. 2014. №3. С. 68-80.
 Перемешивающие свойства некоторых классов подстановок на Fn21 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/13

Перемешивающие свойства некоторых классов подстановок на Fn21 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/13