Русская Википедия:Кривые Эдвардса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Edward-curves.svg

Кривые Эдвардса уравнения x² + y² = 1 − d ·x²·y² над полем действительных чисел с параметрами d = 300 (красный), d = √8 (желтый) и d = −0.9 (синий)

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

Определение

Оригинальной кривой Эдвардса над полем K, не имеющим характеристики 2, называется уравнение вида

<math>x^2 + y^2 = c^2(1 + x^2y^2)</math>

для некоторого скаляра <math>c \in K \setminus \{0,1\}</math>. Однако над конечным полем существует лишь несколько кривых, которые могут быть выражены в такой форме.

Поэтому Даниэлем Бернстайнем и Тани Ланге была предложена модификация кривой Эдвардса с ведением параметра d, не являющимся квадратичным вычетов в поле <math>K</math>:

<math>x^2 + y^2 = c^2(1+dx^2y^2) </math>, <math>d(1 - d c^4) \neq 0 </math>, <math>\left(\frac{d}{p}\right) = -1</math>, где <math>\left( \frac{d}{p} \right)</math>— символ Лежандра, <math>c ,d \in K</math>, <math>p \neq 2</math> — характеристика поля,

Эта модификация и называется эллиптической кривой в форме Эдвардса, или проще кривой Эдвардса.

Кривая Эдвардса изоморфна (бирационально эквивалентна) эллиптической кривой в форме Монтгомери и, следовательно, допускает наличие алгебраической группы при выборе нейтрального элемента. Если поле K конечно, то значительная часть эллиптических кривых над эти полем может быть записана в форме Эдвардса.

Подстановкой <math>\frac{x}{c} \rightarrow x , \frac{y}{c} \rightarrow y</math> в исходное уравнение кривой Эдвардса можно получить изоморфную кривую в форме Эдвардса вида:

<math>x^2 + y^2 = 1 + d'x^2y^2, d'=dc^4</math>

Выбор параметра с = 1 не умаляет общности, поэтому далее при рассмотрении кривых Эдвардса параметр с предполагается равным единице.

Групповой закон

(См. также групповой закон эллиптической кривой в форме Вейерштрасса)

Любая кривая Эдвардса вида <math>x^2 + y^2 = 1 + dx^2y^2 , d \neq 1</math> над полем K с характеристикой <math>p \neq 2</math> изоморфна эллиптической кривой в форме Монтгомери над тем же полем:

<math>(1/e)v^2 = u^3 + (4/e - 2)u^2 + u</math>, где <math>e=1-d, u=\frac{1+y}{1-y}, v=\frac{2(1+y)}{x(1-y)}</math> и точка <math>P = (0,1)</math> является нейтральным элементом. Такая изоморфная замена позволяет породить группу на любой кривой Эдвардса.

Закон сложения для кривых Эдвардса

Для любой эллиптической кривой сумма двух точек представляется рациональным выражением от координат этих точек, хотя в общем случае могут понадобиться несколько дополнительных формул для покрытия всех частных случаев. Для кривых Эдвардса, беря в качестве нейтрального элемента точку (0, 1), сумма точек <math>(x_1,y_1)</math> и <math>(x_2,y_2)</math> представляется формулой:

<math> (x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 - x_1 x_2}{1 - dx_1 x_2 y_1 y_2} \right) \, </math>

Шаблон:Начало скрытого блока Утверждение

Пусть <math>P = (x, y)</math> и <math>Q = (u, v)</math> -- точки кривой Эдвардса и выполняются равентсва <math> x^2 + y^2 = c^2(1 + dx^2y^), u^2 + v^2 = c^2(1 + du^2v^2)</math>. Пусть <math>X = \frac{xv+yu}{c(1+dxyuv)}, Y = \frac{yv - xu}{c(1-dxyuv)}</math>. Тогда <math>X^2 + Y^2 = c^2(1+dX^2Y^2)</math>.

Доказательство

Не умаляя общности примем <math>c = 1</math> (иначе замена переменных <math> \frac{x}{c} \rightarrow x, \frac{y}{c} \rightarrow y </math>)

Рассмотрим полином <math> T = (xv + yu)^2(1 - dxuyv)^2 + (yv - xu)^2(1 + dxuyv)^2 - d(xv + yu)^2(yv - xu)^2 </math>, который после раскрытия скобок и приведений соответствующих слагаемых принимает следующий вид: <math>T = (x^2 + y^2 - (u^2 + v^2)dx^2y^2)(u^2 + v^2 - (x^2 + y^2)du^2v^2)</math>. Из определения точек кривой в общем случае имеем:

