Читать онлайн «Элементарное введение в эллиптическую криптографию 2»

А. А. Болотов, СБ. Пашков А. Б. Фролов ЭЛЕМЕНТАРНОЕ ВВЕДЕНИЕ В ЭЛЛИПТИЧЕСКУЮ КРИПТОГРАФИЮ Протоколы криптографии на эллиптических кривых МОСКВА URSS ББК 32. 81 УДК 512. 8 Болотов Анатолий Александрович, Гашков Сергей Борисович, Фролов Александр Борисович Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. — М. : КомКнига, 2006. — 280 с. ISBN 5-484-00444-6 Настоящая книга содержит описание и сравнительный анализ алгоритмов на эллиптических кривых. Изучаются протоколы эллиптической криптографии, имеющие аналоги — протоколы на основе алгебраических свойств мультипликативной группы конечного поля и протоколы, для которых таких аналогов нет — протоколы, основанные на спаривании Вейля и Тейта. В связи с этим описаны алгоритмы спаривания Вейля и Тейта и их модификации. Изложение теории сопровождается большим числом примеров и упражнений. Предназначено для студентов, преподавателей вузов и специалистов в области защиты информации, прикладной математики, вычислительной техники и информатики. Издание представляет интерес для лиц, связанных с кодированием и передачей информации и цифровой техникой, а также специалистов по прикладной математике, интересующихся компьютерной алгеброй. Издательство «КомКнига». 117312, г. Москва, пр-т 60-летия Октября, 9. Подписано к печати 03. 05. 2006 г. Формат 60x90/16. Печ. л. 17. Зак. № 553. Отпечатано в 000 «ЛЕНАНД». 117312, г. Москва, пр-т 60-летия Октября, д. ПА, стр. 11. Алгоритмы на эллиптических кривых 9 1. 1. Алгоритм сложения и удвоения точек 9 1. 1. 1. Общая схема алгоритма сложения 9 1. 1. 2. Частные формулы для сложения и удвоения 11 1. 1. 3. Алгоритмы сложения и удвоения точек эллиптических кривых 17 1. 2. Эллиптические кривые над GF{2^) 17 1. 2. 1. Суперсингулярные кривые 20 1. 2. 2. Несуперсингулярные кривые 25 1. 2. 3. Стандарты о выборе кривых для реализации криптосистем на эллиптических кривых 27 1. 3. Скалярное умножение на суперсингулярных кривых 31 1. 3. 1. Вычисление к-Р методом аддитивных цепочек 32 1. 3. 2. Использование проективных координат 35 1. 3. 3. Метод Монтгомери 37 1. 4. Скалярное умножение на несуперсингулярных кривых 39 1. 4. 1. Метод Монтгомери для несуперсингулярных кривых 40 1. 4. 2. Метод Монтгомери в проективных координатах 42 1. 4. 3. Метод Лопеса—Дахаба использования проективных координат 43 1. 4. 4. Алгоритм скалярного умножения, использующий операцию «ополовинивания» 45 1. 5. Скалярное умножение на аномальных кривых 54 1. 5. 1. Свойства кривых Коблица 54 1. 5. 2. Использование модулярной редукции 64 1. 6. Вычисление дискретного логарифма 72 1. 6. 1. Проблема дискретного логарифмирования 72 1. 6. 2. Алгоритм «большой шаг — малый шаг» 72 1. 6. 3. Алгоритм для групп составных порядков 74 Глава 2. Протоколы на эллиптических кривых 76 2. 1.