Аннотация 2
Abstract 3
Введение 6
1 Ограничения наибольшей нелинейности (n,m)-функции алгебры логики .... 7
1.1 Постановка задачи 7
1.2 Верхняя оценка наибольшей нелинейности векторной (n,m)-функции
алгебры логики 12
1.3 Нижние границы наибольшей нелинейности (п^Уфункции алгебры
логики 15
1.4 Таблица границ наибольшей нелинейности векторной (п^^функции
алгебры логики для разных n и m 17
2 Применяемые эвристические методы 20
2.1 Метод Метрополиса 20
2.1.1 Метод Метрополиса для несбалансированной задачи 21
2.1.2 Метод Метрополиса для задачи с учётом ограничения на
сбалансированность 22
2.1.3 Версии метода Метрополиса 22
2.2 Поиск восхождением к вершине 22
2.2.1 Метод поиска путём постепенного восхождения к вершине для задачи
без учёта ограничения на сбалансированность 23
2.2.2 Метод поиска путём постепенного восхождения к вершине для задачи
с учётом ограничения на сбалансированность 24
2.3 Генетический алгоритм 24
2.3.1 Генетический алгоритм для несбалансированной задачи 24
2.3.2 Генетический алгоритм для экстремальной задачи с учётом
ограничения на сбалансированность 26
2.3.3 Вариации генетического алгоритма 27
2.4 Совершенствование используемых эвристических методов 28
3 Результаты работы алгоритмов 29
3.1 Результат работы алгоритмов для несбалансированной задачи 31
3.2 Результат работы алгоритмов для сбалансированной задачи 38
Заключение 44
Список используемой литературы 45
Векторные булевы функции выступают основной составляющей при разработке криптографических систем. Для обеспечения криптостойкости векторная булева функция должна иметь некоторые показатели. Ключевыми показателями криптостойкости являются нелинейность и сбалансированность. Функции должны обладать этими показателями каждая в отдельности и совместно. Целью выпускной квалификационной работы является описание и оценка работы различных эвристических методов нахождения нелинейных и сбалансированных векторных функций алгебры логики. Необходимо рассмотреть нахождение таких функций с помощью алгоритма поиска путём постепенного восхождения на вершину, с помощью алгоритма имитации отжига, с помощью генетического алгоритма. Приведённые методы уже применялись для нахождения векторных булевых функций, но не сравнивались между собой.
Для достижения поставленной цели необходимо выполнить следующие задачи:
- определить границы максимального отклонения векторной булевой функции от аппроксимирующей прямой линии;
- выявить векторные функции алгебры логики, у которых отклонение от аппроксимирующей линии близко к ранее определённым границам максимального отклонения;
- выявить векторные функции алгебры логики, обладающие сбалансированностью, с отклонением от аппроксимирующей прямой линии, приближающимся к определённым ранее границам;
- построить алгоритм и выполнить сравнительный анализ методов, способствующих реализации указанных выше задач.
К задачам поиска векторных булевых функций с высокой нелинейностью и поиска сбалансированных векторных булевых функций с высокой нелинейностью были применены эвристические алгоритмы: метод Метрополиса, метод поиска путём постепенного восхождения к вершине, генетический алгоритм и их комбинации. Эти алгоритмы были написаны на языке Java. Также был применён генетический алгоритм Matlab.
Чтобы оценить работу запрограммированных алгоритмов относительно максимально возможного значения нелинейности, были изучены теоретические границы максимальной нелинейности. С помощью исследуемых алгоритмов для случаев п = 5, т = 6 и п = 8, т = 9 удалось уточнить теоретические границы максимальной нелинейности снизу.
По работе алгоритмов для обеих задач максимизации нелинейности векторной булевой функции, с учётом требования сбалансированности и без, была собрана статистика для различных п и т. По ней можно сделать вывод, что лучшей статистикой по найденным функциям обладают комбинированные методы поиска, комбинации генетического алгоритма с методом поиска путём постепенного восхождения к вершине и метод Метрополиса с методом поиска путём постепенного восхождения к вершине. Однако, как стоило ожидать, комбинации алгоритмов имеют наибольшее время работы.
Метод поиска путём постепенного восхождения к вершине для задачи без учёта сбалансированности имеет лучшую статистику по функциям среди некомбинированных алгоритмов. Для задачи с учётом сбалансированности метод поиска путём постепенного восхождения к вершине работает в несколько раз быстрее других алгоритмов и часто ищет функции не хуже, чем комбинированные методы поиска.