<math>x^2 + y^2 = c^2(1 + dx^2y^), u^2 + v^2 = c^2(1 + du^2v^2)</math>.

Умножая второе равенство на <math>-dx^2y^2</math> и вычитая результат из первого, получаем: <math>x^2 + y^2 - (u^2 + v^2)dx^2y^2 = 1 - d^2x^2y^2u^2v^2</math> Аналогично, <math>u^2 + v^2 - (x^2 + y^2)du^2v^2 = 1 - d^2x^2y^2u^2v^2</math> Отсюда получаем <math>T = (1 - d^2x^2y^2u^2v^2)^2</math>

Согласно условию точка <math>(X, Y)</math> выражается через <math>x, y, u, v</math>. Это позволяет нам получить следующее равенство: <math> \begin{align} X^2 + Y^2 - dX^2Y^2 & = \frac{(xv + yu)^2}{(1 + dxyuv)^2} + \frac{(yv - xu)^2}{(1 - dxyuv)^2} - \frac{d(xv + yu)^2(yv - xu)^2}{(1 + dxyuv)^2(1 - dxyuv)^2}\\ & = \frac{T}{(1 + dxyuv)^2(1 - dxyuv)^2}\\ & = \frac{T}{1 - d^2x^2y^2u^2v^2} = 1 \end{align} </math>.

Следовательно выполняется <math> X^2 + Y^2 = 1 + dX^2Y^2</math> Шаблон:Конец скрытого блока Обратная точка определяется как <math>-(x,y) = (-x,y)</math>. Любая Кривая Эдвардса имеет единственную точку 2-го порядка <math>(0,-1)</math> и ровно 2 точки 4-го порядка <math>(\plusmn1,0)</math> с координатами в поле K.

Если d не является квадратичным вычетом в K и <math> \{(x_1,y_1), (x_2,y_2)\} \in \{(x,y)|x^2+y^2=1+d x^2 y^2 \} </math>, тогда кривая не имеет особых точек: в знаменателе <math>1 + dx_{1}x_{2}y_{1}y_{2} \neq 0</math> и <math>1 - dx_{1}x_{2}y_{1}y_{2} \neq 0</math>. Это свойство принято называть полнотой закона сложения для кривых Эдвардса. Оно выполняется, когда d не является квадратичным вычетом в поле K. Другими словами, выражения для суммы двух точек справедливы для любых пар точек кривой Эдвардса над полем K.

Шаблон:Начало скрытого блока Утверждение

Для любых пар точек кривой Эдвардса знаменатели закона сложения не обращаются в нуль: <math>dx_1y_1x_2y_1 \neq \plusmn 1</math>

Доказательство

Пусть точки <math>(x_1, y_1), (x_2, y_2)</math> принадлежат одной кривой <math>x^2 + y^2 = 1 + dx^2y^2</math> и пусть <math>\theta = dx_1y_1x_2y_2</math>.

От противного: пусть <math>\theta \in \{-1, 1\}</math>(Возьмем равной 1). Тогда <math>x_1y_1 = \frac{1}{dx_2y_2}</math> и <math>x_1^2 + y_1^2 = 1 + \frac{1}{dx_2^2y_2^2} = \frac{x_2^2 + y_2^2}{dx_2^2y_2^2}</math>.

<math> \begin{align} (x_1 + y_1)^2 = x_1^2 + y_1^2 + 2x_1y_1 & = \frac{x_2^2 + y_2^2}{dx_2^2y_2^2} + \frac{2}{dx_2y_2}\\ & = \frac{x_2^2 + y_2^2 + 2x_2y_2}{dx_2^2y_2^2}\\ & = \frac{(x_2 + y_2)^2}{dx_2^2y_2^2} \end{align} </math>.

Аналогично, <math>(x_1 - y_1)^2 = x_1^2 + y_1^2 - 2x_1y_1 = \frac{x_2^2 + y_2^2 - 2x_2y_2}{dx_2^2y_2^2} = \frac{(x_2 - y_2)^2}{dx_2^2y_2^2}</math>.

