Кривая Эдвардса

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

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

Определение

Уравнение кривой Эдвардса над полем K , не имеющим характеристики 2, имеет следующий вид:

${\ displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2} \,}$

для некоторого скаляра . Также следующая форма с параметрами c и d называется кривой Эдвардса:${\ Displaystyle д \ в К \ setminus \ {0,1 \}}$

${\ displaystyle x ^ {2} + y ^ {2} = c ^ {2} (1 + dx ^ {2} y ^ {2}) \,}$

где c ,  d  ∈  K с cd (1 -  c ⁴ · d ) ≠ 0.

Каждая кривая Эдвардса бирационально эквивалентна эллиптической кривой в форме Вейерштрасса и, таким образом, допускает закон алгебраической группы, если выбрать точку, которая будет служить нейтральным элементом. Если K конечно, то значительную часть всех эллиптических кривых над K можно записать как кривые Эдвардса. Часто эллиптические кривые в форме Эдвардса определяются как имеющие c = 1, без потери общности. В следующих разделах предполагается, что c = 1.

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

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

Каждый Эдвардса кривой над полем K с характеристикой не равна 2 с бирационально эллиптической кривой над тем же полем: , где и точка отображается в бесконечность O . Это бирациональное отображение индуцирует группу на любой кривой Эдвардса.${\ displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$${\ displaystyle d \ neq 1}$${\ displaystyle (1 / e) v ^ {2} = u ^ {3} + (4 / e-2) u ^ {2} + u}$${\ displaystyle e = 1-d, u = {\ frac {1 + y} {1-y}}, v = {\ frac {2 (1 + y)} {x (1-y)}}}$${\ Displaystyle P = (0,1)}$

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

На любой эллиптической кривой сумма двух точек задается рациональным выражением координат точек, хотя в общем случае может потребоваться несколько формул, чтобы охватить все возможные пары. Для кривой Эдвардса нейтральным элементом считается точка (0, 1), сумма точек и определяется по формуле${\displaystyle (x_{1},y_{1})}$${\displaystyle (x_{2},y_{2})}$

${\displaystyle (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)\,}$

Обратное любой точки есть . Точка имеет порядок 2, а точки имеют порядок 4. В частности, кривая Эдвардса всегда имеет точку порядка 4 с координатами в K .${\displaystyle (x,y)}$${\displaystyle (-x,y)}$${\displaystyle (0,-1)}$${\displaystyle (\pm 1,0)}$

Если d не является квадратом в K и , то исключительных точек нет: знаменатели и всегда отличны от нуля. Таким образом, закон сложения Edwards завершается , когда d не квадрат в K . Это означает, что формулы работают для всех пар входных точек на кривой Эдвардса без исключений для удвоения, без исключения для нейтрального элемента, без исключения для отрицательных элементов и т. Д. ^[1] Другими словами, он определен для всех пар входные точки на кривой Эдвардса над K, и результат дает сумму входных точек.${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}}$${\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}}$${\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}}$

Если d - квадрат в K , то одна и та же операция может иметь исключительные точки, т.е. могут быть пары точек , в которых один из знаменателей обращается в ноль: либо, либо .${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}}$${\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}=0}$${\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}=0}$

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

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

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

${\displaystyle {\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}}$

и суть в этом. Можно доказать, что сумма P ₁ с нейтральным элементом (0,1) снова дает P ₁ . Действительно, используя приведенную выше формулу, координаты точки, заданной этой суммой, равны:${\displaystyle P_{1}=(1,0)}$

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+2x_{1}x_{2}y_{1}y_{2}}}=1}$

${\displaystyle y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-2x_{1}x_{2}y_{1}y_{2}}}=0}$

Аналог по кругу

Группа часов

Чтобы лучше понять концепцию «сложения» точек на кривой, приведем хороший пример классической группы окружностей:

возьмем круг радиуса 1

${\displaystyle {\displaystyle }x^{2}+y^{2}=1}$

и рассмотрим на нем две точки P ₁ = (x ₁ , y ₁ ), P ₂ = (x ₂ , y ₂ ). Пусть α ₁ и α ₂ такие углы, что:

${\displaystyle {\displaystyle }P_{1}=(x_{1},y_{1})=(\sin {\alpha _{1}},\cos {\alpha _{1}})}$

${\displaystyle {\displaystyle }P_{2}=(x_{2},y_{2})=(\sin {\alpha _{2}},\cos {\alpha _{2}})}$

Сумма P ₁ и P ₂ , таким образом, определяется суммой «их углов». То есть точка P ₃ = P ₁ + P ₂ - это точка на окружности с координатами (x ₃ , y ₃ ), где:

