Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию.
Книга 1: АЛГЕБРАИЧЕСКИЕ И АЛГОРИТМИЧЕСКИЕ ОСНОВЫ. Кн.1. Изд. 3, испр. и доп.

Элементарное введение в эллиптическую криптографию. Книга 1: Алгебраические и алгоритмические основы URSS. 2019. 376 с. ISBN 978-5-9710-5390-3.

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

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

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

Аннотация

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

Оглавление

Предисловие
1	Введение
	1.1.	Криптография с открытым ключом
	1.2.	Группы, кольца, поля
		1.2.1.	Группы
		1.2.2.	Кольца. Поля. Многочлены над полем
		1.2.3.	Алгоритм Евклида и его варианты
2	Конечные поля и эллиптические кривые
	2.1.	Поля Галуа
		2.1.1.	Характеристика поля
		2.1.2.	Мультипликативная группа конечного поля
		2.1.3.	Конечное расширение поля
		2.1.4.	Поле разложения многочлена
		2.1.5.	Минимальные многочлены. Существование неприводимых многочленов
		2.1.6.	След и норма элемента конечного поля
		2.1.7.	Алгоритмическое представление конечного поля
		2.1.8.	Поле Галуа как векторное пространство
		2.1.9.	Проверка, является ли нормальная система базисом. Переход от нормального базиса к стандартному
		2.1.10.	Переход от стандартного базиса к нормальному
		2.1.11.	О быстрой линейной алгебре
		2.1.12.	Быстрый алгоритм для решения систем линейных уравнений над конечным полем
		2.1.13.	Оптимальные и гауссовы нормальные базисы
		2.1.14.	Алгебраическое замыкание конечного поля
		2.1.15.	Квадратичные вычеты и извлечение квадратных корней в конечных полях
	2.2.	Эллиптические кривые
		2.2.1.	Алгебраические кривые и эллиптические кривые
		2.2.2.	Группа точек эллиптической кривой
		2.2.3.	Эллиптические кривые над полями действительных и рациональных чисел
	2.3.	Эллиптические кривые над конечными полями
		2.3.1.	Порядок эллиптической кривой
		2.3.2.	Легко ли вычислить порядок группы точек эллиптической кривой
		2.3.3.	Применения теоремы Хассе
		2.3.4.	О структуре групп эллиптических кривых
3	Неприводимые многочлены
	3.1.	Тестирование и поиск неприводимых многочленов
		3.1.1.	Чем интересны неприводимые многочлены
		3.1.2.	Тест на неприводимость. Алгоритм Берлекемпа
		3.1.3.	Оценка сложности алгоритма Евклида
		3.1.4.	Тестирование неприводимости многочленов
		3.1.5.	О тестировании неприводимости многочленов малого веса
		3.1.6.	Асимптотически быстрый алгоритм тестирования неприводимости многочленов
		3.1.7.	Вероятностные алгоритмы тестирования неприводимости многочленов
		3.1.8.	Генерация неприводимых многочленов
	3.2.	Тестирование примитивных многочленов
		3.2.1.	Тестирование примитивности неприводимого многочлена
		3.2.2.	Генерация примитивных многочленов
		3.2.3.	Генерация примитивных элементов в поле $GF(p^n)$
	3.3.	Алгоритмы вычисления минимального многочлена
		3.3.1.	О сложности вычисления минимальных многочленов
		3.3.2.	Быстрый алгоритм вычисления минимального многочлена
	3.4.	Генерация нормальных базисов
		3.4.1.	Критерии базисности нормальной системы
		3.4.2.	Быстрое тестирование базисности нормальных систем
		3.4.3.	O нормальных базисах, порождаемых многочленами малого веса
4	Арифметика GF(2^n) в полиномиальном базисе
	4.1.	Особенности реализации операций
		4.1.1.	Выбор поля и способов реализации
	4.2.	Классический алгоритм умножения в GF(2)[X]
		4.2.1.	Элементарные многочлены. Таблица умножения
		4.2.2.	Умножение многочленов с использованием таблицы умножения
		4.2.3.	Модификация классического алгоритма и гибридный алгоритм умножения
		4.2.4.	Еще две модификации классического алгоритма умножения
	4.3.	Алгоритм Карацубы и его реализация
		4.3.1.	О методе Карацубы
		4.3.2.	Умножение многочленов по методу Карацубы
		4.3.3.	Декомпозиционная схема умножения многочленов над GF(2)
		4.3.4.	Умножение многочленов
		4.3.5.	Последовательные программы умножения многочленов и их синтез
	4.4.	Приведение по модулю неприводимого многочлена
		4.4.1.	Классический алгоритм деления многочленов
		4.4.2.	Приведение многочлена по модулю многочлена малого веса
		4.4.3.	Обобщение алгоритма
		4.4.4.	Приведение по модулю многочлена высокого веса
	4.5.	Возведение в степень и инвертирование
		4.5.1.	Возведение в степень 2^m в стандартном базисе
		4.5.2.	Инвертирование в полиномиальном или нормальном базисах
		4.5.3.	Быстрый алгоритм возведения в степень в стандартном базисе
		4.5.4.	Быстрое инвертирование в стандартном базисе поля GF(p^n)
		4.5.5.	Быстрое программное инвертирование на основе алгоритма Евклида
		4.5.6.	Деление с помощью алгоритма Евклида
	4.6.	Асимптотически быстрые алгоритмы
		4.6.1.	Быстрое умножение чисел и многочленов
		4.6.2.	Аддитивные цепочки
		4.6.3.	Приложения аддитивных цепочек
		4.6.4.	Аддитивные цепочки с вычитаниями
		4.6.5.	Алгоритмы возведения в степень с фиксированной базой
		4.6.6.	Ускорение проверки электронной подписи
		4.6.7.	Метод Монтгомери быстрого возведения в степень
		4.6.8.	Пример реализации метода Монтгомери логическими схемами
		4.6.9.	Быстрое возведения в степень через модулярную композицию
		4.6.10.	Быстрое инвертирование в стандартном базисе через модулярную композицию
		4.6.11.	Уточнения в случае q=2
