Кривая Доче – Икарта – Кохеля, ориентированная на удвоение - Википедия - 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 Р = (х, у)}$ - нетривиальный элемент (${ 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 К = 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 К = 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).

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

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

Примечания

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

• Кристоф Доче, Томас Икарт и Дэвид Р. Кохель (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