Введение 5
Глава 1. Понятия и результаты теории чисел 7
1.1. Сравнения: некоторые свойства и теоремы 7
1.2. Показатели и первообразные корни 9
1.3. Индексы по модулям p ? и 2p ? 10
1.4. Теоремы о числе классов с заданным показателем 11
1.5. Теоремы о числе решений степенных сравнений 13
Глава 2. Алгоритмический минимум 15
2.1. Вычисление наибольшего общего делителя и его линейного представления 15
2.2. Китайская теорема об остатках 16
2.3. Алгоритм быстрого возведения в степень по модулю 17
2.4. Нахождение первообразных корней 19
2.5. Нахождение чисел, относящихся к заданному показателю 20
2.6. Генерация простых чисел 21
2.7. Детерминистическая генерация больших простых чисел 23
2.8. Извлечение квадратных корней по простому модулю 26
2.9. Извлечение корней степени n > 2 по простому модулю 32
2.10. Факторизация B-гладкого модуля RSA 37
2.11. Метод дискретного логарифмирования 39
Глава 3. Краткий обзор классических криптосистем с открытым ключом 45
3.1. Открытое распределение ключей 45
3.2. Открытое шифрование 46
3.3. Системы электронной цифровой подписи 48
3.4. Слепая подпись 54
3.5. Схемы ЭЦП с восстановлением сообщения 55
3.6. Экзистенциальная подделка подписи и потайные каналы в системах ЭЦП 58
Глава 4. Схемы ЭЦП с новым механизмом формирования подписи 63
4.1. Схемы с формированием подписи на основе решения системы сравнений 63
4.2. Схемы с подписью вида (k, S) 67
4.3. Схемы с RSA-модулем 70
4.4. Применение простого модуля в схемах, основанных на сложности факторизации 75
4.5. Схемы с восстановлением сообщения 79
4.6. Новые схемы ЭЦП с сокращенной длиной подписи 86
4.7. Новый подход к уменьшению размера подписи до 160 бит 92
Глава 5. Варианты заданий для курсового проектирования 99
5.1. Схемы ЭЦП на основе сложности дискретного логарифмирования 101
5.2. Схемы ЭЦП на основе сложности факторизации RSA-модуля 108
5.3. Схемы ЭЦП с восстановлением сообщения 115
5.4. Схемы ЭЦП с сокращенным размером подписи 121
5.5. Задания повышенной сложности 130
5.6. Генерация числовых примеров 134
Глава 6. Задачник 139
6.1. Элементы теории чисел 139
6.2. Схемы ЭЦП 149
Глава 7. Ответы, решения и пояснения 181
7.1. Элементы теории чисел 181
7.2. Схемы ЭЦП 213
Заключение 291
Список литературы 293