Application of heuristic methods to search for boolean functions with good cryptographic characteristics.pdf Успех криптоанализа в основном зависит от нахождения уязвимостей в математических свойствах булевых функций, являющихся компонентами шифра. Для противостояния разным видам криптоанализа существуют различные математические требования к функциям. Функции, которые удовлетворяют этим требованиям, называются криптографическими. Для повышения стойкости необходимо искать и применять в шифрах булевы функции с оптимальными криптографическими свойствами. Для ослабления статистической зависимости между входом и выходом функции по умолчанию предполагается, что функция обладает сбалансированностью, т. е. принимает значения 0 и 1 одинаково часто. Работа является продолжением исследования, начальные результаты которого представлены в [1]. Рассматриваются булевы функции от n переменных с такими криптографическими характеристиками: сбалансированность, нелинейность и алгебраическая иммунность. Известны теоретические оценки максимума этих характеристик: для нелинейности - Nf С 2n-1 - 2n/2-1, для алгебраической иммунности - AI(f) С \\n/2~\\. Цель данной работы - построение сбалансированных булевых функций с хорошими криптографическими характеристиками, а также построение на их основе векторных булевых функций с компонентной алгебраической иммунностью и нелинейностью. Функция вида F : Fn Fm называется векторной булевой функцией. Векторную булеву функцию можно представить в виде F = (f 1(x) . ..fm(x)), где f j (x), j = 1,..., m, - координатные (булевы) функции от n переменных. Компонентной функцией называется любая ненулевая линейная комбинация координатных функций, т. е. булева функция vF = v1f1 ф ... ф vmfm, где v = (v1... vm) G G Fm \\ 0m и 0m - нулевой вектор длины m. Нелинейностью Nf и компонентной алгебраической иммунностью AIcomp ( F ) векторной булевой функции F : Fn Fm называются минимальная нелинейность и алгебраическая иммунность её компонентных функций соответственно: NF = mmin NvF, AIcomp(F) = mmin AI(vF). veFm\\om v eFm\\om Можно выделить три способа нахождения таких функций: полный перебор, алгебраическое конструирование и эвристики. Для булевой функции f : Fn F2 длина вектора значений - 2n. При росте числа переменных количество булевых функций растёт дважды экспоненциально, что делает невозможным полный перебор. Алгебраическое построение заведомо сужает множество решений и повышает вероятность успеха криптоанализа из-за предсказуемости построения. Перспективным является подход, использующий эвристические методы, в основе которых лежит итерационный перебор с параметрами для достижения желаемого результата. Для поиска криптографических булевых функций и построения на их основе векторных булевых функций предложен гибридный алгоритм на основе генетического алгоритма и поиска восхождением к вершине (алгоритм Hill Climbing) и проведены вычислительные эксперименты, показывающие его эффективность. Генетический алгоритм (ГА) - это эвристический подход к комбинаторной оптимизации в сложном пространстве пригодности. Идея, лежащая в основе генетического алгоритма, состоит в том, чтобы начать с набора потенциальных решений (генофонда или родительского множества) и каким-то образом объединить их пары (схема размножения) для получения новых решений (дочерних). Схемы размножения могут включать родительский отбор и мутацию полученного в результате ребенка. Новый набор выбирается из числа родителей и детей (отбор) на основе функции пригодности, и процесс повторяется до тех пор, пока не будет найдено оптимальное решение или не будет достигнуто максимальное число итераций. В работе особями являются векторы значений булевых функций от n переменных, начальная популяция - случайное множество сбалансированных особей. Поиск восхождением к вершине (Hill Climbing)-эвристический алгоритм, который начинает с произвольного решения, а затем итерационно пытается найти лучшее решение путём пошагового изменения одного из его элементов. На вход поступает вектор значений булевой функции. Алгоритм итеративно пытается его улучшить, изменяя одну из координат. Более подробное описание алгоритма и теоретическое обоснование его эффективности представлено в [2]. В работе поиск восхождением к вершине применяется после оператора мутации потомков на каждой итерации ГА для поддержания нелинейности. Рассмотрим два варианта реализации оператора скрещивания. Первый - однородное скрещивание. На вход поступают булевы функции f и g от n переменных, заданные векторами значений (f0, f1, . . . , f2n-1 ) и (g0, g1, . . . , g2n-1) соответственно. На выходе булева функция h от n переменных, вектор значений (h0, h1, . . . , h2n-1 ) которой определяется следующим образом: если fi = gi, то hi = fi; если fi = gi , то hi принимается равным значению fi или gi с одинаковой вероятностью, где i = 0, 1, . . . , 2n-1 . Второй вариант предложен в [3], он похож на предыдущий, но, в отличие от первого, позволяет поддерживать сбалансированность потомков. Введём некоторые ограничения на скрещивание. Расстоянием Хэмминга (dist(f, g)) между булевыми функциями f и g от n переменных называется число координат, в которых различаются их векторы значений. Если dist(f , g) > 2n-1, то вместо вектора значений функции g рассматривается вектор, полученный инверсией всех битов вектора значений функции g . Рассмотрено применение двух видов мутации. Первый - к двум различным случайным битам входного вектора значений применялась инверсия. Второй предложен в [4]. Выбираются две случайные позиции в векторе значений. Значение из большей позиции переставляется в меньшую и происходит сдвиг битов вправо. Для генетического алгоритма с целевой функцией cost = AI(f ) проведён сравнительный анализ эффективности различных вариантов операций скрещивания и мутации. Полученные результаты приведены в табл. 1, где n - число переменных; P - размер популяции; T - число итераций. Т а б л и ц а 1 Результаты применения ГА c различными операторами n P T max, min, среднее значение AI(f ) в исходной популяции max, min, среднее значение AI(f ) после применения ГА Количество функций с max AI(f ) Количество функций с max AI(f ) с новыми операторами 6 10 20 (3, 1, 1,9) (3, 3, 3) 659 682 7 10 20 (4, 2, 2,8) (4, 4, 4) 14 34 8 10 20 (4, 1, 2,7) (4, 4, 4) 671 831 Как видно из табл. 1, все потомки имеют ненулевую алгебраическую иммунность вне зависимости от вариации операторов, но неклассические мутации находят большее число функций с максимальной алгебраической иммунностью. Для оценки эффективности гибридного подхода, основанного на сочетании генетического алгоритма с новыми операторами и поиска восхождением к вершине проведён сравнительный анализ по времени и количеству найденных функций со случайным перебором из одного миллиона случайно сгенерированных сбалансированных функций. Результаты представлены в табл. 2. Та б л и ц а 2 Сравнение гибридного подхода со случайным поиском n P T Найдено функций ГА+HC Время, с Случайный поиск из 1000000 функций Время, c 4 20 5000 314222 432 91002 972 6 20 5000 564111 765 123611 1187 7 20 5000 457211 1056 198715 1623 8 20 5000 732888 1434 261238 2111 Как видно из табл. 2, гибридный подход показывает высокую эффективность в задаче поиска булевых функций с алгебраической иммунностью (cost = AI(f )). Полученные булевы функции используются для построения векторных булевых функций. Изменим целевую функцию на сочетание криптографических характеристик и применим гибридный подход для поиска булевых функций и на основе получившихся построим векторные булевы функции для m = 4 и n = 4, 5, 6, 8. Целевая Nf AI(f ) функция - нелинейность и алгебраическая иммунность: cost =--+-----, max Ng max AI(g ) где g пробегает множество особей популяции. Результаты представлениы в табл. 3 Та б л и ц а 3 Результаты для векторных булевых функций n P T Найдено булевых функций Найдено векторных булевых функций Значение NF и AIcomp(F ) Теор. оценка NF Теор. оценка AIcomp(F ) Время, с 4 20 10 1245 415661 6; 2 < 6 < 2 162,202 5 20 10 76 1797608 12; 3 < 13 < 3 5323,85 6 20 10 1346 310295 24; 3 < 28 < 3 363,098 8 20 10 1426 321203 108; 4 < 120 < 4 3061,11 Таким образом, в работе приведены результаты сравнительного анализа гибридного подхода и случайного перебора. Найденные булевы функции использованы для поиска векторных булевых функций. Представлены результаты поиска векторных булевых функций с нелинейностью и компонентной алгебраической иммунностью для m = 4 и n 8. Полученные векторные булевы функции могут быть использованы для построения S-блоков. Наличие компонентной алгебраической иммунности и нелинейности S-блоков способствует противостоянию алгебраическому и линейному криптоанализу шифров соответственно.

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