Введение 2
1 Постановка задачи 3
2 Границы максимальной нелинейности булевой (n. т)-функции 6
2.1 Ограничения сверху 6
2.2 Ограничения снизу 8
2.3 Таблица ограничений на максимальную нелинейность N(n.m) 9
3 Описания используемых алгоритмов поиска 10
3.1 Алгоритм имитации отжига 10
3.1.1 Алгоритм имитации отжига для задачи без ограничений 11
3.1.2 Алгоритм имитации отжига для сбалансированной задачи 11
3.1.3 Модификации 12
3.2 Алгоритм восхождения на вершину 12
3.2.1 Алгоритм восхождения на вершину для задачи без ограничений 12
3.2.2 Алгоритм восхождения на вершину для сбалансированной задачи 13
3.3 Генетический алгоритм 13
3.3.1 Генетический алгоритм для задачи без ограничений 13
3.3.2 Генетический алгоритм для сбалансированной задачи 14
3.3.3 Модификации 15
3.4 Общая модификация для всех алгоритмов 15
4 Результаты работы алгоритмов 15
4.1 Результат работы алгоритмов для задачи без ограничений 17
4.2 Результат работы алгоритмов для сбалансированной задачи 21
Заключение 25
Список литературы 28
Векторные булевы функции являются одним из ключевых компонент в криптосистемах. Для того чтобы обеспечить устойчивость против криптографических атак, векторная булева функция должна обладать определенными свойствами. Из набора требуемых свойств нас будут интересовать высокая нелинейность и сбалансированность. Данные свойства мы будем требовать от функций как в отдельности, так и совместно.
В данной работе мы опишем и оценим работу нескольких эвристических методов поиска хороших векторных булевых функций: генетический алгоритм, алгоритм имитации отжига, алгоритм восхождения на вершину. Большинство этих методов уже применялось для поиска функций с высокой нелинейностью и сбалансированностью, однако, насколько нам известно, никто не проводил сравнительные анализ их работы.
Кроме того, найдем верхние и нижние границы максимальной нелинейности булевых функций, чтобы оценивать работу алгоритмов не только относительно друг друга, но и относительно максимально возможного значения нелинейности.
Поставим следующие цели и задачи:
1. Построить и уточнить границы максимальной нелинейности;
2. Найти векторные булевы функции с нелинейностью, приближающейся к границам максимальной нелинейности;
3. Найти сбалансированные векторные булевы функции с нелинейностью, приближающейся к границам максимальной нелинейности;
4. Запрограммировать и сопоставить методы, способствующие достижению этой цели.
К задачам поиска векторных булевых функций с высокой нелинейностью и поиска сбалансированных векторных булевых функций с высокой нелинейностью были применены эвристические алгоритмы — алгоритм имитации отжига, алгоритм восхождения на вершину, генетический алгоритм и их комбинации. Все алгоритмы были запрограммированы на языке Java. Кроме того, к данным задачам был применен встроенный генетический алгоритм Matlab.
Ко всем алгоритмам был предложен и протестирован набор модификаций, после чего было принято решение о применении или неприменении каждой каждой модификации.
Чтобы оценить работу запрограммированных алгоритмов относительно максимально возможного значения нелинейности, были изучены теоретические границы максимальной нелинейности.
С помощью исследуемых алгоритмов для случаев n = 5, m = 6 и n = 8, m = 9 удалось уточнить теоретические границы максимальной нелинейности снизу.
По работе алгоритмов для обеих задач максимизации нелинейности векторной булевой функции, с учетом требования сбалансированности и без, была собрана статистика для различных n и m. По ней можно сделать вывод, что лучшей статистикой по найденным функциям обладают комбинированные методы поиска, комбинации генетического алгоритма с восхождением на вершину и имитации отжига с восхождением на вершину. Однако, как стоило ожидать, комбинации алгоритмов имеют наибольшее время работы.
Также выделим алгоритм восхождения на вершину, который для задачи без учета сбалансированности имеет лучшую статистику по функциям среди некомбинированных алгоритмов. Для задачи с учетом сбалансированности восхождение на вершину всегда работает в несколько раз быстрее других алгоритмов и часто ищет функции не хуже, чем комбинированные методы поиска.
