Обозначения | 8
|
Введение | 14
|
Глава 1. Из истории криптографии | 17
|
1.1. Исторические шифры | 17
|
1.1.1. Простейшие подстановочные шифры (шифры простой замены) | 18
|
1.1.2. Полиалфавитные подстановочные шифры | 23
|
1.1.3. Простейшие шифры перестановки | 27
|
Упражнения | 33
|
Задачи | 36
|
1.2. Криптоанализ классических шифров | 41
|
1.2.1. Криптоанализ шифров перестановки | 41
|
1.2.2. Криптоанализ шифров простой замены | 42
|
1.2.3. Криптоанализ полиалфавитных криптосистем | 45
|
Упражнения | 50
|
Задачи | 54
|
1.3. Задачи криптографических олимпиад | 61
|
Примеры решения задач | 61
|
Задачи | 66
|
Глава 2. Простейшие симметричные криптосистемы | 74
|
2.1. Аффинные криптосистемы | 74
|
Упражнения | 80
|
Задачи | 83
|
2.2. Криптоанализ аффинных криптосистем | 85
|
Упражнения | 88
|
Задачи | 90
|
Глава 3. Шифрующие матрицы | 94
|
3.1. Алгебра матриц и аффинные матричные криптосистемы | 94
|
Упражнения | 104
|
Задачи | 107
|
3.2. Криптоанализ аффинных матричных криптосистем | 111
|
Упражнения | 116
|
Задачи | 118
|
Глава 4. Система RSA. Дискретный логарифм | 123
|
4.1. Система RSA и ее модификации | 123
|
4.1.1. Криптосистема без передачи ключей | 125
|
4.1.2. Криптосистема с открытым ключом | 128
|
4.1.3. Электронная подпись | 130
|
Упражнения | 133
|
Задачи | 135
|
4.2. Дискретный логарифм | 138
|
4.2.1. Показатели, первообразные корни и индексы | 138
|
4.2.2. Метод перебора | 140
|
4.2.3. Метод согласования | 142
|
4.2.4. Метод Сильвестра–Полига–Хеллмана | 144
|
4.2.5. Алгоритм исчисления порядка | 148
|
Упражнения | 151
|
Задачи | 152
|
Глава 5. Вычислительные алгоритмы и их трудоемкость | 156
|
5.1. Трудоемкость арифметических действий | 156
|
5.1.1. Системы счисления | 157
|
5.1.2. Символ "О"-большое | 160
|
5.1.3. Анализ трудоемкости арифметических действий | 161
|
5.1.4. Классификация алгоритмов по их трудоемкости | 167
|
Упражнения | 169
|
Задачи | 173
|
5.2. Простейшие арифметические алгоритмы и их трудоемкость | 175
|
5.2.1. Алгоритм Евклида | 175
|
5.2.2. Расширенный алгоритм Евклида | 179
|
5.2.3. Бинарный алгоритм Евклида | 180
|
5.2.4. Расширенный бинарный алгоритм | 184
|
5.2.5. Решение неопределенных уравнений первой степени | 185
|
5.2.6. Алгоритм возведения в степень по модулю n | 188
|
Упражнения | 191
|
Задачи | 193
|
Глава 6. Простые и псевдопростые числа | 195
|
6.1. Простые числа. Критерии простоты | 195
|
Упражнения | 200
|
Задачи | 202
|
6.2. Вероятностные тесты простоты. Псевдопростые числа | 204
|
6.2.1. Тест Ферма | 205
|
6.2.2. Тест Соловея–Штрассена | 209
|
6.2.3. Тест Миллера–Рабина | 212
|
Упражнения | 215
|
Задачи | 217
|
6.3. Детерминированные тесты простоты. Генерация больших простых чисел | 219
|
6.3.1. Проверка простоты с использованием числа n-1 | 220
|
6.3.2. Проверка простоты с использованием числа n+1 | 222
|
6.3.3. Генерация простых чисел | 226
|
Упражнения | 227
|
Задачи | 228
|
Глава 7. Факторизация натуральных чисел | 232
|
7.1. Классические методы факторизации | 232
|
7.1.1. Метод пробного деления | 233
|
7.1.2. Метод Ферма | 234
|
Упражнения | 238
|
Задачи | 238
|
7.2. Современные методы факторизации. Вскрытие системы RSA | 240
|
7.2.1. Метод Полларда–Флойда | 240
|
7.2.2. (P-1)-метод Полларда | 242
|
7.2.3. Вскрытие системы RSA | 244
|
Упражнения | 258
|
Задачи | 259
|
Глава 8. Псевдослучайные последовательности над конечным полем | 261
|
8.1. Поля и кольца классов вычетов. Характеристика конечного поля | 262
|
8.1.1. Кольца и поля. Примеры | 262
|
8.1.2. Натуральные кратные элементов поля и характеристика поля | 265
|
8.1.3. Расширения конечного поля. Существование конечного поля | 266
|
8.1.4. Мультипликативная группа конечного поля | 268
|
Упражнения | 270
|
Задачи | 271
|
8.2. Кольцо многочленов над полем F. Построение конечного поля | 273
|
8.2.1. Неприводимые над полем многочлены | 275
|
8.2.2. Сравнимость многочленов и построение конечного поля Fpn | 278
|
8.2.4. Примитивные многочлены над конечным полем | 284
|
Упражнения | 285
|
Задачи | 287
|
8.3. Линейные рекуррентные последовательности над конечным полем | 290
|
8.3.1. Псевдослучайные последовательности | 290
|
8.3.2. Последовательности над конечнымполем | 292
|
8.3.3. Линейные рекуррентные последовательности | 293
|
8.3.4. Аннулирующие многочлены | 296
|
Упражнения | 299
|
Задачи | 301
|
Глава 9. Задания для организации промежуточного и итогового контроля | 303
|
9.1. Контрольные вопросы | 303
|
9.2. Типовые задания обязательного минимума по основам криптографии | 305
|
9.3. Задания для творческих лабораторных работ к разделу "Из истории криптографии" | 312
|
9.3.1. Таблица Виженера | 312
|
9.3.2. Шифр по книге | 313
|
9.3.3. Частотный анализ | 313
|
9.3.4. Решетки Кардано | 317
|
9.3.5. Двойная перестановка | 318
|
9.4. Задания для лабораторных работ к разделу "Простейшие симметричные криптосистемы. Шифрующие матрицы" | 318
|
9.4.1. Аффинные криптосистемы | 318
|
9.4.2. Шифрующие матрицы | 319
|
9.4.3. Содержание отчета | 320
|
9.5. Задания для лабораторных работ к разделу "Система RSA. Дискретный логарифм" | 320
|
9.5.1. Система без передачи ключей | 320
|
9.5.2. Система с открытым ключом | 321
|
9.5.3. Электронная подпись | 321
|
9.5.4. Дискретный логарифм | 322
|
9.5.5. Содержание отчета | 322
|
9.6. Задания для лабораторных работ к разделу "Вычислительные алгоритмы и их трудоемкость" | 323
|
9.6.1. Алгоритм Евклида, его модификации и их трудоемкость | 323
|
9.6.2. Применение алгоритма Евклида к решению неопределенных уравнений первой степени | 323
|
9.6.3. Содержание отчета | 325
|
9.7. Задания для лабораторных работ к разделу "Простые и псевдопростые числа" | 326
|
9.7.1. Простейшие алгоритмы проверки чисел на простоту | 326
|
9.7.2. Вероятностные алгоритмы проверки чисел на простоту | 326
|
9.7.3. Содержание отчета | 327
|
9.8. Задания для лабораторных работ к разделу "Факторизация натуральных чисел" | 328
|
9.8.1. Классические методы факторизации | 328
|
9.8.2. Методы факторизации Полларда | 328
|
9.8.3. Содержание отчета | 328
|
9.9. Задания для лабораторной работы к разделу "Псевдослучайные последовательности над конечным полем" | 330
|
9.9.1. Содержание отчета | 330
|
Глава 10. Таблицы | 332
|
10.1. Таблицы числовых эквивалентов символов русского и английского алфавитов | 332
|
10.2. Таблицы Виженера | 333
|
10.3. Таблицы частотности | 334
|
10.4. Таблицы простых чисел | 338
|
10.5. Таблицы неприводимых и примитивных многочленов | 346
|
10.6. Таблицы индексов | 348
|
Ответы и решения | 355
|
Словарь терминов | 359
|
Литература | 363
|