Читать онлайн «Практикум по криптосистемам с открытым ключом»

Η. Α. Молдовян ПРАКТИКУМ ПО КРИПТОСИСТЕМАМ С ОТКРЫТЫМ КЛЮЧОМ Санкт-Петербург «БХВ-Петербург» 2015 УДК 681. 3 ББК 32. 81 М75 Молдовян Н. А. М75 Практикум по криптосистемам с открытым ключом. — СПб. : БХВ-Петербург, 2015. — 304 с: ил. ISBN 978-5-9775-3524-3 Приведено краткое изложение математических результатов, используемых при синтезе и анализе криптосистем с открытым ключом, и ряда классических и новых криптосистем этого типа, включая достаточно большое число схем электронной цифровой подписи (ЭЦП). Основная часть книги содержит материалы для проведения практических занятий: формулировки заданий для курсовых работ и проектов и большое количество оригинальных задач, связанных с новыми схемами ЭЦП или вопросами, касающимися синтеза и анализа последних. Все задачи сопровождаются подробными указаниями и решениями. Для преподавателей, студентов и аспирантов инженерно-технических вузов УДК 681. 3 ББК 32. 81 Группа подготовки издания: Главный редактор Екатерина Кондукова Зам. главного редактора Игорь Шиишгин Зав, редакцией Григорий Добин Компьютерная верстка Сергея Матвеева Корректор Наталия Першакова Дизайн обложки Игоря Цырулыткова Зав. производством Николай Тверских Формат 70х1001/,6. Усл. печ, п. 24,51. Доп. тираж 20 экз. "БХВ-Петербург", 191036, Санкт-Петербург, Гончарная ул. , 20. Отпечатано в типографии ООО "Супврвэйв Групп" 193149, РФ, Ленинградская область, Всеволожский район, пос Красная Заря, д. 15 ISBN 978-5-9775-3524-3 '<■'■ модаовян н. Α. , 2007,2015 Ό Оформление. тдатсльство "БХП-Петербург", 2007. 2015 Содержание Введение 5 Глава 1. Понятия и результаты теории чисел 7 1. 1. Сравнения: некоторые свойства и теоремы 7 1. 2. Показатели и первообразные корни 9 1. 3. Индексы по модулям/;"и 2р" 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. Извлечение корней степени и > 2 по простому модулю 32 2. 10. Факторизация Л-гладкого модуля 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 Практикум по криптосистемам с открытым ключом Глава 4. Схемы ЭЦП с новым механизмом формирования подписи 63 4. 1. Схемы с формированием подписи на основе решения системы сравнений 63 4. 2. Схемы с подписью вида (k. S) 67 4. 3.