Кривая Доче – Икарта – Кохеля, ориентированная на удвоение - Doubling-oriented Doche–Icart–Kohel curve

Кривая Дош-Икарта-Кохеля уравнения, ориентированная на удвоение ${\displaystyle y^{2}=x^{3}-x^{2}-16x}$

В математика, то кривая Доче – Икарта – Кохеля, ориентированная на удвоение это форма, в которой эллиптическая кривая можно написать. Это частный случай Форма Вейерштрасса и это также важно в криптография с эллиптической кривой потому что удвоение значительно ускоряется (вычисление как композиция 2-изогения и это двойной ). Он был введен Кристофом Доче, Томасом Икартом и Дэвидом Р. Кохелем в Эффективное скалярное умножение с помощью разложения изогении.^[1]

Определение

Позволять ${\displaystyle K}$ быть поле и разреши ${\displaystyle a\in K}$. Тогда кривая Доче – Икарта – Кохеля, ориентированная на удвоение, с параметр а в аффинные координаты представлен:

${\displaystyle y^{2}=x^{3}+ax^{2}+16ax}$

Эквивалентно в проективные координаты:

${\displaystyle ZY^{2}=X^{3}+aZX^{2}+16aXZ^{2},}$

с ${\displaystyle x={\frac {X}{Z}}}$ и ${\displaystyle y={\frac {Y}{Z}}}$.

Обратите внимание: поскольку эта кривая является частным случаем Форма Вейерштрасса, преобразования к наиболее распространенной форме эллиптической кривой (форме Вейерштрасса) не требуются.

Групповое право

Интересно проанализировать групповой закон в криптография на основе эллиптических кривых, определяя формулы сложения и удвоения, поскольку эти формулы необходимы для вычисления кратных точек [n] P (видеть Возведение в степень возведением в квадрат ). В общем случае групповой закон определяется следующим образом: если три точки лежат на одной прямой, то сумма их равна нулю. Таким образом, в силу этого свойства групповые законы различны для каждой формы кривой.

В этом случае, поскольку эти кривые являются частными случаями кривых Вейерштрасса, добавление является просто стандартным добавлением для кривых Вейерштрасса. С другой стороны, чтобы удвоить очко, можно использовать стандартную формулу удвоения, но это будет не так быстро. нейтральный элемент является ${\displaystyle \theta =(0:1:0)}$ (в проективных координатах), для которых ${\displaystyle \theta =-\theta }$. Тогда, если ${\displaystyle P=(x,y)}$ - нетривиальный элемент (${\displaystyle P!=O}$), то обратная к этой точке (сложением) будет –P = (x, -y).

Добавление

В этом случае, аффинные координаты будет использоваться для определения формулы сложения:

(Икс₁, y₁) + (х₂, y₂) = (х₃, y₃) где

Икс₃ = (-x₁³+ (х₂-а) х₁²+ (х₂²+ 2ax₂)Икс₁+ (y₁²-2 года₂у₁+ (- х₂³-ax₂²+ y₂²)))/(Икс₁²-2x₂Икс₁+ х₂²)

у₃ = ((-y₁+ 2 года₂)Икс₁³+ (- ау₁+ (- 3 года₂Икс₂+ ай₂))Икс₁²+ ((3x₂²+ 2ax₂) y₁-2 дня₂Икс₂)Икс₁+ (y₁³-3 года₂у₁²+ (- 2x₂³-ax₂²+ 3 года₂²) y₁+ (y₂Икс₂³+ ай₂Икс₂²-у₂³)))/(-Икс₁³+ 3x₂Икс₁²-3x₂²Икс₁+ х₂³)

Удвоение

2 (х₁, y₁) = (х₃, y₃)

Икс₃ = 1 / (4 года₁²)Икс₁⁴-8г / год₁²Икс₁²+ 64a2 / y₁²

у₃ = 1 / (8лет₁³)Икс₁⁶+ ((- а²+ 40a) / (4 года₁³))Икс₁⁴+ ((ау₁²+ (16a³-640a²)) / (4 года₁³))Икс₁²+ ((- 4a²у₁²-512a³) / г₁³)

Алгоритмы и примеры

Добавление

