Кривая Эдвардса - Edwards curve

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

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

Определение

Уравнение кривой Эдвардса над поле K который не имеет характеристика 2 является:

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

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

${ 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.

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

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

Точки на эллиптической кривой образуют абелеву группу: можно складывать точки и брать целые числа, кратные одной точке. Когда эллиптическая кривая описывается неособым кубическим уравнением, тогда сумма двух точек п и Q, обозначенный п + Q, напрямую связана с третьей точкой пересечения кривой и линией, проходящей через п и Q. Но для особых кривых более высокой степени, таких как кривые Эдвардса, ситуация несколько сложнее. Для геометрического объяснения закона сложения на кривых Эдвардса см. «Ускоренное вычисление пар Тейта» Арен и др.^[1]

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

На любой эллиптической кривой, под которой подразумевается кривая рода 1 и точка, выбранная для обслуживания нейтрального элемента, сумма двух точек задается рациональным выражением координат точек, хотя в общем случае может потребоваться использование несколько формул, охватывающих все возможные пары. Для кривой Эдвардса, взяв нейтральный элемент быть точкой (0, 1), сумма точек (Икс₁, y₁) и (Икс₂, y₂) задается формулой

${ 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) = left ({ frac {x_ {1} y_ {1} + x_ {2} y_ {2}} {x_ {1) } x_ {2} + y_ {1} y_ {2}}}, { frac {x_ {1} y_ {1} -x_ {2} y_ {2}} {x_ {1} y_ {2} -y_ {1} x_ {2}}} right) ,}$

Инверсия любой точки (Икс₁, y₁) является (-Икс₁, y₁). Можно проверить, что точка (0, −1) имеет порядок 2, а точки (± 1,0) имеют порядок 4. В частности, кривая Эдвардса всегда имеет точку порядка 4 с координатами в K.

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

Если d - квадрат в K, то одна и та же операция может иметь исключительные точки, т.е. могут быть пары (Икс₁, y₁) и (Икс₂, y₂) где 1 +dx₁Икс₂y₁y₂ = 0 или 1 -dx₁Икс₂y₁y₂ = 0.

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

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

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

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

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

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

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

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

Группа часов

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

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

${ Displaystyle { Displaystyle} х ^ {2} + у ^ {2} = 1}$

и рассмотрим две точки P₁= (х₁, y₁), П₂= (х₂, 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})}$.

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

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

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

Проективная точка (Икс₁ : Y₁ : Z₁) соответствует аффинная точка (Икс₁/Z₁, Y₁/Z₁) на кривой Эдвардса.

Элемент идентичности представлен как (0: 1: 1). Обратное к (Икс₁ : Y₁ : Z₁) является (-Икс₁ : Y₁ : Z₁).

Формула сложения в проективных однородных координатах задается следующим образом: [они явно неадекватны, поскольку, когда P1 = P2 для удвоения точки, результат переходит в X3 = 0, Y3 = 0, Z3 = 0]

(Икс₃ : Y₃ : Z₃) = (Икс₁ : Y₁ : Z₁) + (Икс₂ : Y₂ : Z₂)

куда

Икс₃ = Z₁Z₂(Икс₁Y₂ − Y₁Икс₂)(Икс₁Y₁Z₂² + Z₁²Икс₂Y₂)

Y₃ = Z₁Z₂(ИКС₁Икс₂ + Y₁Y₂)(ИКС₁Y₁Z₂² - Z₁²Икс₂Y₂)

Z₃ = kZ₁²Z₂²(ИКС₁Икс₂ + Y₁Y₂)(ИКС₁Y₂ - Y₁Икс₂) с k = 1/c.

Алгоритм

Используя следующий алгоритм, X₃, Y₃, Z₃ можно записать как: X₃→ ГДж, Y₃→ HK, Z₃→ кДж.д

где: A → X₁Z₂,

B → Y₁Z₂,

C → Z₁Икс₂,

D → Z₁Y₂,

E → AB,

F → CD,

G → E + F,

H → E-F,

J → (A-C) (B + D) -H,

К → (А + D) (В + С) -G

Удвоение

Удвоение может выполняться по той же формуле, что и сложение. Удвоение относится к случаю, когда входы (Икс₁, y₁) и (Икс₂, y₂), как известно, равны. С (Икс₁, y₁) находится на кривой Эдвардса, можно заменить коэффициент на (Икс₁² + y₁² − 1)/Икс₁²y₁² следующее:

${ displaystyle { begin {align} 2 (x_ {1}, y_ {1}) & = (x_ {1}, y_ {1}) + (x_ {1}, y_ {1}) [6pt ] 2 (x_ {1}, y_ {1}) & = left ({ frac {2x_ {1} y_ {1}} {1 + dx_ {1} ^ {2} y_ {1} ^ {2}) }}, { frac {y_ {1} ^ {2} -x_ {1} ^ {2}} {1-dx_ {1} ^ {2} y_ {1} ^ {2}}} right) [6pt] & = left ({ frac {2x_ {1} y_ {1}} {x_ {1} ^ {2} + y_ {1} ^ {2}}}, { frac {y_ {1} } ^ {2} -x_ {1} ^ {2}} {2-x_ {1} ^ {2} -y_ {1} ^ {2}}} right) end {align}}}$

Это уменьшает степень знаменателя с 4 до 2, что отражается в более быстром удвоении. Общее сложение в координатах Эдвардса занимает 10M + 1S + 1C + 1D + 7а и удвоение затрат 3M + 4S + 3C + 6а куда M это умножение полей, S разводка, D - стоимость умножения на выбираемый параметр кривой и а это добавление поля.

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

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

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

и точка P₁= (1,0). Координаты точки 2P₁ находятся:

${ displaystyle x_ {3} = { frac {2x_ {1} y_ {1}} {1 + dx_ {1} ^ {2} y_ {1} ^ {2}}} = 0}$

${ displaystyle y_ {3} = { frac {y_ {1} ^ {2} -x_ {1} ^ {2}} {1-dx_ {1} ^ {2} y_ {1} ^ {2}} } = - 1}$

Точка, полученная удвоением P₁ таким образом, P₃=(0,-1).

Смешанное добавление

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

Алгоритм

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

B = Z₁²

С = Х₁.ИКС₂

D = Y₁^.Y₂

E = d^.C^.D

F = B-E

G = B + E

Икс₃= А^.F ((X_я+ Y₁)^.(ИКС₂+ Y₂)-CD)

Y₃= А^.грамм^.(ОКРУГ КОЛУМБИЯ)

Z₃= C^.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). ,}$

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

G = E-B.C

H = E-A.C

Я = F + H

J = F-G

Икс₃= G.J.X1

Y₃= H.I.Y1

Z₃= I.J.Z1

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

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

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

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

Подробнее об операциях с этими координатами см. http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

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

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

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

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

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

Примечания

Рекомендации

• Бернштейн, Даниэль; Ланге, Таня (2007), Более быстрое сложение и удвоение эллиптических кривых (PDF)
• Эдвардс, Гарольд М. (9 апреля 2007 г.), «Нормальная форма для эллиптических кривых», Бюллетень Американского математического общества, 44 (3): 393–422, Дои:10.1090 / s0273-0979-07-01153-6, ISSN  0002-9904
• Более быстрые групповые операции над эллиптическими кривыми, Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон
• Д. Дж. Бернштейн, П. Биркнер. Т. Ланге, К. Питерс, Оптимизация односкалярного умножения на эллиптической кривой с двойной базой (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