Введение
Глава 1. Алгоритмические вопросы поиска аннигиляторов булевых функций 21
1.1 Поиск аннигиляторов для различных способов представления булевой функции 21
1.1.1 Для представления функции в виде многочлена Жегалкина 21
1.1.1.1 Алгоритм AM 1 поиска базиса пространства аннигиляторов 22
1.1.1.2 Явный вид системы уравнений, задающей аннигиляторы 25
1.1.1.3 Алгоритм AM 1Б поиска статических соотношений для быстрых алгебраических атак
1.1.1.4 Один способ улучшения алгоритма AM 1 — алгоритм АМ12 30
1.1.2 Для представления функции в виде ДНФ 3 5
1.1.3 Для представления функции в виде формулы или схемы из функциональных элементов
1.1.3.1 Алгоритмы АФ1 и АС 1 поиска аннигиляторов 3 7
1.1.3.2 Дополнение: О линейных аннигиляторах произведения булевых функций 40
1.1.3.3 Дополнение: Структура пространства аннигиляторов для булевых функций с фиктивными переменными 42
1.1.4 Для представления функции в виде трэйс представления 44
1.1.4.1 Алгоритм ATI поиска базиса пространства аннигиляторов 47
1.1.4.2 Алгоритм АТ1Б поиска статических соотношений для быстрых алгебраических атак 50
1.1.4.3 Модификация алгоритма АТ1Б, ориентированная на короткое трэйс представление входной функции 51
1.1.4.4 Алгебраическая иммунность фильтрующей функции генератора WG 53
1.1.5 О поиске аннигиляторов для частично определённых функций 55
1.2 Алгоритмы проверки отсутствия ненулевых аннигиляторов 58
1.2.1 Проверка отсутствия ненулевых аннигиляторов низкой степени у многочлена Жегалкина 59
1.2.1.1 Основной вариант алгоритма АМ2 59
1.2.1.2 Возможные пути модификации алгоритма АМ2 62
1.2.2 Проверка отсутствия ненулевых аннигиляторов низкой степени у ДНФ 63
Глава 2. Нижние и верхние оценки алгебраической иммунности булевых функций, заданных трэйс представлением 65
2.1 Алгебраическая иммунность линейных функций от инверсии 65
2.2 Нижние оценки алгебраической иммунности более широких классов функций 72
2.3 Верхние оценки алгебраической иммунности более широких классов функций 85
Глава 3. Исследование метода быстрых алгебраических атак (БАА) 88
3.1 Предварительные сведения 8 8
3.2 Полиномиальный алгоритм получения тождеств для метода БАА по трэйс представлению функции 90
3.3 Полиномиальный алгоритм получения нелинейных рекуррентных соотношений для фильтрующего генератора по трэйс представлению фильтрующей функции 93
3.4 Явное выражение для минимальной линейной комбинации предварительного шага метода БАА 95
Список литературы 97
