М.: КомКнига, 2006. — 280 с. — ISBN 5-484-00444-6.
Настоящая книга содержит описание и сравнительный анализ алгоритмов
на эллиптических кривых. Изучаются протоколы эллиптической
криптографии, имеющие аналоги — протоколы на основе алгебраических
свойств мультипликативной группы конечного поля и протоколы, для
которых таких аналогов нет — протоколы, основанные на спаривании
Вейля и Тейта. В связи с этим описаны алгоритмы спаривания Вейля и
Тейта и их модификации. Изложение теории сопровождается большим
числом примеров и упражнений.
Предназначено для студентов, преподавателей вузов и специалистов в области защиты информации, прикладной математики, вычислительной техники и информатики. Издание представляет интерес для лиц, связанных с кодированием и передачей информации и цифровой техникой, а также специалистов по прикладной математике, интересующихся компьютерной алгеброй. Предисловие Алгоритмы на эллиптических кривых Алгоритм сложения и удвоения точек
Общая схема алгоритма сложения
Частные формулы для сложения и удвоения
Алгоритмы сложения и удвоения точек эллиптических кривых
Эллиптические кривые над GF (2n)
Суперсингулярные кривые
Несуперсингулярные кривые
Стандарты о выборе кривых для реализации криптосистем на эллиптических кривых
Скалярное умножение на суперсингулярных кривых
Вычисление k ⋅ P методом аддитивных цепочек
Использование проективных координат
Метод Монтгомери
Скалярное умножение на несуперсингулярных кривых
Метод Монтгомери для несуперсингулярных кривых
Метод Монтгомери в проективных координатах
Метод Лопеса—Дахаба использования проективных координат
Алгоритм скалярного умножения, использующий операцию «ополовинивания»
Скалярное умножение на аномальных кривых
Свойства кривых Коблица
Использование модулярной редукции
Вычисление дискретного логарифма
Проблема дискретного логарифмирования
Алгоритм «большой шаг — малый шаг»
Алгоритм для групп составных порядков Протоколы на эллиптических кривых Выбор точки и размещение данных
Введение
Решение квадратных уравнений
Выбор точки эллиптической кривой
Размещение данных на эллиптической кривой
Определение порядка точки эллиптической кривой и нахождение образующего элемента группы точек эллиптической кривой
Распределение ключей
Введение
Распределение ключей для классической криптосистемы (протокол Диффи—Хеллмана)
Распределение ключей для классической криптосистемы (протокол Месси—Омуры)
Протокол распределения ключей Менезеса—Кью—Венстоуна (MQV-протокол)
Криптосистемы Эль-Гамаля
Протоколы цифровой подписи
Электронная цифровая подпись
Обобщенная схема электронной подписи Эль-Гамаля
Электронная подпись Эль-Гамаля с возвратом сообщения — схема Nyberg—Rueppel
Передача с забыванием
Введение
Схема некоторых протоколов передачи с забыванием
Некоторые частные случаи передачи с забыванием
Передача комбинации k из n сообщений с забыванием
Применение передачи k из n сообщений с забыванием Криптосистемы на основе спариваний Билинейная проблема Диффи—Хеллмана
Однораундовый протокол генерации общего секретного ключа между тремя участниками
Короткая цифровая подпись, основанная на спаривании
Криптосистема с публичным индивидуальным ключом
Спаривание Андре Вейля на эллиптических кривых
Дивизоры
Явное определение спаривания Вейля
Функции на гиперэллиптических кривых
Алгоритм вычисления спариваний Вейля и Тейта
Усовершенствования алгоритма Миллера
Спаривание Тейта
Применение спариваний для логарифмирования в эллиптических кривых
Кривые, удобные для спаривания
Искажающее отображение
Удобные для спаривания кривые с множителем безопасности k ⩽ 2
Удобные для спаривания поля
Кривые над полями характеристики три
Устранение делений
О больших значениях параметра безопасности
Скалярное умножение точек кривой над полем большой характеристики
Ускорение алгоритма Миллера для больших k
Итерированное удвоение в якобиевых координатах
Комбинирование с другими методами
Использование аддитивных цепочек с двойной базой
Алгоритм Дуурсма—Ли
Алгоритм Дуурсма—Ли над полями характеристики два
Некоторые алгоритмы арифметики конечных полей
Извлечение квадратных корней в полях характеристики большей двух
Извлечение корней p-й степени в полях характеристики p
Один метод компактной записи точек суперсингулярных кривых
Арифметика в полях характеристики большей двух
О реализации алгоритма Дуурсма—Ли
Использование нормального базиса в поле G
Умножение в поле K методом Карацубы
Умножение в поле K методом Тоома
Возведение в степень p в поле K Приложения Алгоритмы с двоичными матрицами
Представление векторов и матрицы
Умножение матрицы на вектор
Алгоритм GAUS-MATRIX-TRIAN
Алгоритм проверки невырожденности матрицы
Приведение матрицы к диагональному виду
Обращение матрицы
Умножение вектор-строки на матрицу Таблицы неприводимых многочленов
Неприводимые многочлены над полем GF (2)
Неприводимые трехчлены степени n, 2 ⩽ n ⩽ 2000
Неприводимые трехчлены вида 1 + хn-1 + хn степени n, 2 ⩽ n ⩽ 34352
Неприводимые пятичлены степени n, 8 ⩽ n ⩽ 290
Неприводимые трехчлены над полем GF (3) Таблицы ОНБ
ОНБ размерности n, 2 ⩽ n ⩽ 30
ОНБ размерности n, 30 < n < 1013
Возможные размерности ОНБ n, 998 < n < 10000 Примеры исполнения MQV-протокола
Предназначено для студентов, преподавателей вузов и специалистов в области защиты информации, прикладной математики, вычислительной техники и информатики. Издание представляет интерес для лиц, связанных с кодированием и передачей информации и цифровой техникой, а также специалистов по прикладной математике, интересующихся компьютерной алгеброй. Предисловие Алгоритмы на эллиптических кривых Алгоритм сложения и удвоения точек
Общая схема алгоритма сложения
Частные формулы для сложения и удвоения
Алгоритмы сложения и удвоения точек эллиптических кривых
Эллиптические кривые над GF (2n)
Суперсингулярные кривые
Несуперсингулярные кривые
Стандарты о выборе кривых для реализации криптосистем на эллиптических кривых
Скалярное умножение на суперсингулярных кривых
Вычисление k ⋅ P методом аддитивных цепочек
Использование проективных координат
Метод Монтгомери
Скалярное умножение на несуперсингулярных кривых
Метод Монтгомери для несуперсингулярных кривых
Метод Монтгомери в проективных координатах
Метод Лопеса—Дахаба использования проективных координат
Алгоритм скалярного умножения, использующий операцию «ополовинивания»
Скалярное умножение на аномальных кривых
Свойства кривых Коблица
Использование модулярной редукции
Вычисление дискретного логарифма
Проблема дискретного логарифмирования
Алгоритм «большой шаг — малый шаг»
Алгоритм для групп составных порядков Протоколы на эллиптических кривых Выбор точки и размещение данных
Введение
Решение квадратных уравнений
Выбор точки эллиптической кривой
Размещение данных на эллиптической кривой
Определение порядка точки эллиптической кривой и нахождение образующего элемента группы точек эллиптической кривой
Распределение ключей
Введение
Распределение ключей для классической криптосистемы (протокол Диффи—Хеллмана)
Распределение ключей для классической криптосистемы (протокол Месси—Омуры)
Протокол распределения ключей Менезеса—Кью—Венстоуна (MQV-протокол)
Криптосистемы Эль-Гамаля
Протоколы цифровой подписи
Электронная цифровая подпись
Обобщенная схема электронной подписи Эль-Гамаля
Электронная подпись Эль-Гамаля с возвратом сообщения — схема Nyberg—Rueppel
Передача с забыванием
Введение
Схема некоторых протоколов передачи с забыванием
Некоторые частные случаи передачи с забыванием
Передача комбинации k из n сообщений с забыванием
Применение передачи k из n сообщений с забыванием Криптосистемы на основе спариваний Билинейная проблема Диффи—Хеллмана
Однораундовый протокол генерации общего секретного ключа между тремя участниками
Короткая цифровая подпись, основанная на спаривании
Криптосистема с публичным индивидуальным ключом
Спаривание Андре Вейля на эллиптических кривых
Дивизоры
Явное определение спаривания Вейля
Функции на гиперэллиптических кривых
Алгоритм вычисления спариваний Вейля и Тейта
Усовершенствования алгоритма Миллера
Спаривание Тейта
Применение спариваний для логарифмирования в эллиптических кривых
Кривые, удобные для спаривания
Искажающее отображение
Удобные для спаривания кривые с множителем безопасности k ⩽ 2
Удобные для спаривания поля
Кривые над полями характеристики три
Устранение делений
О больших значениях параметра безопасности
Скалярное умножение точек кривой над полем большой характеристики
Ускорение алгоритма Миллера для больших k
Итерированное удвоение в якобиевых координатах
Комбинирование с другими методами
Использование аддитивных цепочек с двойной базой
Алгоритм Дуурсма—Ли
Алгоритм Дуурсма—Ли над полями характеристики два
Некоторые алгоритмы арифметики конечных полей
Извлечение квадратных корней в полях характеристики большей двух
Извлечение корней p-й степени в полях характеристики p
Один метод компактной записи точек суперсингулярных кривых
Арифметика в полях характеристики большей двух
О реализации алгоритма Дуурсма—Ли
Использование нормального базиса в поле G
Умножение в поле K методом Карацубы
Умножение в поле K методом Тоома
Возведение в степень p в поле K Приложения Алгоритмы с двоичными матрицами
Представление векторов и матрицы
Умножение матрицы на вектор
Алгоритм GAUS-MATRIX-TRIAN
Алгоритм проверки невырожденности матрицы
Приведение матрицы к диагональному виду
Обращение матрицы
Умножение вектор-строки на матрицу Таблицы неприводимых многочленов
Неприводимые многочлены над полем GF (2)
Неприводимые трехчлены степени n, 2 ⩽ n ⩽ 2000
Неприводимые трехчлены вида 1 + хn-1 + хn степени n, 2 ⩽ n ⩽ 34352
Неприводимые пятичлены степени n, 8 ⩽ n ⩽ 290
Неприводимые трехчлены над полем GF (3) Таблицы ОНБ
ОНБ размерности n, 2 ⩽ n ⩽ 30
ОНБ размерности n, 30 < n < 1013
Возможные размерности ОНБ n, 998 < n < 10000 Примеры исполнения MQV-протокола