Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию.
Книга 2: Протоколы криптографии на эллиптических кривых. Кн.2. Изд. 3, испр. и доп.

2019. 376 с.

Серия: Основы защиты информации

Типографская бумага

Мягкая обложка
Твердый переплет 1707 р. ››

Все последующие издания — стереотипные.

Аннотация

Настоящая книга содержит описание и сравнительный анализ алгоритмов на эллиптических кривых. Изучаются протоколы эллиптической криптографии, имеющие аналоги, --- протоколы на основе алгебраических свойств мультипликативной группы конечного поля, и протоколы, для которых таких аналогов нет, --- протоколы, основанные на операциях спаривания на эллиптических кривых по алгоритмам Вейля и Тейта и их модификациям, описанным в книге. Изложение теории... (Подробнее)

Оглавление

Предисловие
1. Алгоритмы на эллиптических кривых
	1.1.	Алгоритм сложения и удвоения точек
		1.1.1.	Общая схема алгоритма сложения
		1.1.2.	Частные формулы для сложения и удвоения
		1.1.3.	Алгоритмы сложения и удвоения точек эллиптических кривых
	1.2.	Эллиптические кривые над GF(2ⁿ)
		1.2.1.	Суперсингулярные кривые
		1.2.2.	Несуперсингулярные кривые
		1.2.3.	Стандарты о выборе кривых для реализации криптосистем на эллиптических кривых
	1.3.	Скалярное умножение на суперсингулярных кривых
		1.3.1.	Вычисление k.P методом аддитивных цепочек
		1.3.2.	Использование проективных координат
		1.3.3.	Метод Монтгомери
	1.4.	Скалярное умножение на несуперсингулярных кривых
		1.4.1.	Метод Монтгомери для несуперсингулярных кривых
		1.4.2.	Метод Монтгомери в проективных координатах
		1.4.3.	Метод Лопеса–Дахаба использования проективных координат
		1.4.4.	Алгоритм скалярного умножения, использующий операцию "ополовинивания"
	1.5.	Скалярное умножение на аномальных кривых
		1.5.1.	Свойства кривых Коблица
		1.5.2.	Использование модулярной редукции
	1.6.	Вычисление дискретного логарифма
		1.6.1.	Проблема дискретного логарифмирования
		1.6.2.	Алгоритм "большой шаг – малый шаг"
		1.6.3.	Алгоритм для групп составных порядков
Глава 2. Протоколы на эллиптических кривых
	2.1.	Выбор точки и размещение данных
		2.1.1.	Введение
		2.1.2.	Решение квадратных уравнений
		2.1.3.	Выбор точки эллиптической кривой
		2.1.4.	Размещение данных на эллиптической кривой
		2.1.5.	Определение порядка точки эллиптической кривой и нахождение образующего элемента группы точек эллиптической кривой
	2.2.	Распределение ключей
		2.2.1.	Введение
		2.2.2.	Распределение ключей для классической криптосистемы (протокол Диффи–Хеллмана)
		2.2.3.	Распределение ключей для классической криптосистемы (протокол Месси–Омуры)
		2.2.4.	Протокол распределения ключей Менезеса–Кью–Венстоуна (MQV-протокол)
	2.3.	Криптосистемы Эль-Гамаля
	2.4.	Протоколы цифровой подписи
		2.4.1.	Электронная цифровая подпись
		2.4.2.	Обобщенная схема электронной подписи Эль-Гамаля
		2.4.3.	Электронная подпись Эль-Гамаля с возвратом сообщения – схема Nyberg–Rueppel
	2.5.	Передача с забыванием
		2.5.1.	Введение
		2.5.2.	Схема некоторых протоколов передачи с забыванием
		2.5.3.	Некоторые частные случаи передачи с забыванием
		2.5.4.	Передача комбинации k из n сообщений с забыванием
		2.5.5.	Применение передачи k из n сообщений с забыванием
