ОГЛАВЛЕНИЕ
Предисловие . . .3
1. Введение . . .5
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 11
2. Криптосистемы с открытым ключом 12
2.1. Предыстория и основные идеи . . . . . . . . . . . . . . . 12
2.2. Первая система с открытым ключом . . . . . . . . . . . 18
2.3. Элементы теории чисел . . . . . . . . . . . . . . . . . . . 21
2.4. Шифр Шамира . . . . . . . . . . . . . . . . . . . . . . . 28
2.5. Шифр Эль-Гамаля . . . . . . . . . . . . . . . . . . . . . 31
2.6. Одностороння функция с “лазейкой” и шифр RSA . . . 34
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 38
3. Методы взлома шифров 41
3.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . 41
3.2. Метод “Шаг младенца – шаг великана” . . . . . . . . . 43
3.3. Алгоритм исчисления порядка . . . . . . . . . . . . . . 45
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 50
4. Электронная, или цифровая подпись 52
4.1. Электронная подпись RSA . . . . . . . . . . . . . . . . . 52
4.2. Электронная подпись на базе шифра Эль-Гамаля . . . 55
4.3. Стандарты на электронную (цифровую) подпись . . . . 58
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 62
5. Криптографические протоколы 65
5.1. Ментальный покер . . . . . . . . . . . . . . . . . . . . . 65
5.2. Доказательства с нулевым знанием . . . . . . . . . . . . 70
Задача о раскраске графа . . . . . . . . . . . . . . . . . 71
Задача о нахождении гамильтонова цикла в графе . . . 75
5.3. Электронные деньги . . . . . . . . . . . . . . . . . . . . 82
5.4. Взаимная идентификация с установлением ключа . . . 88
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 95
6. Криптосистемы на эллиптических кривых . . . 97
6.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2. Математические основы . . . . . . . . . . . . . . . . . . 98
6.3. Выбор параметров кривой . . . . . . . . . . . . . . . . . 106
6.4. Построение криптосистем . . . . . . . . . . . . . . . . . 108
Шифр Эль-Гамаля на эллиптической кривой . . . . . . 109
Цифровая подпись по ГОСТ Р34.10-2001 . . . . . . . . 110
6.5. Эффективная реализация операций . . . . . . . . . . . 111
6.6. Определение количества точек на кривой . . . . . . . . 117
6.7. Использование стандартных кривых . . . . . . . . . . . 126
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 129
7. Теоретическая стойкость криптосистем . . .131
7.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.2. Теория систем с совершенной секретностью . . . . . . . 132
7.3. Шифр Вернама . . . . . . . . . . . . . . . . . . . . . . . 134
7.4. Элементы теории информации . . . . . . . . . . . . . . 135
7.5. Расстояние единственности шифра с секретным ключом. . . 142
7.6. Идеальные криптосистемы . . . . . . . . . . . . . . . . . 148
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . 154
8. Современные шифры с секретным ключом 156
8.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.2. Блоковые шифры . . . . . . . . . . . . . . . . . . . . . . 159
Шифр ГОСТ 28147-89 . . . . . . . . . . . . . . . . . . . 161
Шифр RC6 . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Шифр Rijndael (AES) . . . . . . . . . . . . . . . . . . . . 167
8.3. Основные режимы функционирования блоковых шифров . . . . 177
Режим ECB . . . . . . . . . . . . . . . . . . . . . . . . . 177
Режим CBC . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.4. Потоковые шифры . . . . . . . . . . . . . . . . . . . . . 179
Режим OFB блокового шифра . . . . . . . . . . . . . . . 181
Режим CTR блокового шифра . . . . . . . . . . . . . . . 182
Алгоритм RC4 . . . . . . . . . . . . . . . . . . . . . . . . 183
8.5. Криптографические хеш-функции . . . . . . . . . . . . 185
9. Случайные числа в криптографии 188
9.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
9.2. Использование физических генераторов . . . . . . . . . 190
9.3. Генераторы псевдослучайных чисел . . . . . . . . . . . 192
9.4. Тесты для проверки генераторов . . . . . . . . . . . . . 195
9.5. Статистическая атака на блоковые шифры . . . . . . . 200
Ответы к задачам и упражнениям . . .214
Список литературы . . .218