${\displaystyle {\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}}$

${\displaystyle {\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}.}$

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

${\displaystyle {\displaystyle }(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1}x_{2})}$.

Геометрический смысл сложения точек на кривых Эдвардса

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

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

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

Бирациональное отображение между кривой Эдварда и соответствующей эллиптической кривой переводит прямые линии в конические сечения ^[2] . Другими словами, для кривых Edwards три точки , и лежат на гиперболы .${\displaystyle Axy+Bx+Cy+D=0}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle -(P+Q)}$

Учитывая две различные неединичные точки , коэффициенты квадратичной формы (с точностью до скаляров) равны:${\displaystyle P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2}),P_{1}\neq P_{2}}$

${\displaystyle A=(x_{1}-x_{2})+(x_{1}y_{2}-x_{2}y_{1})}$,

${\displaystyle B=(x_{2}y_{2}-x_{1}y_{1})+y_{1}y_{2}(x_{2}-x_{1})}$,

${\displaystyle C=x_{1}x_{2}(y_{1}-y_{2}),D=C}$

В случае удвоения точки обратная точка лежит на конике, которая касается кривой в этой точке . Коэффициенты квадратичной формы, определяющей конику, равны (с точностью до скаляров):${\displaystyle P=(x,y)}$${\displaystyle -2P}$${\displaystyle P}$

${\displaystyle A=dx^{2}y-1}$,

${\displaystyle B=y-x^{2}}$,

${\displaystyle C=x(1-y),D=C}$

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

В контексте криптографии однородные координаты используются для предотвращения инверсий поля, которые появляются в аффинной формуле. Чтобы избежать инверсий в исходных формулах сложения Эдвардса, уравнение кривой можно записать в проективных координатах как:

${\displaystyle (X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$.

Проективная точка соответствует аффинной точке на кривой Эдвардса.${\displaystyle (X:Y:Z)}$ ${\displaystyle (X/Z:Y/Z)}$

Элемент идентичности представлен значком . Обратные IS .${\displaystyle (0:1:1)}$${\displaystyle (X:Y:Z)}$${\displaystyle (-X:Y:Z)}$

Формула сложения в однородных координатах имеет вид: ${\displaystyle (X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})}$

куда

${\displaystyle X_{3}=Z_{1}Z_{2}(X_{1}Y_{2}+X_{2}Y_{1})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})}$

${\displaystyle Y_{3}=Z_{1}Z_{2}(Y_{1}Y_{2}-X_{1}X_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}$

${\displaystyle Z_{3}=(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}$

Алгоритм

Сложение двух точек на кривой Эдвардса может быть вычислено более эффективно ^[3] в расширенной форме Эдвардса , где :${\displaystyle (X:Y:Z:T)}$${\displaystyle T=XY/Z}$${\displaystyle (X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})}$

${\displaystyle A=X_{1}X_{2};B=Y_{1}Y_{2};C=dT_{1}T_{2};D=Z_{1}Z_{2};}$

${\displaystyle E=(X_{1}+Y_{1})(X_{2}+Y_{2})-A-B;F=D-C;G=D+C;H=B-A;}$

${\displaystyle X_{3}=E\cdot F;Y_{3}=G\cdot H;Z_{3}=F\cdot G;T_{3}=E\cdot H;}$

Удвоение

Удвоение может быть выполнено по той же формуле, что и сложение. Удвоение относится к случаю, когда входы ( x ₁ ,  y ₁ ) и ( x ₂ ,  y ₂ ) равны.

Удвоение балла : ${\displaystyle P=(x,y)}$

${\displaystyle {\begin{aligned}(x,y)+(x,y)&=\left({\frac {2xy}{1+dx^{2}y^{2}}},{\frac {y^{2}-x^{2}}{1-dx^{2}y^{2}}}\right)\\[6pt]&=\left({\frac {2xy}{x^{2}+y^{2}}},{\frac {y^{2}-x^{2}}{2-x^{2}-y^{2}}}\right)\end{aligned}}}$

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

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

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

${\displaystyle x^{2}+y^{2}=1+2x^{2}y^{2}}$

и суть . Координаты точки :${\displaystyle P=(1,0)}$${\displaystyle P_{2}=2P_{1}}$

${\displaystyle x_{2}={\frac {2xy}{x^{2}+y^{2}}}=0}$

${\displaystyle y_{2}={\frac {y^{2}-x^{2}}{2-(x^{2}+y^{2})}}=-1}$

Таким образом, точка, полученная удвоением P, равна .${\displaystyle P_{2}=(0,-1)}$

Смешанное сложение

Смешанное сложение - это случай, когда известно, что Z ₂ равно 1. В таком случае A = Z ₁ ^. Z ₂ можно устранить, а общая стоимость уменьшится до 9 M +1 S +1 C +1 D +7 a.

Алгоритм

А = Z ₁ ^. Z ₂ // другими словами, A = Z ₁

В = Z ₁ ²

С = Х ₁ .X ₂

D = Y ₁ ^. Y ₂

E = d ^. C ^. D

F = BE

G = B + E

Х ₃ = А ^. F ((X _I + Y ₁ ) ^. (X ₂ + Y ₂ ) -CD)

У ₃ = А ^. G ^. (ОКРУГ КОЛУМБИЯ)

Z ₃ = С ^. F ^. грамм

Утроение

Можно утроить результат, сначала удвоив точку, а затем добавив результат к самому себе. Применяя уравнение кривой, как при удвоении, получаем

${\displaystyle 3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,}$

Есть два набора формул для этой операции в стандартных координатах Эдвардса. Первый стоит 9 M  +- S в то время как вторые потребностях в 7 М  +- S . Если отношение S / M очень мало, в частности, ниже 2/3, то лучше использовать второй набор, а для больших соотношений предпочтительнее первый. ^[4] Используя формулы сложения и удвоения (как указано выше), точка ( X ₁  :  Y ₁  :  Z ₁ ) символически вычисляется как 3 ( X ₁  :  Y ₁  :  Z ₁ ) и сравнивается с ( X₃  :  Y ₃  :  Z ₃ )

Пример утроения

Учитывая кривую Эдвардса с d = 2 и точку P ₁ = (1,0), точка 3P ₁ имеет координаты:

${\displaystyle x_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1}=-1}$

