Умножение точек эллиптической кривой

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

Основы

Для данной кривой E , определенной по некоторому уравнению в конечном поле (например, E : $y 2 = x 3 + ax + b$ ), умножение точек определяется как повторное добавление точки вдоль этой кривой. Обозначим , как $Np = Р + Р + Р + ... P$ для некоторого скалярного (целое число) п и точку $Р = (х, у)$ , лежащей на кривой, Е . Этот тип кривой известен как кривая Вейерштрасса.

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

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

Операции с точками эллиптической кривой: сложение (показано на фасете 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}} \ конец {выровненный}}}

Для эллиптических кривых это точка с той же координатой x, но с отрицательной координатой y :

{\begin{aligned}(x,y)+(-(x,y))&={\mathcal {O}}\\(x,y)+(x,-y)&={\mathcal {O}}\\(x,-y)&=-(x,y)\end{aligned}}

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

С 2 -х различных точек, P и Q , сложение определяется как отрицание точки в результате пересечения кривой, Е , и прямой линией , определенной точками P и Q , что дает точку, R .

{\begin{aligned}P+Q&=R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}

.

Предполагая, что эллиптическая кривая E задана как $y 2 = x 3 + ax + b$ , это можно рассчитать как:

{\begin{aligned}\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}\\\end{aligned}}

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

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

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

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

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

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

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

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

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

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

Чтобы вычислить sP , начните с двоичного представления для s :, где . $s=s_{0}+2s_{1}+2^{2}s_{2}+\cdots +2^{m}s_{m}$ $s_{0}~..~s_{m}\in \{0,1\},m=\lfloor \log _{2}{s}\rfloor$

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

 let bits = bit_presentation (s) # вектор битов (от MSB к LSB), представляющий s let res = # указывает на бесконечность ${\begin{aligned}{\mathcal {O}}\end{aligned}}$  для бит в битах: res = res + res # двойной если бит == 1: res = res + P # добавить я = я - 1 вернуть res

Обратите внимание, что этот метод уязвим для временного анализа. См. Альтернативный подход к Лестнице Монтгомери ниже.

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

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

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

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

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

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

 Q ← 0 для я от м до 0 делать Q ← point_double_repeat (Q, w) если d _i > 0, то Q ← point_add (Q, d _i P) # с использованием предварительно вычисленного значения d _i P вернуть Q

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

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

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

 Q ← 0 для я от м до 0 делаю если d _i = 0, то Q ← точка_двойная (Q) еще t ← извлечь j (до w - 1) дополнительных бит из d (включая d _i ) я ← я - j если j <w, то Выполните двойное сложение с помощью t вернуть Q еще Q ← point_double_repeat (Q, w) Q ← point_add (Q, tP) вернуть Q

Преимущество этого алгоритма состоит в том, что этап предварительного вычисления примерно вдвое сложнее обычного оконного метода, а также торгует более медленными прибавлениями для удвоения пунктов. Фактически, нет особых причин использовать оконный метод вместо этого подхода, за исключением того, что первый может быть реализован в постоянное время. Алгоритм требует удвоения точек и в большинстве случаев добавления точек. $\scriptstyle w\,-\,1\,+\,n$ $\scriptstyle 2^{w-1}\,-\,1\,+\,{\frac {n}{w}}$

$w$ -aryметоднесмежной формы ( $w$ NAF)

В несмежной форме мы стремимся использовать тот факт, что вычитание точек так же просто, как и добавление точек, для выполнения меньшего количества (того и другого) по сравнению с методом скользящего окна. NAF множимого необходимо вычислить сначала по следующему алгоритму $\scriptstyle d$

 я ← 0 в то время как (d> 0) делать если (d mod 2) = 1, то d _i ← d моды 2 ^w d ← d - d _i еще d _я = 0 d ← d / 2 я ← я + 1 return (d _{i − 1} , d _i-2 ,…, d ₀ )

