Линейный криптоанализ
Год издания: 2026
Автор: Бейн Тим, Рэймен Винсент
Переводчик: Слинкин А. А.
Издательство: ДМК Пресс
ISBN: 978-5-93700-474-1
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Количество страниц: 182
Описание: Данное руководство посвящено анализу безопасности (криптоанализу) фундаментальных блоков, на которых основаны криптографические приложения. Линейный криптоанализ рассматривается с математической точки зрения и сопровождается обзором наиболее влиятельных публикаций. Главы дополнены большим количеством примеров и упражнений, опирающихся на теорию и практику.
Предварительные знания теории криптографии не требуются. Издание будет полезно как начинающим читателям, изучающим криптографию, так и опытным экспертам, применяющим ее на практике.
Примеры страниц (скриншоты)
Оглавление
Предисловие от издательства........................................................................... 9
Предисловие................................................................................................... 10
Глава 1. Введение........................................................................................... 13
1.1. Криптографические примитивы................................................................. 13
1.1.1. Анализ................................................................................................. 13
1.1.2. Проектирование.................................................................................... 14
1.2. Линейные аппроксимации......................................................................... 15
1.2.1. Смещение............................................................................................. 16
1.2.2. Таблицы линейной аппроксимации......................................................... 17
1.3. Линейные следы и лемма о набегании знаков............................................ 19
1.4. Восстановление ключа............................................................................. 21
1.4.1. Алгоритм Мацуи 1................................................................................. 21
1.4.2. Алгоритм Мацуи 2................................................................................. 23
1.5. Оставшиеся проблемы................................................................................. 24
1.6. Историческая справка.................................................................................. 24
1.7. Литература..................................................................................................... 25
1.8. Упражнения................................................................................................... 25
Глава 2. Корреляционные матрицы.................................................................... 27
2.1. Корреляция случайной величины на 𝔽2........................................................27
2.2. Корреляция между булевыми функциями..................................................... 28
2.3. Корреляционные матрицы.......................................................................... 29
2.4. Корреляционные матрицы структурных функций.......................................... 31
2.5. Линейные следы........................................................................................... 33
2.6. Историческая справка.................................................................................. 35
2.7. Литература.................................................................................................... 36
2.8. Упражнения................................................................................................... 37
Глава 3. Оптимизация линейных следов............................................................... 42
3.1. Метод ветвей и границ................................................................................. 42
3.1.1. Поиск в глубину..................................................................................... 42
3.1.2. Метод Мацуи.......................................................................................... 43
3.2. Смешанно-целочисленное линейное программирование........................... 46
3.2.1. Пример: шифр типа Rijndael................................................................ 46
3.2.2. Построение модели............................................................................... 48
3.2.3. Решение модели.................................................................................... 50
3.3. Выполнимость и выполнимость в теориях................................................ 50
3.3.1. Пример: шифр add-rotate-xor............................................................... 51
3.3.2. Построение модели..............................................................................52
3.3.3. Решение модели...................................................................................53
3.4. Историческая справка................................................................................54
3.5. Литература...................................................................................................54
3.6. Упражнения.................................................................................................54
Глава 4. Статистика линейного криптоанализа ..................................................58
4.1. Статистический вывод...............................................................................58
4.1.1. Статистические оценки.......................................................................58
4.1.2. Проверка гипотез.................................................................................59
4.2. Восстановление ключа с помощью проверки статистических гипотез.........62
4.2.1. Известная корреляция.........................................................................62
4.2.2. Неизвестная корреляция.....................................................................64
4.3. Стратегии выборки.....................................................................................66
4.4. Восстановление ключа с использованием ранжирования ключей...................67
4.5. Историческая справка................................................................................68
4.6. Литература...................................................................................................68
4.7. Упражнения.................................................................................................68
Глава 5. Методы восстановления ключа.........................................................69
5.1. Восстановление ключа по алгоритму 2.....................................................69
5.2. Подход Мацуи..............................................................................................70
5.2.1. Однонаправленный случай.................................................................70
5.2.2. Двунаправленный случай....................................................................72
5.3. Метод быстрого преобразования Фурье...................................................73
5.3.1. Циркулянтная структура.....................................................................73
5.3.2. Умножение на циркулянтные матрицы.............................................74
5.4. Историческая справка................................................................................76
5.5. Литература...................................................................................................76
5.6. Упражнения.................................................................................................77
Глава 6. Множественный линейный криптоанализ........................................78
6.1. Множественный линейный криптоанализ...............................................78
6.1.1. Множественные линейные аппроксимации......................................78
6.1.2. Различители.........................................................................................81
6.2. Многомерный линейный криптоанализ...................................................84
6.2.1. Многомерные линейные аппроксимации.........................................84
6.2.2. Различители.........................................................................................86
6.2.3. Атаки с выбранным открытым текстом.............................................87
6.3. Заключительные замечания......................................................................88
6.3.1. Восстановление ключа.........................................................................88
6.3.2. Нахождение подходящих линейных аппроксимаций.......................89
6.4. Историческая справка................................................................................89
6.5. Литература...................................................................................................89
6.6. Упражнения.................................................................................................90
Глава 7. Оптимальная проверка статистических гипотез.......................................94
7.1. Вероятностные меры..................................................................................94
7.2. Простые гипотезы.......................................................................................95
7.2.1. Теория Неймана–Пирсона...................................................................96
7.2.2. Два многомерных нормальных распределения.................................97
7.2.3. Два распределения почти равны.........................................................98
7.3. Составные гипотезы..................................................................................101
7.3.1. Коэффициенты Байеса.......................................................................102
7.3.2. Гипотеза рандомизации с правильным ключом.............................102
7.3.3. Гипотеза рандомизации с неправильным ключом.........................104
7.4. Оптимальное восстановление ключа......................................................106
7.5. Историческая справка...............................................................................107
7.6. Литература.................................................................................................107
7.7. Упражнения................................................................................................107
Глава 8. Аппроксимации с нулевой корреляцией..................................................109
8.1. Идея............................................................................................................109
8.2. Нахождение аппроксимаций с нулевой корреляцией...........................110
8.3. Использование аппроксимаций с нулевой корреляцией......................112
8.3.1. Одна аппроксимация.........................................................................113
8.3.2. Несколько аппроксимаций................................................................115
8.4. Статистический подход............................................................................116
8.5. Историческая справка..............................................................................117
8.6. Литература.................................................................................................117
8.7. Упражнения...............................................................................................118
Глава 9. Различные обобщения.........................................................................121
9.1. Точные свойства........................................................................................121
9.1.1. Атаки с насыщением..........................................................................121
9.1.2. Инвариантные подпространства......................................................123
9.1.3. Нелинейные инварианты..................................................................125
9.2. Приближенные свойства..........................................................................127
9.2.1. Статистическое насыщение..............................................................127
9.2.2. Нелинейные аппроксимации............................................................128
9.2.3. Каркас проецирования......................................................................128
9.3. Историческая справка..............................................................................129
9.4. Литература.................................................................................................129
9.5. Упражнения...............................................................................................130
Глава 10. Функции на абелевых группах.......................................................132
10.1. Линейная алгебра над полем ℂ............................................................132
10.1.1. Нормированные векторные пространства и двойственные им..............133
10.1.2. Пространства со скалярным произведением......................................135
10.1.3. Сингулярное разложение................................................................137
10.1.4. Тензорные произведения векторных пространств..............................137
10.2. Анализ Фурье на конечных абелевых группах......................................138
10.2.1. Характеры группы............................................................................139
10.2.2. Преобразование Фурье....................................................................141
10.2.3. Двойственность Понтрягина...........................................................143
10.3. Историческая справка............................................................................144
10.4. Литература...............................................................................................144
10.5. Упражнения.............................................................................................145
Глава 11. Геометрический подход..............................................................148
11.1. Геометрический взгляд...........................................................................148
11.1.1. Криптоаналитические свойства.....................................................148
11.1.2. Распространение..............................................................................149
11.1.3. Геометрия.........................................................................................151
11.2. Линейный криптоанализ........................................................................152
11.2.1. Корреляционные матрицы..............................................................152
11.2.2. Множественный линейный криптоанализ.........................................154
11.3. Точное распространение........................................................................155
11.3.1. Прямое распространение................................................................155
11.3.2. Обратное распространение.............................................................155
11.3.3. Нулевая корреляция.........................................................................156
11.3.4. Инварианты......................................................................................156
11.4. Приближенное распространение...........................................................157
11.4.1. Отображения аппроксимации.............................................................157
11.4.2. Геометрия.........................................................................................158
11.4.3. Принцип доминирующих следов.........................................................159
11.5. Историческая справка............................................................................160
11.6. Литература...............................................................................................160
11.7. Упражнения.............................................................................................160
Приложение A. Нормальное распределение........................................................164
Приложение B. Краткий справочник по статистике..............................................167
Приложение C. Список блочных шифров.............................................................169
Литература.......................................................................................................170
Предметный указатель.......................................................................................174