Самым быстрым добавлением является следующее (по сравнению с результатами, приведенными в: http://hyperelliptic.org/EFD/g1p/index.html ), а затраты на это - 4 умножения, 4 возведения в квадрат и 10 сложения.

А = Y₂-Y₁

AA = A²

B = X₂-ИКС₁

CC = B²

F = X₁CC

Z₃ = 2CC

D = X₂Z₃

ZZ₃ = Z₃²

Икс₃ = 2 (AA-F) -aZ₃-D

Y₃ = ((А + В)²-AA-CC) (D-X₃) -Y₂ZZ₃

Пример

Позволять ${\displaystyle K=\mathbb {Q} }$. Пусть P = (X₁, Y₁) = (2,1), Q = (X₂, Y₂) = (1, -1) и a = 1, то

А = 2

AA = 4

B = 1

CC = 1

F = 2

Z₃=4

D = 4

ZZ₃=16

Икс₃=-4

Y₃=336

Таким образом, P + Q = (- 4: 336: 4)

Удвоение

Следующий алгоритм является самым быстрым (см. Следующую ссылку для сравнения: http://hyperelliptic.org/EFD/g1p/index.html ), а затраты на это - 1 умножение, 5 возведение в квадрат и 7 сложений.

А = Х₁²

B = A-a16

C = а₂А

YY = Y₁²

YY₂ = 2YY

Z₃ = 2YY₂

Икс₃ = B²

V = (Y₁+ B) 2-YY-X₃

Y₃ = V (X₃+ 64C + a (ГГ₂-C))

ZZ₃ = Z₃²

Пример

Позволять ${\displaystyle K=\mathbb {Q} }$ и а = 1. Пусть P = (- 1,2), тогда Q = [2] P = (x3, y3) определяется как:

А = 1

В = -15

С = 2

ГГ = 4

YY₂=8

Z₃=16

Икс₃=225

V = 27

Y₃=9693

ZZ₃=256

Таким образом, Q = (225: 9693: 16).

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

Вычисления сложения и удвоения должны выполняться как можно быстрее, поэтому удобнее использовать следующее представление координат:

${\displaystyle x,y}$ представлены ${\displaystyle X,Y,Z,ZZ}$ удовлетворяющие следующим уравнениям:

${\displaystyle x={\frac {X}{Z}}}$

${\displaystyle y={\frac {Y}{ZZ}}}$

${\displaystyle ZZ=Z^{2}}$

Тогда кривая Доче – Икарта – Кохеля, ориентированная на удвоение, задается следующим уравнением:

${\displaystyle Y^{2}=ZX^{3}+aZ^{2}X^{2}+16aZ^{3}X}$.

В этом случае,${\displaystyle P=(X:Y:Z:ZZ)}$ общая точка с обратным ${\displaystyle -P=(X:-Y:Z:ZZ)}$Кроме того, точки над кривой удовлетворяют: ${\displaystyle (X:Y:Z:Z^{2})=(\lambda X:\lambda ^{2}Y:\lambda Z:\lambda ^{2}Z^{2})}$ для всех ${\displaystyle \lambda }$ ненулевой.

Формулы более быстрого удвоения для этих кривых и формулы смешанного сложения были введены Доче, Икартом и Кохелем; но в настоящее время эти формулы улучшены Дэниелом Дж. Бернстайном и Таней Ланге (см. ниже ссылку на EFD).

Внутренняя ссылка

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

Примечания

1. Кристоф Доче, Томас Икарт и Дэвид Р. Кохель, Эффективное скалярное умножение с помощью разложения изогении

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

• Кристоф Доче, Томас Икарт и Дэвид Р. Кохель (2006). «Эффективное скалярное умножение с помощью разложения изогении». Криптография с открытым ключом - PKC 2006. Конспект лекций по информатике. 3958. Springer Berlin / Heidelberg. С. 191–206. Дои:10.1007/11745853_13. ISBN  978-3-540-33851-2.

• Даниэль Дж. Бернштейн и Таня Ланге (2008). Анализ и оптимизация скалярного умножения на эллиптическую кривую. ISBN  9780821857892.

внешняя ссылка

• http://hyperelliptic.org/EFD/g1p/index.html
• http://www.hyperelliptic.org/EFD/g1p/auto-2dik.html