Так как <math>d</math> не является квадратичным вычетом, то оба равенства выполняются лишь тогда, когда одновременно <math>x_1 + y_1 = 0</math> и <math>x_1 - y_1 = 0</math>. Следовательно, <math>x_1 = y_1</math>, но кривая Эдвардса не содержит такой точки. Противоречие.

Аналогичным образом и для случая, когда <math>\theta = -1</math>:

<math>(x_1 + y_1)^2 = x_1^2 + y_1^2 + 2x_1y_1 = \frac{x_2^2 + y_2^2 - 2x_2y_2}{dx_2^2y_2^2} = \frac{(x_2 - y_2)^2}{dx_2^2y_2^2}</math>.

<math>(x_1 - y_1)^2 = x_1^2 + y_1^2 - 2x_1y_1 = \frac{x_2^2 + y_2^2 + 2x_2y_2}{dx_2^2y_2^2} = \frac{(x_2 + y_2)^2}{dx_2^2y_2^2}</math>.

Вывод аналогичен. Шаблон:Конец скрытого блока Если d является квадратичным вычетом в K, то существуют особые точки, то есть может быть пара точек <math> (x_1,y_1), (x_2,y_2) \in \{(x,y)|x^2+y^2=1+d x^2 y^2 \} </math> для которых один из знаменателей обращается в ноль: <math>1 + dx_{1}x_{2}y_{1}y_{2} = 0</math> или <math>1 - dx_{1}x_{2}y_{1}y_{2} = 0</math>.

Пример закона сложения:

Рассмотрим эллиптическую кривую в форме Эдвардса с параметром d = 2

<math>{\displaystyle}x^2 + y^2 = 1 + 2 x^2 y^2</math>

и точкой <math>P_1=(1,0)</math> на ней.

Покажем, что сумма <math>P_1</math> и нейтрального элемента <math>(0,1)</math> дает снова <math>P_1</math>. Действительно, используя выражения для закона сложения, получаем координаты точки суммы:

<math>x_3 = \frac{x_1 y_2 + y_1 x_2}{1 + 2x_1 x_2 y_1 y_2} = 1</math>

<math>y_3 = \frac{y_1 y_2 - x_1 x_2}{1 - 2x_1 x_2 y_1 y_2} = 0</math>

Геометрическая интерпретация

Файл:Геометрическая интерпретация закона сложения.svg

Сложение углов на единичной окружности

Для лучшего понимания можно рассмотреть геометрическую интерпретацию закона сложения:

Возьмем окружность радиуса 1:

<math>{\displaystyle}x^2+y^2=1</math>

и рассмотрим точки <math>P_1 = (x_1, y_1), P_2 = (x_2, y_2)</math>. Пусть <math>\alpha_1</math> и <math>\alpha_2 </math> углы такие, что:

<math>{\displaystyle}P_{1}=(x_{1},y_{1})=(\sin{\alpha_{1}},\cos{\alpha_{1}})</math>

<math>{\displaystyle}P_{2}=(x_{2},y_{2})=(\sin{\alpha_{2}},\cos{\alpha_{2}})</math>

Сумма <math>P_1</math> и <math>P_2</math> будет «суммой их углов». То есть точка<math>P_3 = P_1 + P_2</math> это точка <math>(x_3, y_3)</math> на круге такая, что:

<math>{\displaystyle}x_{3}=\sin({\alpha}_{1}+{\alpha}_{2})=\sin{\alpha}_{1}\cos{\alpha}_{2}+\sin{\alpha}_{2}\cos{\alpha}_{1}=x_{1}y_{2}+x_{2}y_{1}</math>

<math>{\displaystyle}y_{3}=\cos({\alpha}_{1}+{\alpha}_{2})=\cos{\alpha}_{1}\cos{\alpha}_{2}-\sin{\alpha}_{1}\sin{\alpha}_{2}=y_{1}y_{2}-x_{1}x_{2}.</math>

Таким образом, формула сложения для точек на окружности радиуса 1:

<math>{\displaystyle}(x_1,y_1)+(x_2,y_2) = (x_1y_2+x_2y_1,y_1y_2-x_1x_2)</math>.

Файл:Sum of two points on an Edwards curve.svg

Сумма двух точек на кривой Эдвардса с d = −30

Закон сложения на кривых Эдвардса

