Hybrid approach to the search for boolean functions with high algebraic immunity based on heuristics.pdf Развивающийся интерес к криптоанализу повышает потребность в улучшении стойкости шифров. Для защиты от статистических и аналитических методов криптоанализа для построения компонент шифра необходимо использовать булевы функции, обладающие хорошими криптографическими характеристиками. В 2003 г. N. Courtois и W. Meier в [1] предложили новый метод криптоанализа шифров, названный алгебраическим криптоанализом. Высокая алгебраическая иммунность помогает противостоять такому криптоанализу. Целью работы является построение булевых функций с максимальной алгебраической иммунностью - характеристикой, повышающей стойкость шифра к алгебраическим атакам. Алгебраическая иммунность булевой функции f (AI(f))-минимальное число d, такое, что существует булева функция g степени d, не тождественно равная нулю, для которой выполняется равенство fg = 0 или (f ф 1)g = 0, где f и g - функции от равного числа переменных. Известно, что для любой функции f от n переменных справедливо AI(f) < \\n/2\\. Задача полного описания класса булевых функций, обладающих максимальной алгебраической иммунностью, а также получения новых конструкций таких функций является открытой проблемой. Существует три способа нахождения функций с высокой алгебраической иммунностью: полный перебор, алгебраическое конструирование и эвристики. При росте числа переменных множество булевых функций растёт дважды экспоненциально, что ухудшает эффективность полного перебора. Алгебраическое построение заведомо сужает множество решений. Перспективным является подход, использующий эвристические методы, в основе которых лежит структурированный перебор с параметрами для достижения желаемого результата. Предлагается рассмотреть применение эвристических методов, в частности генетического алгоритма и алгоритма Hill Climbing. Специфика применения данных алгоритмов для поиска булевых функций с высокими значениями нелинейности впервые описана в [2]. Получены также теоретические результаты применения этих алгоритмов для функций от 16 переменных. Эффективность эвристических методов продемонстрирована в ряде работ: в [3] исследована возможность применения алгоритма имитации отжига для поиска функций с высокой нелинейностью и низкой автокорреляцией; в [4] реализован генетический алгоритм для поиска бент-функций и сбалансированных функций; в [5] приведены результаты применения гибридного генетического алгоритма для построения сбалансированной булевой функции с оптимальными криптографическими характеристиками. Для достижения максимального значения алгебраической иммунности реализованы два алгоритма. Генетический алгоритм (ГА) - это метод поиска, аналогичный естественному отбору в природе. Для получения более жизнеспособных потомков к особям из начальной популяции итерационно применяются скрещивание и мутация. Последовательно происходит полное обновление популяции потомками, обладающими наибольшими значениями целевой функцией. В терминах нашей задачи: - особь - вектор значений булевой функции; - начальная популяция - случайное множество особей, без ограничений; - мутация - перестановка двух случайных различных битов вектора значений входной функции; - целевая функция - алгебраическая иммунность; - скрещивание - однородный кроссинговер. На вход поступают булевы функции f и g, представленные векторами значений (f0, f1, ..., f2n-1) и (g0, g1, . .., g2n-1). На выходе - булева функция h, вектор значений (h0, h1,..., h2«-i) которой определяется следующим образом: если fi = gi, то hi = fi; если fi = gi, то hi принимается равным fi или gi с одинаковой вероятностью, i = 0, 1 , . . . , 2n-1 . Введём некоторые ограничения на скрещивание. Для этого нам потребуется расстояние Хэмминга. Расстоянием Хэмминга dist(f, g) между булевыми функциями f и g называется число координат, в которых различаются их векторы значений. Если dist(f, g) > 2n-1, то вместо вектора значений функции g рассматривается вектор, полученный инверсией всех битов вектора значений функции g. В рамках работы вероятность выполнения операции скрещивания принималась равной 0,8. Далее в таблице представлены экспериментальные результаты применения генетического алгоритма для булевых функций при n = 4, 6, 8. Алгоритм повышает значения алгебраической иммунности до максимальной теоретической оценки для всех особей популяции. Подсчитано количество функций с максимальным значением целевой функции, получаемых на каждой итерации при каждом обновлении популяции. Hill Climbing - итерационный алгоритм, который начинается с произвольного решения задачи, а затем пытается найти лучшее путём пошагового изменения одного из элементов решения. В рамках рассматриваемой задачи используется понятие нелинейности - характеристики, повышающей стойкость к линейному криптоанализу [6]. Преобразованием Уолша - АДамара булевой функции f называется функция Wf : Fn Z, где Wf (y) = E(-1)f (x)®{x,y>, y G Fn, (x,y) = xiyi Ф ... Ф xnyn. x С помощью преобразования Уолша - Адамара можно вычислить нелинейность функции f : N = 2"-1 - axlW/ (y)l. 2 yeFj При чётном числе переменных n максимально возможное значение нелинейности равно 2n-1 - 2n/2-1. В случае нечётного n точное значение максимальной нелинейности неизвестно. Алгоритм для повышения нелинейности описан в [2]. На вход поступает вектор значений булевой функции. Алгоритм итеративно пытается улучшить нелинейность, изменяя одну из координат. На каждой итерации коэффициенты Уолша - Адамара разбиваются на множества и последовательно происходит проверка условий повышения значения целевой функции. В настоящей работе Hill Climbing применяется для поддержания высокой нелинейности после мутации потомков на каждой итерации генетического алгоритма. Известно следующее соотношение, связывающее нелинейность и алгебраическую иммунность булевой функции [7]: AI(f)-2 n- i 1 N > 2 £ i=0 Соотношение определяет верхнюю границу алгебраической иммунности: если нелинейность булевой функции достаточно высока, то эта граница увеличивается. В данной работе при поиске булевых функций с максимальной алгебраической иммунностью на каждой итерации поддерживается высокое значение нелинейности для получаемых потомков с помощью алгоритма Hill Climbing. Проведённые эксперименты показали эффективность такого подхода. Результаты экспериментов для n = 4, 6, - представлены в таблице, где n - число переменных; P - размер популяции; T - число итераций. Результаты применения ГА и Hill Climbing n P T min, среднее, max значения AI(f ) в исходной популяции min, среднее, max значения AI (f ) после применения ГА Количество функций с max AI (f ) при применении ГА Количество функций с max AI(f ) при применении ГА + Hill Climbing 4 10 20 (0; 1,1; 2) (2; 2; 2) 609 715 6 10 20 (0; 1,6; 3) (3; 3; 3) 649 718 8 10 20 (1; 2,5; 4) (4; 4; 4) 683 703 8 20 20 (1; 2,75; 4) (4; 4; 4) 2864 2989 Полученные булевы функции могут быть использованы при поиске векторных булевых функций с высокой компонентной алгебраической иммунностью. Наличие высокой компонентной алгебраической иммунности S-блоков способствует противостоянию алгебраическому криптоанализу поточных и блочных шифров.

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