Умножение точек эллиптической кривой - Elliptic curve point multiplication

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

Основы

Учитывая кривую, E, определенный по некоторому уравнению в конечном поле (например, E: $у 2 = Икс 3 + топор + б$ ) умножение точек определяется как повторное добавление точки вдоль этой кривой. Обозначим как $нП = п + п + п + \dots + п$ для некоторого скаляра (целого) п и точка $п = (Икс, у)$ что лежит на кривой, E. Этот тип кривой известен как кривая Вейерштрасса.

Безопасность современных ECC зависит от сложности определения п из $Q = нП$ учитывая известные значения Q и п если п большой (известный как задача дискретного логарифмирования эллиптической кривой по аналогии с другими криптографические системы ). Это связано с тем, что добавление двух точек на эллиптической кривой (или добавление одной точки к самой себе) дает третью точку на эллиптической кривой, положение которой не имеет непосредственной очевидной связи с местоположением первых двух, и повторение этого много раз более дает точку нП это может быть где угодно. Интуитивно это похоже на то, что если бы вы п на окружности, добавление 42,57 градуса к его углу может быть точкой "не слишком далеко" от п, но добавление 1000 или 1001 умножить на 42,57 градуса даст точку, которая может находиться где угодно на окружности. Возврат к этому процессу, т. Е. Учитывая Q = nP и п и определение п поэтому можно сделать только опробовав все возможные п- усилие, которое трудно поддается вычислению, если п большой.

Точечные операции

Операции с точками эллиптической кривой: сложение (показано на фасете 1), удвоение (фасеты 2 и 4) и отрицание (фасет 3).

Для точек эллиптической кривой обычно используются три операции: сложение, удвоение и отрицание.

Точка на бесконечность

Точка в бесконечности - это элемент идентичности арифметики эллиптических кривых. Добавление его к любой точке приводит к появлению этой другой точки, включая добавление точки на бесконечности к самой себе.

{ displaystyle { begin {align} { mathcal {O}} + { mathcal {O}} = { mathcal {O}} { mathcal {O}} + P = P end {выровнено} }}

Точка на бесконечности также записывается как $0$ .

Точечное отрицание

Отрицание точки находит такую точку, что добавление ее к самому себе приведет к точке на бесконечности ( ${ displaystyle { mathcal {O}}}$ ).

{ Displaystyle { begin {выровненный} P + (- P) = { mathcal {O}} конец {выровненный}}}

Для эллиптических кривых это точка с одинаковым Икс координировать, но отрицать у координата:

{ displaystyle { begin {align} (x, y) + (- (x, y)) & = { mathcal {O}} (x, y) + (x, -y) & = { mathcal {O}} (x, -y) & = - (x, y) end {выровнено}}}

Добавление точки

С двумя разными точками, п и Q, сложение определяется как отрицание точки, полученной в результате пересечения кривой, E, а прямая, определяемая точками п и Q, придавая смысл, р.

{ displaystyle { begin {align} P + Q & = R (x_ {p}, y_ {p}) + (x_ {q}, y_ {q}) & = (x_ {r}, y_ {r) }) end {выровнены}}}

.

Предполагая эллиптическую кривую, E, дан кем-то $у 2 = Икс 3 + топор + б$ , это можно рассчитать как:

{ displaystyle { begin {align} lambda & = { frac {y_ {q} -y_ {p}} {x_ {q} -x_ {p}}} x_ {r} & = lambda ^ {2} -x_ {p} -x_ {q} y_ {r} & = lambda (x_ {p} -x_ {r}) - y_ {p} конец {выровнено}}}

Эти уравнения верны, когда ни одна из точек не является бесконечно удаленной, ${ displaystyle { mathcal {O}}}$ . Это важно для Алгоритм проверки ECDSA где хеш-значение может быть нулевым.

Удвоение очков

Где точки п и Q совпадают (в тех же координатах), сложение аналогично, за исключением того, что нет четко определенной прямой, проходящей через п, поэтому операция замыкается в предельном случае, касательная к кривой, E, в п.

Рассчитывается, как указано выше, за исключением:

{ displaystyle lambda = { frac {3x_ {p} ^ {2} + a} {2y_ {p}}}}

куда а из определяющего уравнения кривой, E, над.