Точки на эллиптической кривой образуют абелеву группу: их можно складывать и умножать на целое число. Если эллиптическая кривая описывается несингулярным кубическим уравнением, то сумма двух точек <math>P</math> и <math>Q</math>, обозначаемая <math>P+Q</math>, тесно связана с третьей точкой, являющейся точкой пересечения эллиптической кривой и прямой, проходящей через <math>P</math> и <math>Q</math>.

Изоморфное отображение между кривой Эдвардса и соответствующей эллиптической кривой отображает прямые линии в конические сечения <math>Axy + Bx + Cy + D = 0</math>. Другими словами, для кривой Эдвардса три точки <math>P</math>, <math>Q</math> и <math>-(P+Q)</math> лежат на гиперболе.

Для двух различных точек <math>P_1=(x_1,y_1), P_2=(x_2,y_2), P_1 \ne P_2</math>, коэффициенты квадратичной формы:

<math> A = (x_1 - x_2) + (x_{1}y_{2} - x_{2}y_{1})</math>,

<math> B = (x_{2}y_{2} - x_{1}y_{1}) + y_{1}y_{2}(x_{2} - x_{1})</math>,

<math> C = x_{1}x_{2}(y_{1} - y_{2}), </math>

<math> D = C </math>

В случае удвоения точки <math>P=(x,y)</math> обратный элемент <math>-2P</math> лежит на конусе, который касается кривой в точке <math>P</math>. Коэффициенты квадратичной формы, определяющей конус:

<math> A = dx^2y - 1</math>,

<math> B = y - x^2</math>,

<math> C = x(1 - y),</math>

<math> D = C </math>

Проективные однородные координаты

(См. также проективные однородные координаты)

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

Проективные координаты позволяют избежать 2-х инверсий в законе сложения. Ввод третьей переменней дает возможность заменить операцию инверсии другими операциями. Введем третью координату <math>Z</math> как общий знаменатель в законе сложения. Обозначим <math>x = \frac{X}{Z}, y = \frac{Y}{Z}</math>, тогда исходное уравнение кривой Эдвардса примет вид:

<math>(X^2+Y^2)Z^2 = Z^4+dX^2Y^2</math>

Нейтральный элемент в проективных координатах: <math>(0 : 1 : 1)</math>

Нахождение обратной точки <math>-(X : Y : Z) = (-X : Y : Z)</math>

В проективных координатах <math>(X : Y : Z)</math> сумма двух точек записывается как <math>(X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_2) = (X_3 : Y_3 : Z_3)</math>. С учетом подстановок получается:

<math> \begin{align} y_3 = \frac{Y_3}{Z_3} & = \frac{(\frac{X_1Y_2}{Z_1Z_2} + \frac{X_2Y_1}{Z_1Z_2})(1 - d\frac{X_1X_2Y_1Y_2}{Z_1^2Z_2^2})}{(1 + d\frac{X_1X_2Y_1Y_2}{Z_1^2Z_2^2})(1 - d\frac{X_1X_2Y_1Y_2}{Z_1^2Z_2^2})))} \\ & = \frac{Z_1Z_2(Z_1^2Z_2^2 - dX_1X_2Y_1Y_2)(X_1Y_2 + X_2Y_1)}{(Z_1^2Z_2^2 + dX_1X_2Y_1Y_2)(Z_1^2Z_2^2 - dX_1X_2Y_1Y_2)}\\

x_3 = \frac{X_3}{Z_3} & = \frac{X_3}{Z_3} = \frac{Z_1Z_2(Z_1^2Z_2^2 + dX_1X_2Y_1Y_2)(X_1X_2 - Y_1Y_2)}{(Z_1^2Z_2^2 + dX_1X_2Y_1Y_2)(Z_1^2Z_2^2 - dX_1X_2Y_1Y_2)} \end{align} </math>

Обозначим:

<math> \begin{align} &A = Z_1Z_2;\\ &B = A^2;\\ &C = X_1X_2;\\ &D = Y_1Y_2;\\ &E = dCD;\\ &F = B - E;\\ &G = B + E \end{align}</math>

Тогда

<math>\begin{align} & Y_3 = A \cdot F \cdot ((X_1 + Y_1) \cdot (X_2 + Y_2) - C - D)\\ & X_3 = A \cdot G \cdot (D - C)\\ & Z_3 = F \cdot G\\ \end{align}</math>

