On a heuristic approach to constructing bijective vector boolean functions with given cryptographic properties.pdf Биективные векторные булевы функции (подстановки) используются в качестве нелинейных примитивов многих симметричных шифров. Построение подстановок размерности n 8 бит с криптографическими характеристиками, гарантирующими стойкость шифров к разностному и линейному методам криптоанализа, является сложной задачей. В [1] представлены спектрально-линейный и спектрально-разностный методы генерации подстановок, основанные на итеративном улучшении их криптографических характеристик путём умножения на транспозиции. В [2, 3] описана обобщённая конструкция векторных булевых (2m, 2т)-функций, использующая мономиальные и произвольные подстановки размерности m. В случае m = 4 экспериментально найдены 768 наборов показателей степеней мономов, перспективных для построения 8-битовых 6-равномерных подстановок, имеющих нелинейность 108 и алгебраическую степень 7 при правильном выборе вспомогательных 4-битовых подстановок. В настоящей работе предложен эвристический алгоритм поиска таких 4-битовых подстановок в обобщённой конструкции, при этом используются идеи спектральнолинейного и спектрально-разностного методов. Обозначим: Vn - n-мерное векторное пространство над полем из двух элементов F2; VJ = Vn \\ {0}; S(Vn) - симметрическую группу всех подстановок пространства V^; F2n - конечное поле из 2n элементов. Пусть a Е Vn, b Е Vm. Конкатенацию двух векторов будем обозначать как a\\\\b Е Vn+m. Скалярным произведением двух векторов a,b Е Vn называется элемент поля F2, вычисляемый по формуле (a,b) = an-1bn-1 + + ... + a0b0. Транспозиция - это цикл длины 2. Умножение подстановки G на транспозицию справа G ◦ (i1, i2) приводит к транспозиции элементов i1 и i2 в верхней строке подстановки G [4, с. 51], другими словами, в нижней строке подстановки G меняются местами образы элементов i1 и i2. Приведём определения некоторых криптографических характеристик подстановок. Подстановка F G S(Vn) называется Дифференциально Sp-равномерной, если SF = max SF (a,b), a€Vnx ,b€Vn где SF(a, b) = |{x G Vn : F(x + a) + F(x) = b}|. Значение SF называется показателем дифференциальной равномерности подстановки F. Таблицей распределения разностей (Difference Distribution Table -DDT) подстановки F называется такая 2n x 2n таблица DDTF, что DDTF[a, b] = Sp(a,b). Для всех элементов S G {0, 2,..., 2n} определим множества Dp(S) = {(a, b) G V* x Vn : SF(a, b) = S}. Разностным спектром подстановки F называется множество пар DF = {(S, |DF(S)|)}. Преобразованием Уолша - Адамара WF(a,b) подстановки F G S(Vn) называется отображение WF : Vn x Vn Z, заданное равенством Wp(a,b) = £ (-1)bxHAp(x)) для любых a,b G Vn. xev„ Линейность tF подстановки F определяется как tp = max |Wp(a, b)|. Нелиней-a€Vn, beV* ность Np подстановки F вычисляется по формуле Np = 2n-1 - -tF. Таблицей линейных приближений (Linear Approximation Table -LAT) [5] подстановки F называется такая 2n x 2n таблица LATF, что LATF [a, b] = tF(a, b), где tp(a, b) = |{x G Vn : (a, x) = (b, F(x))}| - 2n-1 = - WF(a, b). Для всех элементов t G {0, 2,..., 2n-1} определим множества Lp(t) = {(a,b) G Vn x x V* : |tp(a, b) | = t}. Линейным спектром подстановки F называется множество пар Lp = {(t, |Lp(t)|)}. Алгебраической степенью deg(F) подстановки F называется минимальная степень многочленов Жегалкина для всевозможных линейных комбинаций её координатных функций (a, F(x)) по всем a G V*: deg(F) = min deg((a, F(x))). aev„x Рассмотрим (2m, 2т)-функцию F(x1, x2) = y1 ||y2, где x1, x2, y1, y2 G Vm, задаваемую следующей обобщённой конструкцией [2]: y1 = G1(x1, x2) = a в x1 • x2, 7T1(X1), x2 = 0, x2 = 0, y2 = G2(x1, x2) = Y 6 x 1 x2, p2(x2), x1 = 0, x1 = 0. (1) В силу существования взаимно-однозначного отображения Vm F2m в (1) и далее операции возведения в степень и умножения производятся в поле F2m . Параметрами функции (1) являются набор показателей степеней (a,e,Y,S) мономиальных подстановок и значения подстановок Г1, п2 G S(Vm). Без ограничения общности будем предполагать, что Г1(0) = 0, Г (0) = 0. Отметим, что конструкция (1) основана на структуре типа «бабочка», предложенной в [6] и полученной при изучении декомпозиции APN-подстановки Диллона [7], и допускает TU-представление [8]. (2) Далее исследуем обобщённую конструкцию (1) в случае m = 4 с одним из 768 наборов параметров (а, в, Y, ^), приведённых в [3]. Поскольку подстановки Г1,п2 в (1) выбираются независимо от параметров (а, в, Y,^), предложим эвристический алгоритм поиска таких 4-битовых подстановок Г1,Г2, чтобы итоговая 8-битовая подстановка (1) обладала заданными криптографическими характеристиками Nf = 108, 6f = 6. Вопрос о возможности получения с использованием конструкции (1) подстановок с NF > 108, dF С 6 требует дополнительного исследования. Идея алгоритма 1 заключается в итеративном умножении начальных случайно сгенерированных 4-битовых подстановок на транспозиции и отбора среди полученных по формулам (1) 8-битовых подстановок, лучших по нелинейности, показателю дифференциальной равномерности и соответствующим значениям в линейном и разностном спектрах. Алгоритм 1. Вход: Подстановка F G S(V8), построенная по формулам (1) с использованием одного из 768 наборов параметров (а, в, Y, ^) [3] и произвольных 4-битовых подстановок 7Г1, п2 (2), с криптографическими характеристиками G-1 > 40 или 5f > 6. Параметры: Num_Trans - количество умножений на транспозиции, Num_Best - количество отбираемых пар (Г1,Г2) на каждой итерации алгоритма. 1: Сформировать список Best из одной пары подстановок (Г1,Г2). 2: Для всех пар подстановок (Г1,Г2) из списка Best: 3: запомнить пару (Г1,Г2) как просмотренную; 4: псевдослучайно выбрать номер t G {1, 2}. 5: Для i = 1, . . . , Num_Trans 6: псевдослучайно выбрать x, y G V^x, x = y, получить подстановку rt = rt◦ (x, y). 7: Если пара (Г1,Г2) ещё не просмотрена, то 8: встроить rt в F; 9: вычислить набор характеристик подстановки (£F, JF, |LF(£F/2)|, |DF(JF)|); 10: добавить пару (Г1,Г2) в список Best. 11: Отобрать (по принципу многоуровневой сортировки по возрастанию) Num_Best лучших (т. е. с меньшими значениями с учётом приоритетов) из всех наборов характеристик подстановок F, порождённых парами (Г1,Г2) из текущего списка Best, считая, что в наборе приоритет убывает от G-1 к |DF(5F)|. 12: Если в наилучшем наборе значения ^.F = 40 и dF = 6, то 13: Вывести подстановки Г1, Г2, порождающие подстановку F, 14: иначе 15: Сформировать новый список Best из Num_Best пар подстановок (Г1,Г2), соот ветствующих лучшим наборам, отобранным на шаге 11. 16: Перейти к шагу 2. Выход: Подстановка F G S(V8), отличающаяся от исходной только значениями подстановок Гг1, Г2, такая, что (3) £f - 40 (Nf - 108),

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