Умножение точек

Самый простой способ вычисления умножения точек - это повторное сложение. Однако это полностью экспоненциальный подход к вычислению умножения.

Двойное и сложное

Самый простой метод - это метод двойного сложения,^[1] похожий на умножить на квадрат в модульном возведении в степень. Алгоритм работает следующим образом:

Вычислить dP, начнем с двоичного представления для d: ${ displaystyle d = d_ {0} + 2d_ {1} + 2 ^ {2} d_ {2} + cdots + 2 ^ {m} d_ {m}}$ , куда ${ displaystyle d_ {0} ~ .. ~ d_ {m} in {0,1 }, m = lfloor log _ {2} {d} rfloor}$ .Существует два возможных итерационных алгоритма.

Итерационный алгоритм, увеличение индекса:

  N ← P Q ← 0 для i от 0 до m делать, если d_я = 1, затем Q ← point_add (Q, N) N ← point_double (N) return Q

Итерационный алгоритм, уменьшение индекса:

  Q ← 0 для i от m до 0 do Q ← point_double (Q), если d_я = 1, затем Q ← point_add (Q, P) return Q

Альтернативный способ записать вышесказанное как рекурсивную функцию:

  f (P, d) is if d = 0 then return 0 # вычисление завершено else if d = 1 then return P else if d mod 2 = 1 then return point_add (P, f (P, d - 1)) # сложение, когда d нечетное else return f (point_double (P), d / 2) # удвоение при четном d

куда ж - функция умножения, п координата для умножения, d - количество раз, когда координата добавляется к самой себе. Пример: 100P можно записать как 2 (2 [P + 2 (2 [2 (P + 2P)])]) и, следовательно, требует операций с шестью точками двойного и двухточечного сложения. 100P будет равно f (P, 100).

Для этого алгоритма требуется журнал₂(d) итераций удвоения и сложения точек для вычисления полного умножения точек. Существует множество вариантов этого алгоритма, таких как использование окна, скользящего окна, NAF, NAF-w, векторных цепочек и лестницы Монтгомери.

Оконный метод

В оконной версии этого алгоритма^[1] выбирается размер окна ш и вычисляет все ${ displaystyle scriptstyle 2 ^ {w}}$ ценности ${ displaystyle scriptstyle dP}$ за ${ Displaystyle scriptstyle d ~ = ~ 0, , 1, , 2, , точки, , 2 ^ {w} , - , 1}$ . Теперь алгоритм использует представление ${ Displaystyle scriptstyle d ~ = ~ d_ {0} , + , 2 ^ {w} d_ {1} , + , 2 ^ {2w} d_ {2} , + , cdots , + , 2 ^ {mw} d_ {m}}$ и становится

  Q ← 0 для i от m до 0 do Q ← point_double_repeat (Q, w), если d_я > 0, то Q ← point_add (Q, d_яP) # используя предварительно вычисленное значение d_яP возврат Q

Этот алгоритм имеет ту же сложность, что и подход «двойное и сложение», но с преимуществом использования меньшего количества точек (что на практике медленнее, чем удвоение). Обычно значение ш выбрано достаточно маленьким, поэтому предварительное вычисление этап тривиального компонента алгоритма. Для кривых, рекомендованных NIST, ${ Displaystyle scriptstyle ш ~ = ~ 4}$ обычно лучший выбор. Вся сложность для п-битовое число измеряется как ${ Displaystyle scriptstyle п , + , 1}$ удвоение очков и ${ displaystyle scriptstyle 2 ^ {w} , - , 2 , + , { frac {n} {w}}}$ точечные дополнения.

Метод раздвижного окна

