Обозначения 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
Литература
