Криптография на основе эллиптических кривых - это популярная форма шифрования с открытым ключом, основанная на математической теории эллиптических кривых . Точки на эллиптической кривой могут быть добавлены и образованы группой с помощью этой операции сложения. В этой статье описываются вычислительные затраты на добавление этой группы и некоторые связанные операции, которые используются в алгоритмах криптографии с эллиптическими кривыми.
Сокращения для операций
В следующем разделе представлена таблица всех временных затрат на некоторые из возможных операций с эллиптическими кривыми. Столбцы таблицы помечены различными вычислительными операциями. Строки таблицы относятся к разным моделям эллиптических кривых. Рассматриваются следующие операции:
DBL - удвоение
ADD - добавление
mADD - Смешанное сложение: добавление входа, масштабированного до координаты Z 1.
mDBL - Смешанное удвоение: удвоение входа, масштабированного до координаты Z 1.
TPL - Утроение.
DBL + ADD - комбинированный двойной и дополнительный шаг
Чтобы узнать, как определяются точки добавления (ADD) и удвоения (DBL) на эллиптических кривых, см . Групповой закон . Важность удвоения скорости умножения скейлера обсуждается после таблицы. Для получения информации о других возможных операциях с эллиптическими кривыми см. Http://hyperelliptic.org/EFD/g1p/index.html .
Табулирование
При различных предположениях об умножении, сложении, инверсии элементов в некотором фиксированном поле временные затраты на эти операции варьируются. В этой таблице предполагается, что:
- I = 100M, S = 1M, * param = 0M, add = 0M, * const = 0M
Это означает, что требуется 100 умножений (M), чтобы инвертировать (I) элемент; одно умножение требуется для вычисления квадрата (S) элемента; умножение не требуется для умножения элемента на параметр (* param), на константу (* const) или для добавления двух элементов.
Для получения дополнительной информации о других результатах, полученных при различных предположениях, см. Http://hyperelliptic.org/EFD/g1p/index.html.
Важность удвоения
В некоторых применениях эллиптической кривой криптографии и эллиптической кривой методом факторизации ( ECM ) необходимо рассмотреть скалярное произведение [ п ] P . Один из способов сделать это - последовательно вычислить:
Но это быстрее использовать метод двойного и добавления , например , [5] P = [2] ([2] P) + P . В общем, чтобы вычислить [ k ] P , напишите
с k i в {0,1} и, k l = 1, то:
.
Обратите внимание, что этот простой алгоритм занимает не более 2l шагов, и каждый шаг состоит из удвоения и (если k i ≠ 0) добавления двух точек. Итак, это одна из причин, по которой определены формулы сложения и удвоения. Кроме того, этот метод применим к любой группе, и если групповой закон записан мультипликативно, алгоритм двойного и сложения вместо этого называется алгоритмом квадратного и умножения .
Рекомендации
- ^ Fay, Бьёрн (2014-12-20). «Двойное и сложение с относительными координатами Якоби» . Архив криптологии ePrint .