Маховенко Е. Б. Теоретико-числовые методы в криптографии: Учебное пособие / Е. Б. Маховенко. — М.: Гелиос АРВ, 2006. — 320 с., ил.
В учебном пособии излагаются методы решения алгебраических и теоретико-числовых задач, возникающих при разработке и исследовании криптографических методов и средств защиты информации. Изучаются алгоритмы арифметики больших целых чисел и полиномов, проверки чисел на простоту и разложения на множители. Исследуется безопасность криптосистем RSA, Диффи-Хеллмана, ранцевых криптосистем.
Приведены примеры практических заданий по реализации ряда алгоритмов.
Для студентов, обучающихся по специальности «Компьютерная безопасность».
ОГЛАВЛЕНИЕ
Введение...............................................................3
Глава 1. ДЕЛИМОСТЬ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ................................5
1.1. Делимость в кольце целых чисел.........................7
1.2. Наибольший общий делитель и наименьшее общее кратное 11
1.3. Вычисление наибольшего общего делителя.......................16
1.3.1. Алгоритм Евклида..........................................16
1.3.2. Бинарный алгоритм Евклида................................20
1.3.3. Расширенный алгоритм Евклида......................22
1.4. Простые числа.......................................27
1.4.1. Свойства простых чисел...................................27
1.4.2. Распределение простых чисел.............................30
Упражнения к главе 1...............................................32
Литература к главе 1.............................................33
Глава 2. СРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ...........................34
2.1. Отношение сравнимости....................................34
2.2. Решение сравнений........................................40
2.2.1. Сравнения первой степени.................................41
2.2.2. Китайская теорема об остатках............................45
2.2.3. Сравнения произвольной степени по простому модулю.... 48
2.3. Сравнения второй степени................................50
2.3.1. Символы Лежандра и Якоби................................50
2.3.2. Случаи простого модуля..................................62
2.3.3. Случаи составного модуля...........................67
Упражнения к главе 2............................................79
Литература к главе 2...........................................81
Глава 3. ОСНОВЫ ТЕОРИИ НЕПРЕРЫВНЫХ ДРОБЕЙ................82
3.1. Определение непрерывной дроби.........................82
3.2. Подходящие дроби........................................86
3.3. Квадратичные иррациональности............................99
3.4. Использование непрерывных дробей для решения задач............103
3.4.1. Простейшие диофантовы уравнения и сравнения первой степени..........104
3.4.2. Уравнение Пелля..............................................105
3.4.3. Представление числа в виде суммы квадратов........................111
3.5. Разложение функций в непрерывные дроби.............................113
Упражнения к главе 3.....................................116
Литература к главе 3.....................................................117
Глава 4. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ.............118
4.1. Сложение и вычитание.................................................118
4.2. Умножение...........................................................121
4.2.1. Умножение «в столбик». Возведение в квадрат.........................121
4.2.2. Умножение методом Карацубы-Офмана................................124
4.2.3. Умножение в классах вычетов........................................125
4.3. Умножение с помощью быстрого преобразования Фурье .... 130
4.3.1. Дискретное преобразование Фурье..........................130
4.3.2. Алгоритм быстрого преобразования Фурье...................140
4.3.3. Алгоритм Шенхаге-Штрассена для умножения целых чисел.............146
4.4. Модульное умножение.............................................150
4.4.1. Метод Монтгомери................................................150
4.4.2. Модульное возведение в степень..........................154
4.5. Целочисленное деление с остатком................................157
4.5.1. Схема Горнера.................................................158
4.5.2. Деление на 2m - с.......................................................160
4.5.3. Общий случай......................................................161
Упражнения к главе 4........................................166
Литература к главе 4...............................................167
Глава 5. ПРОВЕРКА ЧИСЕЛ НА ПРОСТОТУ.............................169
5.1. Вероятностные алгоритмы проверки чисел на простоту............169
5.1.1. Тест Ферма...................................................171
5.1.2. Тест Соловэя-Штрассена.........................................179
5.1.3. Тест Милл ера-Рабина...........................................183
5.1.4. Генерация простого числа..........................................192
5.2. Детерминированные алгоритмы проверки чисел на простоту..........193
5.2.1. Проверка чисел Мерсенна.................................194
5.2.2. Проверка с использованием разложения числа n - 1....................200
Упражнения к главе 5...........................................203
Литература к главе 5.....................................................205
Глава 6. РАЗЛОЖЕНИЕ ЧИСЕЛ НА МНОЖИТЕЛИ И КРИПТОСИСТЕМА RSA................207
6.1. Метод пробного деления.............................................207
6.2. р-метод Полларда.................................................209
63.(р- 1 )-Метод Полларда................................................213
6.4. Метод квадратов.................................................216
6.4.1. Метод непрерывных дробей........................................219
6.4.2. Метод квадратичного решета......................................222
6.5. Криптографическая система RSA...................................225
6.5.1. Принцип действия................................................226
6.5.2. Безопасность криптосистемы RSA и задача разложения на множители......227
6.5.3. Атаки на криптосистему RSA, не требующие разложения 229
Упражнения к главе 6...................................................236
Литература к главе 6....................................................237
Глава 7. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ В КОНЕЧНОМ ПОЛЕ....................239
7.1. Задача дискретного логарифмирования в конечном поле .. 239
7.1.1. р-Метод Полларда..............................................240
7.1.2. Методы Гельфонда и Сильвера-Полига-Хеллмана....................242
7.1.3. Метод встречи посередине......................................246
7.1.4. Метод базы разложения........................................247
7.2. Протокол Диффи-Хеллмана...............................249
Упражнения к главе 7.................................................253
Литература к главе 7.................................................254
Глава 8. ЭЛЕМЕНТЫ ТЕОРИИ РЕШЕТОК........................................256
8.1. Процесс ортогонализации Грама-Шмидта......................... 256
8.2. Алгоритм Ленстры-Ленстры-Ловаша и его применение..........259
8.3. Задача об укладке ранца...................................273
8.3.1. Способы решения..............................................274
8.3.2. Ранцевые алгоритмы шифрования с открытым ключом..........278
Упражнения к главе 8...............................................283
Литература к главе 8.......................................284
ПРИЛОЖЕНИЕ......................................................286
Лабораторная работа 1. Вычисление наибольшего общего делителя....... 287
Лабораторная работа 2. Вероятностные алгоритмы проверки чисел на простоту...... 290
Лабораторная работа 3. Разложение чисел на множители.......... 296
Лабораторная работа 4. Дискретное логарифмирование в конечном поле............. 299
Лабораторная работа 5. Алгоритм Ленстры-Ленстры-Ловаша и его применение....... 303
ОТВЕТЫ И УКАЗАНИЯ К УПРАЖНЕНИЯМ............................ 308
