Аппроксимация дискретных функций алгебраически вырожденными функциями в анализе систем защиты информации

• Автор: Алексеев, Евгений Константинович
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 106 с. : ил.

Содержание
Введение

Глава 1. Основные определения, понятия и обозначения.

1.1. Основные параметры булевых функций.

1.2. Криптографические параметры булевых функций

Глава 2. Алгебраические и комбинаторные свойства корреляционноиммунных булевых функций.

2.1. Некоторые свойства множества четных функций

2.2. Строение множества С1п.

2.3. Нижняя оценка для мощности множества С1п.

2.4. Некоторые критерии корреляционной иммунности

2.5. Минимальность корреляциоииоиммунных функций .

2.6. Минимальные корреляционноиммунные булевы функции
и линейные коды
2.7. Корреляционноиммунные булевы функции веса 4 и 2м 4
2.8. Пространства корреляционноиммунных функций
Глава 3. Аппроксимация булевых функций с помощью алгебраически вырожденных функций.
3.1. Невырожденность булевых функций .
3.2. Порядок алгебраической вырожденности наилучших аппроксимаций .
3.3. Связь с другими криптографическими параметрами .
3.4. Свойства яуфункций и вычисление параметра 7тр
3.5. Случай бентфункций . .
Глава 4. Алгоритмы восстановления ключа фильтрующего генератора, использующие аппроксимацию алгебраически вырожденными функциями.
4.1. Постановка задачи.
4.2. Предварительные рассуждения
4.3. Алгоритм К определения ключа
4.4. Оценка трудоемкости алгоритма С
4.5. Вероятностный алгоритм Срг определения ключа.
4.6. Об одном классе аппроксимирующих функций
4.7. Примеры.
Заключение
Литература


Примерами таких свойств являются: максимально возможная удаленность от множества аффинных функций ([]); отсутствие корреляционных связей между значением функции и набором ее переменных фиксированной мощности ([]); отсутствие у булевой функции низкос-тепенных аннигиляторов ([]); отсутствие у булевой функции (отображения) линейных структур ([]). Множества булевых функций, обладающих данными свойствами, выделяются в отдельные классы. К их числу относятся бент-функции, корреляционно-иммунные функции, алгебраически иммунные функции и алгебраически невырожденные функции. Примерами результатов исследований в этой области могут служить работы [9],[] и [] для корреляционно-иммунных функций, оценки для числа бсит-функций - [],[], асимптотические оценки числа алгебраически вырожденных функций - []. Подобные функции, имеющие нетривиальные линейные структуры, не обладают необходимыми криптографическими свойствами. Вместе с тем, они играют определяющую роль в криптоанализе. Исторически первыми для аппроксимации были использованы аффинные функции ([]), входящие в класс функций, обладающих нетривиальными линейными структурами. Например, некоторые разновидности корреляционного метода криптоанализа используют для аппроксимации аффинные функции ([],[]). При его использовании осуществляется переход от исходной криптографической задачи определения ключа (в широком смысле) к задачам математической статистики или теории кодирования. По этой причине, в частности, расстояние до функций, обладающих нетривиальными линейными структурами, рассматривается как одна из криптографических характеристик булевых функций ([]), обобщающих понятие нелинейности булевой функции. Класс функций, обладающих нетривиальными линейными структурами, включает в себя такой интересный с точки зрения приложений класс функций, как алгебраически вырожденные функции ([]). В данной работе исследуются алгебраические, комбинаторные и криптографические свойства аппроксимаций криптографических функций алгебраически вырожденными булевыми функциями. В первой главе диссертации приводятся основные понятия и ранее известные результаты, которые используются далее в работе или представляются важными для понимания следующих глав. Во второй главе исследуются комбинаторные и алгебраические свойства множества корреляционно-иммунных булевых функций «в целом». Булева функция называется корреляционно-иммунной порядка к, если ее выход статистически не зависит в естественной теоретико-вероятностной модели от любой линейной комбинации к и менее входов. С1(п) — множество всех корреляционно-иммунных булевых функций как минимум первого порядка от п переменных. Необходимо отметить некоторые работы, посвященные исследованию множества корреляционно-иммунных функций. В работе [] была предпринята попытка рассмотреть свойства множества корреляционно-иммунных булевых функций с использованием аппарата алгебраически вырожденных функций. Фактически, в дайной работе рассматриваются свойства алгебраически вырожденных корреляционно-иммунных булевых функций. В работе [] корреляционно-иммунные булевы функции рассматриваются сточки зрения групповой алгебры1ВУУп. Книга [] посвящена исследованию такого математического объекта, как ортогональные массивы. Многие результаты из книги [] (например, неравенство Рао) могут быть переформулированы в терминах корреляционно-иммунных булевых функций. В разделе 2. В разделе 2. CI(п), как объединения смежных классов по подпространствам пространства четных функций специального вида (Теорема 2. Следствием этого описания является доказанная в разделе 2. С1(п) (Теорема 2. В разделе 2. СЦп). Один из этих критериев (Теорема 2. ЭВМ. Критерий, доказанный в теореме 2. В разделе 2. Функция / G С1(п) называется минимальной, если не существует такой булевой функции g от п переменных, что f'g = g и g G С1{п). Введение этого определения продиктовано следующим свойством корреляционно-иммунных булевых функций: если / € С1(п) и g такова, что / • g = g и g G С1(п), то / © g G CI(n). Это означает, что корреляционно-иммунные функции, которые не являются минимальными, «раскладываются» на сумму ортогональных (таких g и h, что g • h = 0) корреляционно-иммунных функций.