| Обозначения | 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
|
Деза Елена Ивановна 
Котова Лидия Владимировна 