Глава 3. Криптосистемы на основе спариваний
	3.1.	Билинейная проблема Диффи–Хеллмана
		3.1.1.	Однораундовый протокол генерации общего секретного ключа между тремя участниками
		3.1.2.	Короткая цифровая подпись, основанная на спаривании
		3.1.3.	Криптосистема с публичным индивидуальным ключом
	3.2.	Спаривание Андре Вейля на эллиптических кривых
		3.2.1.	Дивизоры
		3.2.2.	Явное определение спаривания Вейля
		3.2.3.	Функции на гиперэллиптических кривых
	3.3.	Алгоритм вычисления спариваний Вейля и Тейта
		3.3.1.	Усовершенствования алгоритма Миллера
	3.4.	Спаривание Тейта
		3.4.1.	Применение спариваний для логарифмирования в эллиптических кривых
		3.4.2.	Кривые, удобные для спаривания
		3.4.3.	Искажающее отображение
		3.4.4.	Удобные для спаривания кривые с множителем безопасности kменьше 2
		3.4.5.	Удобные для спаривания поля
	.5.	Кривые над полями характеристики три
		3.5.1.	Устранение делений
	3.6.	О больших значениях параметра безопасности
		3.6.1.	Скалярное умножение точек кривой над полем большой характеристики
		3.6.2.	Ускорение алгоритма Миллера для больших k
		3.6.3.	Итерированное удвоение в якобиевых координатах
		3.6.4.	Комбинирование с другими методами
		3.6.5.	Использование аддитивных цепочек с двойной базой
	3.7.	Алгоритм Дуурсма–Ли
		3.7.1.	Алгоритм Дуурсма–Ли над полями характеристики два
	3.8.	Некоторые алгоритмы арифметики конечных полей
		3.8.1.	Извлечение квадратных корней в полях характеристики большей двух
		3.8.2.	Извлечение корней p-й степени в полях характеристики p
		3.8.3.	Один метод компактной записи точек суперсингулярных кривых
		3.8.4.	Арифметика в полях характеристики большей двух
	3.9.	О реализации алгоритма Дуурсма–Ли
		3.9.1.	Использование нормального базиса в поле G
		3.9.2.	Умножение в поле K методом Карацубы
		3.9.3.	Умножение в поле K методом Тоома
		3.9.4.	Возведение в степень p в поле K
Приложение A. Алгоритмы с двоичными матрицами
	A.1.	Представление векторов и матрицы
	A.2.	Умножение матрицы на вектор
	A.3.	Алгоритм GAUS-MATRIX-TRIAN
	A.4.	Алгоритм проверки невырожденности матрицы
	A.5.	Приведение матрицы к диагональному виду
	A.6.	Обращение матрицы
	A.7.	Умножение вектор-строки на матрицу
Приложение B. Таблицы неприводимых многочленов
	B.1.	Неприводимые многочлены над полем GF(2)
		B.1.1.	Неприводимые трехчлены степени n, 2<=n<=2000
		B.1.2.	Неприводимые трехчлены вида 1 + X^n-1 + Xⁿ степени n, 2<=n 34353
		B.1.3.	Неприводимые пятичлены степени n, 8<=n<=290
	B.2.	Неприводимые трехчлены над полем GF(3)
Приложение C. Таблицы ОНБ
	C.1.	ОНБ размерности n, 2<=n<=30
	C.2.	ОНБ размерности n, 30<n< 1013
	C.3.	Возможные размерности ОНБ n, 998<n<10000 Приложение D. Примеры исполнения MQV-протокола
Литература
Предметный указатель
Уточнения и дополнения к первому изданию

Предисловие

Настоящее второе издание публикуется параллельно со вторым изданием (М.: URSS, 2012) книги "Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы", которая является сходной по тематике. Поэтому ссылки на нее в тексте помечены как первая книга. Во втором издании обеих книг помещен раздел "Уточнения и дополнения к первому изданию". Работа авторов над вторым изданием осуществлена при финансовой поддержке Российского фонда фундаментальных исследований, проекты N08–01–00632а и N11–01–00792а. При этом были учтены замечания наших читателей и использованы научные результаты авторов, полученные при выполнении указанных проектов.

Первая глава данной книги посвящена базовым алгоритмам для операций в группе точек эллиптических кривых. Такими операциями являются основная операция сложения, операция умножения на константу, равную характеристике поля, и основная криптографическая операция – умножение точки на произвольную константу, аддитивный аналог операции возведения в степень элемента мультипликативной группы. Анализируются условия безопасного применения этих операций, в связи с чем приводятся рекомендации стандартов по выбору эллиптических кривых. Приводится и алгоритм дискретного логарифмирования в группе точек эллиптической кривой.

Во второй главе описаны примитивные операции – взятие точки эллиптической кривой и размещение данных в точке кривой. Здесь формируется представление о реализации на эллиптических кривых ряда известных криптографических протоколов (распределения ключей для классической криптосистемы, цифровой подписи, передачи с забыванием), допускающих также реализацию с использованием мультипликативной группы конечного поля.

