Experimental research on exponents of mixing matrices for generalized feistel networks.pdf Введение Обозначим через R(n, r, k) класс регистров сдвига длины n над множеством V двоичных r-мерных векторов с k обратными связями, n, r > 1, k ^ 1. Класс R(n, r, k) обобщает класс R(2,r, 1), относящийся к оригинальным сетям Фейстеля. Увеличение длины базового регистра способствует увеличению производительности шифрования и вместе с тем числа раундов, достаточного для перемешивания входных данных. Свойства обобщённых сетей Фейстеля (ОСФ) исследовались как в зарубежных [1-4], так и в отечественных работах [5-7]. На основе ОСФ построены алгоритмы CAST-256, MARS, SMS4, CLEFIA, Piccolo, HIGHT и др. В [3] исследованы классы сетей R(n,r, n/2), n - чётное (эти сети названы обобщёнными сетями Фей-стеля 2-го типа). Отмечено, что вычислительная реализация таких сетей допускает распараллеливание и количество раундов, необходимых для перемешивания входных данных, оценивается снизу величиной порядка n. С целью улучшения перемешивающих свойств сетей из класса R(n, r, n/2) в [3] предложено заменить циклический сдвиг подблоков перестановками, что позволило понизить оценку числа раундов полного перемешивания подблоков до 2 log2 n. В [4] исследованы классы сетей R(n, r, 1), R(n, r, n/2), R(n, r, n - 1) (ОСФ 1-го, 2-го и 3-го типа соответственно). С помощью орграфа перемешивания подблоков получены оценки числа раундов перемешивания входных подблоков: (n - 1)2 + 1 для R(n, r, 1); n для двух других. Отметим, что перемешивание входных подблоков не обеспечивает перемешивания битов (зависимости каждого бита выходного блока от всех входных битов), что сохраняет возможность применения некоторых криптоаналитических атак. Следовательно, исследование битового перемешивания для ОСФ является актуальным. Работа посвящена перемешивающим свойствам раундовых функций ОСФ, построенных на основе классов регистров сдвига R(4, 32, k), k = 1, 2, 3, т. е. ОСФ 1-го, 2-го и 3-го типа соответственно. Для исследования перемешивающих свойств используется оценочный матрично-графовый подход, который заключается в построении перемешивающей матрицы M для раундовой функции и экспериментальном определении значения её экспонента (exp M). Значение exp M оценивает снизу число итераций, необходимое для полного перемешивания входных данных, то есть для обеспечения существенной зависимости каждой координатной булевой функции от всех входных переменных. Приведены результаты экспериментального исследования, направленного на выбор параметров регистровых функций, при которых реализуется наиболее быстрое полное перемешивание входных данных. 1. ОСФ на основе класса регистров сдвига R(4,32,k) Сети классов регистров сдвига R(4, 32,1), R(4, 32, 2), R(4, 32, 3) реализуют преобразования , g(2), g(3) соответственно: g(1)(Xi,X2,X3,X4) = (Fq(Xi) e X2,X3,X4,Xi); (1) g(2)(Xi,X2,X3,X4) = (Fq (Xi) e X2,X3,Fw (X3) e X4,Xi); (2) g(3)(Xi, X2, X3, X4) = (Fq (Xi) e X2, Fw (X2) e X3, Fv (X3) e X4, Xi), (3) где q,w,v,Xi,X2,X3,X4 G V32; (Xi,X2,X3,X4) -открытый текст; q,w,v - раундовые ключи (подключи в случае схем типа 2 и 3); Fa : V32 ^ V32 - функция усложнения, реализуемая при раундовом ключе (подключе) a G {q, w, v}. Схемы раунда шифрования для ОСФ 1-го, 2-го и 3-го типа представлены на рис. 1, выходные подблоки Yi, Y2, Y3, Y определены в соответствии с формулами (1)-(3). A'l Х2 A3 Х4 Х\ Х2 Х3 Д"4 Х\ Х2 Хз Л"4 Yl 72 УЗ У4 П 72 73 74 7l У2 73 У4 Рис. 1. Схемы раунда шифрования для ОСФ 1-го, 2-го и 3-го типов 2. Экспериментальное исследование перемешивающих свойств ОСФ при некоторых вариантах функции усложнения Раундовые функции алгоритмов шифрования на основе ОСФ 2-го и 3-го типа могут использовать идентичные функции усложнения, что позволяет применить распараллеливание при вычислении раундовой функции. В эксперименте в качестве функции Fa, a Е {q,w,v}, использована функция усложнения отечественного алгоритма блочного шифрования ГОСТ 28147-89 (с различными вариантами подмешивания раундовых ключей), свойства которой хорошо изучены. Определим функцию усложения Fa: F„(Xi)= Tieft(Ss,4(Xi * a)), где a,Xi Е V32, i = 1,2,3; * означает или XOR-суммирование двоичных векторов (обозначаемое ф), или сложение по модулю 232 (обозначаемое +); Sg)4 = (Si,..., Sg); Si,..., Sg - преобразования множества V4 (s-боксы алгоритма ГОСТ 28147-89); Tleft - циклический сдвиг векторов из V32 на 11 битов влево. Используя (1), (2) и (3), построим перемешивающие матрицы M(g(1)), M(g(2)), M(g(3)). В матрицах M(g(j)), i = 1, 2, 3, обозначим подматрицы размера 32 х 32: 0 - нулевая (состоящая из нулей) подматрица; E - единичная подматрица; Ф - "0(i, j), где "0(i, j) - 1 ^ функция gj ) зависит существенно от переменной x, i, j Е {1,... , 32}; Ф = 0(i, j), где ф(г, j) = 1 ^ функция gjj) зависит существенно от переменной Xj, i Е {65,..., 96}, j Е {65,..., 96}; Л = A(i, j), где A(i, j) = 1 ^ функция gjj) зависит существенно от переменной Xj, i Е {33,... , 64}, j Е {33,... , 64}. Таким образом, матрицы M (g(j)), i = 1 , 2, 3, имеют следующий вид: Ф 0 0 E E 0 0 0 0 E 0 0 0 E 0 Ф 0 0 E E 0 0 0 0 E Ф 0 0 0 E 0 Ф 0 0 E E Л 0 0 0 E Ф 0 0 0 E 0 M (g(1)) M (g(2)) M (g(3)) В таблице приведены результаты вычислительного эксперимента по определению значений экспонентов перемешивающих матриц M(g(1)), M(g(2)), M(g(3)) в зависимости от способов построения функций Fa. Значения экспонентов перемешивающих матриц M(g(1)), M(g(2)), M(g(3)) Функция Fa exp M (g(1)) exp M (g(2)) exp M (g(3)) Teft (Sg,4 (Xi ф a)) 14 12 12 Tleft(S8,4(Xi + a)) 9 7 7 В результате экспериментальных исследований получены некоторые рекомендации по выбору параметров функций обратной связи регистров сдвига, при которых реализуется наиболее быстрое полное перемешивание входных данных. В частности, к улучшению перемешивающих свойств приводит: 1) Замена циклического левого сдвига на 11 бит инволюцией координат вектора (Tinv(x1,... ,x32) = (x32,... ,x1)). При таком изменении expM(g(1)) = 8, expM(g(2)) = 6, expM(g(3)) = 6. 2) Укрупнение s-боксов (использование преобразований S1,... , S4 множества Vg). В этом случае exp M(g(1)) = 8, exp M(g(2)) = 6, exp M(g(3)) = 6. 3) Использование инволютивной перестановки битов в начальных подблоках, являющихся аргументами функции усложнения (для схемы 2-го типа это подблоки 2 и 4). В этом случае exp M(g(2)) = 5. 4) Замена циклического сдвига подблоков другой перестановкой. Например, в схеме 3-го типа можно заменить перестановку подблоков п = {4,1, 2, 3} на п = = {4,1, 3, 2}. В этом случае exp M(g(3)) = 5. Выводы Экспериментально получены значения экспонентов раундовых перемешивающих матриц ОСФ, построенных на основе регистров сдвига длины 4. Это позволяет сформулировать обоснованные рекомендации по выбору числа итераций раундового преобразования, при котором обеспечивается существенная зависимость каждой координатной функции выхода от всех переменных входа. Даны рекомендации по выбору параметров функций обратной связи регистров сдвига, при которых реализуется наиболее быстрое перемешивание входных данных.

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