5	Арифметика в нормальных базисах
	5.1.	Оптимальные нормальные базисы
		5.1.1.	Три типа оптимальных нормальных базисов
		5.1.2.	Некоторые примеры примитивных элементов по модулю $p$
		5.1.3.	Алгоритм генерации оптимальных нормальных базисов первого типа и доказательство их оптимальности
		5.1.4.	Алгоритм генерации оптимальных нормальных базисов второго типа и доказательство их оптимальности
		5.1.5.	Алгоритм генерации оптимальных нормальных базисов третьего типа и доказательство их оптимальности
	5.2.	Оптимизация преобразований базисов
		5.2.1.	О комбинированном использовании полиномиального и нормального базисов
		5.2.2.	Пример выполнения алгоритма перехода от оптимального базиса первого типа к стандартному и обратно
		5.2.3.	Примеры построения логических схем для умножения в стандартном и оптимальном нормальном базисе первого типа
		5.2.4.	Оценка сложности перехода от оптимальных нормальных базисов второго и третьего типа к стандартным и обратно
		5.2.5.	О явном вычислении формул перехода и минимальных многочленов для оптимальных нормальных базисов
		5.2.6.	Оценка сложности перехода от оптимальных нормальных базисов второго и третьего типа к стандартным в общем случае
		5.2.7.	Пример выполнения алгоритма перехода от оптимального базиса 2-го или 3-го типа к стандартному и обратно
		5.2.8.	Замечание о программной реализации
		5.2.9.	О сложности арифметических операций в конечных полях
		5.2.10.	Об оценках сложности возведения в степень и инвертирования в конечных полях
	5.3.	Гауссовы нормальные базисы
		5.3.1.	Построение гауссовых нормальных базисов
		5.3.2.	Сложность умножения, инвертирования и возведения в степень в ГНБ
		5.3.3.	Гауссовы базисы и гауссовы периоды
		5.3.4.	Еще один вывод таблицы умножения для ГНБ
		5.3.5.	Примеры гауссовых нормальных базисов в полях $GF(2^n)$
		5.3.6.	Порядки генераторов базисов низкой сложности и быстрый алгоритм возведения в степень
		5.3.7.	О сложности порождения нормальных базисов, примитивных элементов и неприводимых многочленов
		5.3.8.	Редундантные базисы
	5.4.	Операции в нормальных базисах
		5.4.1.	Пример построения схемы для умножения и инвертирования в оптимальных нормальных базисах второго типа
		5.4.2.	Пример схемного инвертирования с использованием редундантного базиса
		5.4.3.	Пример схемы умножения в ГНБ
		5.4.4.	Быстрое программное инвертирование с помощью ГНБ
Литература
Предметный указатель

Предисловие

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

Книга посвящена вычислительным методам конечной алгебры, используемым в современной прикладной криптографии и теории кодирования. Она состоит из пяти глав.

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

Вторая глава посвящена теории и алгоритмическому строению конечных полей и групп точек эллиптических кривых.

Третья глава освещает вопросы тестирования и генерации неприводимых многочленов.

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

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

В конце книги приведен список цитируемых источников и предметный указатель.

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

Алгебраическая и криптографическая терминология согласуется с учебниками.

Большинство излагаемых понятий и алгоритмов иллюстрируется примерами. Наиболее существенные положения формулируются в виде теорем, более сложные из них даются с доказательствами, а более очевидные или менее принципиальные иногда формулируются в виде упражнений с указаниями к решению.

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

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

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

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

Об авторах

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

Кандидат физико-математических наук, доцент. До 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 кн.), "Дискретная математика: Учебник и практикум для академического бакалавриата", "Дискретная математика: Прикладные задачи и сложность алгоритмов" и других.

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

Кандидат физико-математических наук, доцент. Доцент кафедры математической теории интеллектуальных систем механико-математического факультета МГУ имени М. В. Ломоносова, консультант фирмы Huawei Technologies. Соавтор книг "Алгоритмические основы эллиптической криптографии", "Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы" (URSS) и других.