Всего получается 10 умножений в поле, одно возведение в квадрат и одно умножение на параметр кривой <math>d</math>, не считая простые операции сложения (вычитания).

Закон удвоения

Удвоение может быть произведено с помощью тех же выражений, что и для закона сложения. Удвоение является частным случаем сложения двух одинаковых точек

Файл:Double Point on Edwards Curve.svg

Удвоение точки на кривой Эдвардса с d = −30

<math>(x_1, y_1), (x_2, y_2); x_1 = x_2, y_1 = y_2</math>

Удвоение точки <math>P=(x,y)</math>:

<math> \begin{align} (x,y)+(x,y) & = \left( \frac{2xy}{1+dx^2y^2}, \frac{y^2-x^2}{1-dx^2y^2} \right) \\[6pt] & = \left( \frac{2xy}{x^2+y^2}, \frac{y^2-x^2}{2-x^2-y^2} \right) \end{align} </math>

Знаменатели были упрощены согласно уравнению кривой <math>x^2 + y^2 = 1 + dx^2y^2</math>. Дальнейшая оптимизация достигается путем подсчета <math>2xy</math> как <math>(x + y)^2 - x^2 - y^2</math>. Это сокращает стоимость удвоения в гомоморфных координатах до 3M + 4S + 3C + 6a, в то время как обычное сложение стоит 10M + 1S + 1C + 1D + 7a. Здесь M — умножение в поле, S — возведение в квадрат в поле, D — стоимость умножение на параметр кривой d, a — сложение в поле.

В проективных координатах закон удвоения принимает вид:

<math>\begin{align} x_3 = \frac{X_3}{Z_3} & = \frac{2\frac{X}{Z}\frac{Y}{Z} \left(2 - \left( \frac{X}{Z} \right)^2 - \left( \frac{Y}{Z} \right)^2 \right)}{\left( 2 - \left( \frac{X}{Z} \right)^2 - \left( \frac{Y}{Z} \right)^2 \right) \left( \left(\frac{X}{Z} \right)^2 + \left( \frac{Y}{Z} \right)^2 \right)}\\ & = \frac{2XY(X^2 + Y^2)}{(2Z^2 - X^2 - Y^2)(X^2 + Y^2)}\\ y_3 = \frac{Y_3}{Z_3} &= \frac{\left( \left(\frac{X}{Z} \right)^2 - \left( \frac{Y}{Z} \right)^2 \right) \left( \left(\frac{X}{Z} \right)^2 + \left( \frac{Y}{Z} \right)^2 \right)}{\left( 2 - \left( \frac{X}{Z} \right)^2 - \left( \frac{Y}{Z} \right)^2 \right) \left( \left(\frac{X}{Z} \right)^2 + \left( \frac{Y}{Z} \right)^2 \right)}\\ & = \frac{(X^2 - Y^2)(X^2 + Y^2)}{(2Z^2 - X^2 - Y^2)(X^2 + Y^2)}\\ \end{align}</math>

Обозначим:

<math>\begin{align} &A = X^2\\ &B = Y^2\\ &C = Z^2\\ &D = (A + B)\\ &E = (A - B)\\ &F = 2C - A - B\\ \end{align}</math>

Тогда

<math>\begin{align} & X_3 = 2X \cdot Y \cdot F\\ & Y_3 = D \cdot E\\ & Z_3 = D \cdot F\\ \end{align}</math>

Всего получается 3 возведения в квадрат и 4 умножения в поле.

Пример удвоения

Как и примере с законом сложения, рассмотри кривую Эдвардса с параметром d=2:

<math>x^2 + y^2 = 1 + 2 x^2 y^2</math>

и точку <math>P=(1,0)</math>. Координаты точки <math>P_2 = 2P_1</math>:

<math>x_2 = \frac{2xy}{x^2 + y^2} = 0</math>

<math>y_2 = \frac{y^2-x^2}{2 - (x^2 + y^2)} = -1</math>

Точка, полученная удвоением P, имеет координаты <math>P_2=(0,-1)</math>.

Применение

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

• EdDSA — схема цифровой подписи с использованием кривых Эдвардса
• ECDH — протокол Ди́ффи-Хе́ллмана на эллиптических кривых
• ECQMV — протокол распределения общего ключа
• ECIES — протокол направленного шифрования

См. также

• Twisted Edwards curve — скрученные кривые Эдвардса, альтернативная форма представления кривых.