Болотов А.А. и др. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых ОНЛАЙН

В связи с этим описаны алгоритмы спаривания Вейля и Тейта и их модификации. Изложение теории сопровождается большим числом примеров и упражнений.
Предназначено для студентов, преподавателей вузов и специалистов в области защиты информации, прикладной математики, вычислительной техники и информатики. Издание представляет интерес для лиц, связанных с кодированием и передачей информации и цифровой техникой, а также специалистов по прикладной математике, интересующихся компьютерной алгеброй.
Оглавление
Предисловие…………………………………………..7
Глава 1. Алгоритмы на эллиптических кривых…………………………….9
1.1. Алгоритм сложения и удвоения точек………………………..9
1.1.1. Общая схема алгоритма сложения……………………….9
1.1.2. Частные формулы для сложения и удвоения…………..11
1.1.3. Алгоритмы сложения и удвоения точек эллиптических
кривых………………………………………………………………17
1.2. Эллиптические кривые над GF(2n)………………………………….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. Выбор точки и размещение данных …………………………………76
2.1.1. Введение………….. ……………………………………76
2.1.2. Решение квадратных уравнений ………………………………….76
2.1.3. Выбор точки эллиптической кривой………………………………81
2.1.4. Размещение данных на эллиптической кривой………………….82
2.1.5. Определение порядка точки эллиптической кривой и нахождение образующего элемента группы точек эллиптической кривой…………………………..83
2.2. Распределение ключей……………………………83
2.2.1. Введение…………………………………………………………….83
2.2.2. Распределение ключей для классической криптосистемы (протокол Диффи—Хеллмана) ……………………………………85
2.2.3. Распределение ключей для классической криптосистемы (протокол Месси—Омуры)…………………………………………86
2.2.4. Протокол распределения ключей Менезеса—Кью—Венстоуна (MQV-протокол)……………………………………………………90
2.3. Криптосистемы Эль-Гамаля…………………………………………..93
2.4. Протоколы цифровой подписи……………………………………….96
2.4.1. Электронная цифровая подпись………………………………….96
2.4.2. Обобщенная схема электронной подписи Эль-Гамаля…………..98
2.4.3. Электронная подпись Эль-Гамаля с возвратом сообщения —
схема Nyberg—Rueppel……………………..102
2.5. Передача с забыванием……………………….105
2.5.1. Введение……………………………..105
2.5.2. Схема некоторых протоколов передачи с забыванием…….106
2.5.3. Некоторые частные случаи передачи с забыванием………109
2.5.4. Передача комбинации к из п сообщений с забыванием……112
2.5.5. Применение передачи к из п сообщений с забыванием……115
Глава 3. Криптосистемы на основе спариваний…………….120
3.1. Билинейная проблема Диффи—Хеллмана…………….120
3.1.1. Однораундовый протокол генерации общего секретного
ключа между тремя участниками………………..122
3.1.2. Короткая цифровая подпись, основанная на спаривании…..122
3.1.3. Криптосистема с публичным индивидуальным ключом ……123
3.2. Спаривание Андре Вейля на эллиптических кривых………124
3.2.1. Дивизоры…………………………….125
3.2.2. Явное определение спаривания Вейля . …………….128
3.2.3. Функции на гиперэллиптических кривых……………130
3.3. Алгоритм вычисления спариваний Вейля и Тейта ……….136
3.3.1. Усовершенствования алгоритма Миллера……………139
3.4. Спаривание Тейта…………………………..143
3.4.1. Применение спариваний для логарифмирования
в эллиптических кривых…………………….145
3.4.2. Кривые, удобные для спаривания ……………….146
3.4.3. Искажающее отображение……………………148
3.4.4. Удобные для спаривания кривые с множителем безопасности
к < 2.....................................152
3.4.5. Удобные для спаривания поля......... . ............153
3.5. Кривые над полями характеристики три................. 154
3.5.1. Устранение делений............................155
3.6. О больших значениях параметра безопасности............160
3.6.1. Скалярное умножение точек кривой над полем большой характеристики........ 162
3.6.2. Ускорение алгоритма Миллера для больших к............163
3.6.3. Итерированное удвоение в якобиевых координатах............164
3.6.4. Комбинирование с другими методами....................164
3.6.5. Использование аддитивных цепочек с двойной базой . ......166
3.7. Алгоритм Дуурсма—Ли............................168
3.7.1. Алгоритм Дуурсма—Ли над полями характеристики два......174
3.8. Некоторые алгоритмы арифметики конечных полей ........176
3.8.1. Извлечение квадратных корней в полях характеристики
большей двух................................176
3.8.2. Извлечение корней р-й степени в полях характеристики р ... . 177
3.8.3. Один метод компактной записи точек суперсингулярных
кривых....................................180
3.8.4. Арифметика в полях характеристики большей двух.........182
3.9. О реализации алгоритма Дуурсма—Ли..................188
3.9.1. Использование нормального базиса в поле G............189
3.9.2. Умножение в поле К методом Карацубы...............190
3.9.3. Умножение в поле К методом Тоома.................191
3.9.4. Возведение в степень р в поле К ...................192
Приложение А. Алгоритмы с двоичными матрицами.............196
А.1. Представление векторов и матрицы ...................196
А.2. Умножение матрицы на вектор.......................197
А.З. Алгоритм GAUS-MATRIX-TRIAN ....................199
А.4. Алгоритм проверки невырожденности матрицы...........201
А. 5. Приведение матрицы к диагональному виду..............202
А.6. Обращение матрицы..............................204
A.7. Умножение вектор-строки на матрицу..................206
Приложение В. Таблицы неприводимых многочленов............208
B.1. Неприводимые многочлены над полем GF(2) ............208
В.1.1. Неприводимые трехчлены степени n, 2



Читать онлайн
скачать бесплатно


Теги:
Болотов криптография, эллиптическая криптография

Коментарі до Болотов А.А. и др. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых ОНЛАЙН