S-blocks with maximum component algebraic immunity on a small number of variables.pdf S-блоки играют решающую роль в обеспечении стойкости блочных шифров к различным типам атак. Основная причина этого в том, что в классических и современных блочных шифрах нелинейный слой представлен именно данными блоками. S-блок является отображением множества двоичных векторов длины n в множество двоичных векторов длины m. В 2003 г. в [1] был представлен новый вид криптоанализа - алгебраический, основанный на понижении степени системы уравнений, описывающей шифр. Для противостояния такому роду атак необходимо, чтобы S-блок имел максимально возможное значение компонентной алгебраической иммунности. Будем рассматривать S-блоки определённого вида, а именно Fn(x) = (f (x), f (n(x)), ... , f (nn~ 3(x))), где Fn : F? F?; f - булева функция от n переменных; n - циклический сдвиг влево на один. Эта конструкция предложена А. Удовенко в решении олимпиадной задачи на NSUCRYPTO-2016 [2]. Он показал, что при таком построении векторной функции можно получить функцию с максимальной алгебраической иммунностью от 3, 4, . . . , 10 переменных. В настоящее время остаётся открытым вопрос о существовании векторной булевой функции с максимальной компонентной иммунностью \\п/2~\\ от произвольного числа переменных п. Алгебраической иммунностью AI(f) булевой функции f называется минимальное число d, такое, что существует булева функция g степени d, не тождественно равная нулю, для которой выполняется равенство fg = 0 или (f ф 1)g = 0 [3]. Известно, что для произвольной булевой функции f от n переменных выполнено AI(f) С \\n/2~\\. Компонентной алгебраической иммунностью AIcomp(F ) векторной булевой функции F называется минимальная алгебраическая иммунность её компонентных функций, т. е. функций fb(x) = (b, F(x)), где b G Fn, b = 0 и (a,b) = a1b1 ф ... ф anbn - скалярное произведение векторов по модулю 2. В данной работе для построения S-блока с максимальной компонентной алгебраической иммунностью реализован метод нахождения линейного подпространства размерности n в множестве, содержащем векторы значений нулевой функции и всех булевых функций от n переменных с максимальной алгебраической иммунностью |”n/2"|. В первую очередь путём полного перебора формируется множество булевых функций с максимальной алгебраической иммунностью. К этому множеству добавляется нулевой вектор. Далее из этого множества выбирается функция и на её основе строятся оставшиеся n - 1 функций (применением перестановки п к аргументам); все такие функции также лежат в этом множестве. Затем проверяется, порождают ли все n функций линейное подпространство размерности n. Если да, то данное подпространство позволяет построить S-блок с максимальной компонентной иммунностью, выбрав в качестве координатных функций S-блока базис подпространства. Для однозначности пусть функция строится в виде Fn(x) = (f (x), f (n(x)),... , f (nn-1(x))). Для n = 3 путём полного перебора получено, что существует 56 булевых функций с максимальной алгебраической иммунностью 2. Из них на основе 12 функций (им отвечают четыре подпространства) можно построить векторную булеву функцию с максимальным значением иммунности. Все эти функции можно представить в виде АНФ общего вида. Утверждение 1. Булевы функции f от трёх переменных с максимальной алгебраической иммунностью 2, такие, что векторные функции вида Fn(x) = (f (x), f (n(x)), f (n2(x))), где п - циклический сдвиг, также имеют максимальную компонентную алгебраическую иммунность 2, можно описать следующей конструкцией: f(x1, x2, x3) = xi + xj + xixk + a, где {i, j, k} = {1, 2, 3}, a G F2. Для n = 4 путём полного перебора получено, что существует 54 952 булевых функций с максимальной алгебраической иммунностью 2. При рассмотрении всевозможных перестановок п (а не только циклического сдвига влево, как это происходило ранее) оказалось, что только при шести перестановках существуют векторные булевы функции, которые сохраняют максимальную иммунность. Эти перестановки можно представить в векторном виде: (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 3, 1, 2) или циклическом (1234), (1243), (1342), (1324), (1432), (1423). Для каждой перестановки существует 6144 булевых функций (или 1536 линейных подпространств), построенные на основе которых векторные булевы функции также имеют максимально возможную компонентную алгебраическую иммунность. Утверждение 2. Пусть f - булева функция от n переменных с максимальной алгебраической иммунностью |"n/2"|. Если векторная булева функция Fn (x) = = (f (x), f (n(x)),... , f (nn-1 (x))) имеет максимальную компонентную алгебраическую иммунность, то п является полноцикловой перестановкой. Для n = 5 путём полного перебора получено, что всего существует 197 765 122 булевых функций с максимальной алгебраической иммунностью 3. Существует как минимум четыре булевых функции (им отвечает одно подпространство), на основе которых строится векторная булева функция с максимальным значением иммунности. С учётом экспериментальных результатов сформулированы следующие гипотезы: Гипотеза 1. Для любого n 2 в множестве, состоящем из булевых функций от n переменных с максимальной алгебраической иммунностью и нулевой функции, существует линейное подпространство размерности n. Данная гипотеза доказана для n = 2, 3, 4, 5, 6, 8, 10 благодаря собственным результатам и результатам А. Удовенко. Для n = 7, 9 пока не найдено таких подпространств. Гипотеза 2. Пусть f - булева функция от n переменных с максимальной алгебраической иммунностью |"n/2"|. Тогда в её АНФ присутствует по меньшей мере по одному моному каждой степени i, где i = 1,2,..., |”n/2"|. Данная гипотеза проверена для n = 2, 3, 4, 5, 6, 8, 10 благодаря собственным результатам и результатам А. Удовенко. Таким образом, возможно построение S-блока от малого числа переменных, который устойчив к алгебраическим атакам. В дальнейшем планируется анализ булевых и векторных булевых функций от большего числа переменных.

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