Третья глава отражает последние достижения в области криптографических приложений эллиптических кривых. В ней рассматриваются так называемые спаривания Вейля и Тейта и основанные на них криптосистемы с новыми интересными свойствами, которые не удается реализовать, используя только арифметику конечного поля.

В Приложении помещены таблицы неприводимых многочленов и некоторые громоздкие примеры.

Для удобства пользования в конце книги приведен предметный указатель, где ссылки на первую книгу [4] помечены символом I после номера страницы.

Приведен также список цитируемых источников.

Теоремы, следствия, леммы, утверждения, примеры и упражнения нумеруются по главам и разделам, например, "Теорема 3.2.1" есть первая теорема второго раздела третьей главы; а уравнения (или алгебраические выражения), таблицы и рисунки имеют сплошную нумерацию внутри главы, и номер раздела в их обозначениях отсутствует.

В издании отражен опыт преподавания авторами математических основ криптологии и криптографических методов обеспечения информационной безопасности в Московском государственном университете, Московском энергетическом институте, на факультете защиты информации Российского государственного гуманитарного университета, на кафедре информационной безопасности Российского государственного социального университета и даже в физико-математической школе-интернате при МГУ.

При подготовке примеров использована библиотека алгоритмов криптографии эллиптических кривых и "визуализирующий" ее алгебраический процессор, разработанные под руководством авторов студентами МЭИ П.И.Артемьевой, В.С.Гамовым, Я.Ю.Грачевым, А.Б.Дроздовым, Ал.И.Мамонтовым и Е.В.Шестаковым при выполнении дипломных проектов и магистерских диссертаций, и другие программы, разработанные под руководством авторов студентами МГУ и МЭИ.

В заключение авторы выражают благодарность за замечания О.Н.Василенко и Д.В.Матюхину, прочитавшим рукопись, студентам МЭИ и МГУ, заметившим ряд неточностей и осуществившим экспериментальную проверку описаний алгоритмов и числовых параметров, приведенных в книге. Также мы благодарны заведующему кафедрой информационной безопасности РГСУ профессору А.В.Бабашу и доценту РГГУ Э.А.Применко за поддержку настоящего издания. Мы с благодарностью примем замечания наших читателей.

Опечатка

PDF

Об авторах

Болотов Анатолий Александрович

Кандидат физико-математических наук, доцент. До 2000 г. доцент кафедры математического моделирования МЭИ и старший научный сотрудник кафедры математической теории интеллектуальных систем механико-математического факультета МГУ имени М. В. Ломоносова; с 2000 г. работает в США, Member of Board of Trustees (Lincoln University, California, USA), Distinguished Engineer/Director (LSI/Avago/Intel Corporation, California, USA). Соавтор книг "Дискретная математика и сложность алгоритмов", "Алгоритмические основы эллиптической криптографии", "Основы теории однородных структур", "Элементарное введение в эллиптическую криптографию" (URSS; в 2 кн.), "Дискретная математика: теория однородных структур", "Дискретная математика: прикладные задачи и сложность алгоритмов" и других.

Гашков Сергей Борисович

Доктор физико-математических наук, профессор. Профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова. Автор и соавтор книг «Примени математику», «Арифметика. Алгоритмы. Сложность вычислений», «Системы счисления и их применения», «Современная элементарная алгебра», «Элементарное введение в эллиптическую криптографию» (URSS; в 2 кн.), «Криптографические методы защиты информации», «Занимательная компьютерная арифметика» (URSS; в 2 кн.), «Геометрические неравенства: Путеводитель в задачах и теоремах» (URSS), «Алгоритмические основы эллиптической криптографии», «Дискретная математика: Учебник и практикум для академического бакалавриата», «Обыкновенные дроби: От Древнего Египта до наших дней» (URSS), «Булев куб, или Булеан: Уникальная комбинаторная конструкция и ее приложения» (URSS), «Введение в конструктивную комбинаторику» (URSS), «Элементарная комбинаторика» (URSS).

Фролов Александр Борисович

Доктор технических наук, профессор. Профессор кафедры математического моделирования НИУ "МЭИ". Автор и соавтор книг "Модели и методы технической диагностики", "Дискретная математика и сложность алгоритмов", "Алгоритмические основы эллиптической криптографии", "Элементарное введение в эллиптическую криптографию" (URSS; в 2 кн.), "Дискретная математика: Учебник и практикум для академического бакалавриата", "Дискретная математика: Прикладные задачи и сложность алгоритмов" и других.