Таблица затрат операций на эллиптических кривых

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

Сокращения для операций

В следующем разделе представлена ​​таблица всех временных затрат некоторых возможных операций с эллиптическими кривыми. Столбцы таблицы помечены различными вычислительными операциями. Строки таблицы относятся к различным моделям эллиптических кривых. Рассматриваются следующие операции:

Двухместный номер - удвоение
ДОБАВИТЬ - Дополнение
mADD — смешанное сложение: добавление входного сигнала, масштабированного до координаты Z 1.
mDBL — Смешанное удвоение: удвоение входного сигнала, который был масштабирован до координаты Z 1.
ОСАГО – тройное.
DBL+ADD — комбинированный двойной и дополнительный шаг.

Чтобы узнать, как определяются точки добавления (ADD) и удвоения (DBL) на эллиптических кривых, см. Групповой закон . Важность удвоения для увеличения скорости умножения обсуждается после таблицы. Информацию о других возможных операциях с эллиптическими кривыми см. на http://hyperelliptic.org/EFD/g1p/index.html .

Табуляция

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

I = 100M, S = 1M, *param = 0M, add = 0M, *const = 0M

Это означает, что для инвертирования (I) элемента требуется 100 умножений (M); для вычисления квадрата (S) элемента требуется одно умножение; для умножения элемента на параметр (*param), на константу (*const) или для сложения двух элементов умножение не требуется.

Дополнительную информацию о других результатах, полученных при различных предположениях, см. на http://hyperelliptic.org/EFD/g1p/index.html.

Форма кривой, представление	двухместный номер	ДОБАВЛЯТЬ	Мэдд	мДВБЛ	ВГЗ	Двухместный+ДОБАВИТЬ
Короткая проекция Вейерштрасса	11	14	11	8
Короткая проектива Вейерштрасса с a4=-1.	11	14	11	8
Короткая проектива Вейерштрасса с a4=-3.	10	14	11	8
Короткий относительный якобиан Вейерштрасса	10	11	(7)	(7)		18
Тройная ориентированная кривая Доша – Икарта – Коэля	9	17	11	6	12
Расширенная кривая Гессе	9	12	11	9
Проективная кривая Гессе	8	12	10	6	14
Квартика Якоби XYZ	8	13	11	5
Якоби четвертой степени удвоения, ориентированной на XYZ	8	13	11	5
Проективная скрученная кривая Гессе	8	12	12	8	14
Кривая Доша – Икарта – Коэля, ориентированная на удвоение	7	17	12	6
Проективное пересечение Якоби	7	14	12	6	14
Перекресток Якоби продлен	7	12	11	7	16
Проекция Twisted Edwards	7	11	10	6
Витой Эдвардс в перевернутом виде	7	10	9	6
Twisted Edwards расширенный	8	9	8	7
Проективный Эдвардс	7	11	9	6	13
Якоби четвертой степени удвоения, ориентированной на XXYZZ	7	11	9	6	14
Квартика Якоби XXYZZ	7	11	9	6	14
Квартика Якоби XXYZZR	7	10	9	7	15
Кривая Эдвардса перевернутая	7	10	9	6
Кривая Монтгомери	4			3

Важность удвоения

В некоторых приложениях криптографии эллиптических кривых и метода факторизации эллиптических кривых ( ECM ) необходимо учитывать скалярное умножение [ n ] P . Один из способов сделать это — последовательно вычислить:

$P,\quad [2]P=P+P,\quad [3]P=[2]P+P,\dots ,[n]P=[n-1]P+P$

Но быстрее использовать метод двойного сложения , например, [5] P = [2]([2]P) + P . В общем, чтобы вычислить [ k ] P , напишите

$k=\sum _{i\leq l}k_{i}2^{i}$

с k _i в {0,1} и $l=[log_{2}k]$, k _l = 1, тогда:

$[2](....([2]([2]([2]([2]([2]P+[k_{(l-1)}]P)+[k_{(l-2)}]P)+[k_{(l-3)}]P)+\dots )\dots +[k_{1}]P)+[k_{0}]P=[2^{l}]P+[k_{(l-1)}2^{l-1}]P+\dots +[k_{1}2]P+[k_{0}]P$.

Обратите внимание, что этот простой алгоритм занимает не более 2l шагов, и каждый шаг состоит из удвоения и (если k _i ≠ 0) добавления двух точек. Итак, это одна из причин, по которой определены формулы сложения и удвоения. Более того, этот метод применим к любой группе, и если групповой закон записан мультипликативно, алгоритм двойного сложения вместо этого называется алгоритмом квадрата и умножения .

Ссылки

• http://hyperelliptic.org/EFD/g1p/index.html