${\displaystyle y_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-2(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0}$

Итак, 3P ₁ = (- 1,0) = P- ₁ . Этот результат также можно найти, рассматривая пример удвоения: 2P ₁ = (0,1), поэтому 3P ₁ = 2P ₁ + P ₁ = (0, -1) + P ₁ = -P ₁ .

Алгоритм

А = Х ₁ ²

B = Y ₁ ²

С = (2Z ₁ ) ²

D = А + В

E = D ²

F = 2D. (AB)

G = EB.C

H = EA.C

Я = F + H

J = FG

X ₃ = GJX1

Y ₃ = HIY1

Z ₃ = IJZ1

Эта формула стоит 9 M  + 4 S

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

Бернштейн и Ланге ввели еще более быструю систему координат для эллиптических кривых, названную перевернутыми координатами Эдварда ^[5], в которой координаты ( X  :  Y  :  Z ) удовлетворяют кривой ( X ²  +  Y ² ) Z ²  = ( dZ ⁴  +  X ² Y ² ) и соответствует аффинной точке ( Z / X ,  Z / Y ) на кривой Эдвардса x ²  +  y ²  = 1 +  dx ²y ² с XYZ ≠ 0.

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

Для получения дополнительной информации об операциях с этими координатами см. Http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html.

Расширенные координаты кривых Эдварда

Существует еще одна система координат, с помощью которой можно представить кривую Эдвардса; эти новые координаты называются расширенными координатами ^[6] и даже быстрее, чем инвертированные координаты. Для получения дополнительной информации о временных затратах, необходимых для операций с этими координатами, см .: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Смотрите также

• Скрученная кривая Эдвардса

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

Примечания

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

• Бернштейн, Даниэль ; Ланге, Таня (2007),Более быстрое сложение и удвоение эллиптических кривых (PDF)
• Эдвардс, Гарольд М. (9 апреля 2007), "Нормальная форма для эллиптических кривых", Бюллетень Американского математического общества , 44 (3): 393-422, DOI : 10,1090 / s0273-0979-07-01153-6 , ISSN  0002-9904
• Более быстрые групповые операции над эллиптическими кривыми , Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон
• DJBernstein, P.Birkner. Т. Ланге, К. Питерс,Оптимизация односкалярного умножения на эллиптической кривой с двойной базой (PDF)CS1 maint: несколько имен: список авторов ( ссылка )
• Вашингтон, Лоуренс К. (2008), Эллиптические кривые: теория чисел и криптография , дискретная математика и ее приложения (2-е изд.), Chapman & Hall / CRC, ISBN 978-1-4200-7146-7
• Бернштейн, Даниэль ; Ланге, Таня, перевернутые координаты Эдвардса (PDF)

внешние ссылки

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-edwards.html