В версии с раздвижным окном мы стремимся обменять добавление очков на удвоение. Мы вычисляем ту же таблицу, что и в оконной версии, за исключением того, что мы вычисляем только точки ${ displaystyle scriptstyle dP}$ за ${ displaystyle scriptstyle d ~ = ~ 2 ^ {w-1}, , 2 ^ {w-1} , + , 1, , dots, , 2 ^ {w} , - , 1}$ . Фактически, мы только вычисляем значения, для которых установлен самый старший бит окна. Затем алгоритм использует исходное представление двойного и сложения ${ Displaystyle scriptstyle d ~ = ~ d_ {0} , + , 2d_ {1} , + , 2 ^ {2} d_ {2} , + , cdots , + , 2 ^ {m} d_ {m}}$ .

  Q ← 0 для i от m до 0 делать, если d_я = 0, то Q ← point_double (Q) else t ← извлечь j (до w - 1) дополнительных бит из d (включая d_я) i ← i - j, если j Преимущество этого алгоритма состоит в том, что этап предварительного вычисления примерно вдвое сложнее обычного оконного метода, а также торгует более медленным добавлением точек для удвоения. Фактически, нет особых причин использовать оконный метод вместо этого подхода, за исключением того, что первый может быть реализован в постоянное время. Алгоритм требует  ${ Displaystyle scriptstyle ш , - , 1 , + , n}$  поинт-дабл и самое большее  ${ displaystyle scriptstyle 2 ^ {w-1} , - , 1 , + , { frac {n} {w}}}$  точечные дополнения.
 $ш$ -арная несмежная форма ( $ш$ NAF) метод
в несмежная форма мы стремимся использовать тот факт, что вычитание точек так же просто, как и добавление точек, для выполнения меньшего количества (того и другого) по сравнению с методом скользящего окна. НАФ множимого  ${ displaystyle scriptstyle d}$  сначала необходимо вычислить по следующему алгоритму
   i ← 0 while (d> 0) do if (d mod 2) = 1 then d_я ← d моды 2^ш           г ← г - г_я       еще d_я = 0 d ← d / 2 i ← i + 1 return (d_я-1, d_i-2,…, D₀)
Где знаковая функция по модулю моды определяется как 
   если (d mod 2^ш) >= 2^{w − 1}       возврат (д мод 2^ш) − 2^ш   иначе вернуть d мод 2^ш
Это дает NAF, необходимый для выполнения умножения. Этот алгоритм требует предварительного вычисления точек  ${ Displaystyle scriptstyle lbrace 1, , 3, , 5, , точки, , 2 ^ {w-1} , - , 1 rbrace P}$  и их негативы, где  ${ displaystyle scriptstyle P}$  это точка, которую нужно приумножить. На типичных кривых Вейерштрасса, если  ${ Displaystyle scriptstyle P ~ = ~ lbrace x, , y rbrace}$  тогда  ${ Displaystyle scriptstyle -P ~ = ~ lbrace x, , - y rbrace}$ . Так что, по сути, негативы дешевы в вычислении. Затем следующий алгоритм вычисляет умножение  ${ displaystyle scriptstyle dP}$ :
   Q ← 0 для j ← i - 1 вниз до 0 do Q ← point_double (Q) if (d_j ! = 0) Q ← point_add (Q, d_jG) вернуть Q
WNAF гарантирует, что в среднем будет плотность  ${ displaystyle scriptstyle { frac {1} {ш , + , 1}}}$  точечные добавления (немного лучше, чем беззнаковое окно). Требуется удвоение 1 балла и  ${ Displaystyle scriptstyle 2 ^ {ш-2} , - , 1}$  точечные дополнения для предварительного расчета. Затем алгоритм требует  ${ displaystyle scriptstyle n}$  удвоения точек и  ${ Displaystyle scriptstyle { гидроразрыва {п} {ш , + , 1}}}$  точечные сложения для остальной части умножения.
Одним из свойств NAF является то, что мы гарантируем, что каждый ненулевой элемент  ${ displaystyle scriptstyle d_ {i}}$  следует как минимум  ${ Displaystyle scriptstyle ш , - , 1}$  дополнительные нули. Это потому, что алгоритм очищает нижнюю  ${ displaystyle scriptstyle w}$  кусочки  ${ displaystyle scriptstyle d}$  при каждом вычитании вывода моды функция. Это наблюдение можно использовать для нескольких целей. После каждого ненулевого элемента могут подразумеваться дополнительные нули, и их не нужно сохранять. Во-вторых, множественные порядковые деления на 2 можно заменить делением на  ${ displaystyle scriptstyle 2 ^ {w}}$  после каждого ненулевого  ${ displaystyle scriptstyle d_ {i}}$  элемент и делите на 2 после каждого нуля.
Было показано, что посредством применения атаки по побочному каналу FLUSH + RELOAD на OpenSSL, полный закрытый ключ может быть раскрыт после выполнения кэширования для всего лишь 200 выполненных подписей.^[2]
Лестница Монтгомери
Лестница Монтгомери^[3] Подход вычисляет умножение точки в фиксированный количество времени. Это может быть полезно, когда измерения времени или энергопотребления доступны злоумышленнику, выполняющему атака по побочным каналам. Алгоритм использует то же представление, что и при двойном сложении.
  р₀ ← 0 R₁ ← P для i от m до 0 делать, если d_я = 0, то R₁ ← point_add (R₀, Р₁)        Р₀ ← точка_двойная (R₀) иначе R₀ ← point_add (R₀, Р₁)        Р₁ ← точка_двойная (R₁) return R₀