Где подписанные моды функций по модулю определяются как

 если (d mod 2 ^w )> = 2 ^{w − 1} return (d mod 2 ^w ) - 2 ^w еще возврат d mod 2 ^w

Это дает NAF, необходимый для выполнения умножения. Этот алгоритм требует предварительного вычисления точек и их отрицаний, где - точка, которая должна быть умножена. О типичных кривых Вейерштрасса, если тогда . Таким образом, по сути, негативы дешевы в вычислении. Затем следующий алгоритм вычисляет умножение : $\scriptstyle \lbrace 1,\,3,\,5,\,\dots ,\,2^{w-1}\,-\,1\rbrace P$ $\scriptstyle P$ $\scriptstyle P~=~\lbrace x,\,y\rbrace$ $\scriptstyle -P~=~\lbrace x,\,-y\rbrace$ $\scriptstyle dP$

 Q ← 0 для j ← i - 1 вниз до 0 делать Q ← точка_двойная (Q) если (d _j  ! = 0) Q ← point_add (Q, d _j G) вернуть Q

WNAF гарантирует, что в среднем будет плотность добавления точек (немного лучше, чем беззнаковое окно). Для предварительного вычисления требуется удвоение 1 балла и добавление баллов. Затем алгоритм требует удвоения точек и сложения точек для остальной части умножения. $\scriptstyle {\frac {1}{w\,+\,1}}$ $\scriptstyle 2^{w-2}\,-\,1$ $\scriptstyle n$ $\scriptstyle {\frac {n}{w\,+\,1}}$

Одним из свойств NAF является то, что мы гарантируем, что каждый ненулевой элемент сопровождается по крайней мере дополнительными нулями. Это связано с тем, что алгоритм очищает младшие биты при каждом вычитании вывода функции модов . Это наблюдение можно использовать для нескольких целей. После каждого ненулевого элемента могут подразумеваться дополнительные нули, и их не нужно сохранять. Во-вторых, несколько последовательных делений на 2 можно заменить делением на после каждого ненулевого элемента и делением на 2 после каждого нуля. $\scriptstyle d_{i}$ $\scriptstyle w\,-\,1$ $\scriptstyle w$ $\scriptstyle d$ $\scriptstyle 2^{w}$ $\scriptstyle d_{i}$

Было показано, что посредством применения атаки по побочному каналу FLUSH + RELOAD на OpenSSL, полный закрытый ключ может быть раскрыт после выполнения кэширования для всего лишь 200 выполненных подписей. ^[2]

Лестница Монтгомери

Лестничный подход Монтгомери ^[3] вычисляет умножение точек за фиксированный промежуток времени. Это может быть полезно, когда измерения времени или энергопотребления доступны злоумышленнику, выполняющему атаку по побочному каналу . Алгоритм использует то же представление, что и при двойном сложении.

 R ₀ ← 0 R ₁ ← P для я от м до 0 делаю если d _i = 0, то R ₁ ← point_add (R ₀ , R ₁ ) R ₀ ← point_double (R ₀ ) еще R ₀ ← point_add (R ₀ , R ₁ ) R ₁ ← точка_двойная (R ₁ ) возврат R ₀

Этот алгоритм фактически имеет ту же скорость, что и подход двойного и сложения, за исключением того, что он вычисляет такое же количество точек и удваивает независимо от значения множимого d . Это означает, что на этом уровне алгоритм не пропускает никакой информации по таймингу или мощности. Однако было показано, что посредством применения атаки по побочному каналу FLUSH + RELOAD на OpenSSL, полный закрытый ключ может быть раскрыт после выполнения кэширования только для одной подписи с очень низкими затратами. ^[4]

использованная литература

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

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

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

[3] Монтгомери, Питер Л. (1987). «Ускорение методов факторизации Полларда и эллиптических кривых» . Математика. Комп. 48 (177): 243–264. DOI : 10.2307 / 2007888 . JSTOR 2007888 . Руководство по ремонту 0866113 .

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

[1]