Этот алгоритм в действительности имеет ту же скорость, что и подход двойного и сложения, за исключением того, что он вычисляет такое же количество точек сложения и удвоения независимо от значения множимого. d. Это означает, что на этом уровне алгоритм не пропускает никакой информации по таймингу или мощности. Однако было показано, что посредством применения атаки по побочному каналу FLUSH + RELOAD на OpenSSL полный закрытый ключ может быть раскрыт после выполнения кеширования. синхронизация только с одной подписью по очень низкой цене.^[4]
Рекомендации









^ ^а ^б Хэнкерсон, Даррел; Ванстон, Скотт; Менезес, Альфред (2004). Руководство по криптографии с эллиптическими кривыми. Springer Professional Computing. Нью-Йорк: Springer-Verlag. Дои:10.1007 / b9764891 (неактивно 18.11.2020). ISBN  0-387-95273-X.CS1 maint: DOI неактивен по состоянию на ноябрь 2020 г. (связь)
^ Бенгер, Наоми; ван де Поль, Йооп; Умный, Найджел П .; Яром, Юваль (2014). Батина, Лейла; Робшоу, Мэтью (ред.). "О, ах ... немного": небольшое количество побочного канала может иметь большое значение (PDF). Криптографическое оборудование и встроенные системы - CHES 2014. Конспект лекций по информатике. 8731. Springer. С. 72–95. Дои:10.1007/978-3-662-44709-3_5. ISBN  978-3-662-44708-6.
^ Монтгомери, Питер Л. (1987). "Ускорение методов факторизации Полларда и эллиптической кривой". Математика. Комп. 48 (177): 243–264. Дои:10.2307/2007888. JSTOR  2007888. МИСТЕР  0866113.
^ Яром, Юваль; Бенджер, Наоми (2014). «Восстановление одноразовых значений OpenSSL ECDSA с помощью атаки по побочному каналу кэша FLUSH + RELOAD». IACR Cryptology ePrint Archive.

[guide-1] а ^б Хэнкерсон, Даррел; Ванстон, Скотт; Менезес, Альфред (2004). Руководство по криптографии с эллиптическими кривыми. Springer Professional Computing. Нью-Йорк: Springer-Verlag. Дои:10.1007 / b9764891 (неактивно 18.11.2020). ISBN 0-387-95273-X.CS1 maint: DOI неактивен по состоянию на ноябрь 2020 г. (связь)

[2] Бенгер, Наоми; ван де Поль, Йооп; Умный, Найджел П .; Яром, Юваль (2014). Батина, Лейла; Робшоу, Мэтью (ред.). "О, ах ... немного": небольшое количество побочного канала может иметь большое значение (PDF). Криптографическое оборудование и встроенные системы - CHES 2014. Конспект лекций по информатике. 8731. Springer. С. 72–95. Дои:10.1007/978-3-662-44709-3_5. ISBN 978-3-662-44708-6.

[3] Монтгомери, Питер Л. (1987). "Ускорение методов факторизации Полларда и эллиптической кривой". Математика. Комп. 48 (177): 243–264. Дои:10.2307/2007888. JSTOR 2007888. МИСТЕР 0866113.

[4] Яром, Юваль; Бенджер, Наоми (2014). «Восстановление одноразовых значений OpenSSL ECDSA с помощью атаки по побочному каналу кэша FLUSH + RELOAD». IACR Cryptology ePrint Archive.

[1]

[2]

[3]

[4]