Кривая Монтгомери - Википедия - Montgomery curve

В математика в Кривая Монтгомери это форма эллиптическая кривая, отличается от обычного Форма Вейерштрасса, представлен Питер Л. Монтгомери в 1987 г.^[1] Он используется для определенных вычислений, в частности в различных криптография Приложения.

Определение

Кривая Монтгомери уравнения ${ textstyle { frac {1} {4}} y ^ {2} = x ^ {3} + 2,5x ^ {2} + x}$

Кривая Монтгомери над поле K определяется уравнение

${ displaystyle M_ {A, B}: By ^ {2} = x ^ {3} + Ax ^ {2} + x}$

для некоторых А, B ∈ K и с B(А² − 4) ≠ 0.

Обычно это изгиб рассматривается над конечное поле K (например, над конечным полем q элементы, K = F_q) с характеристика отличается от 2 и с А ≠ ±2 и B ≠ 0, но они также рассматриваются рациональные с такими же ограничениями для А и B.

Арифметика Монтгомери

Можно проделать некоторые «операции» между точки эллиптической кривой: «складываем» две точки ${ displaystyle P, Q}$ состоит из поиска третьего ${ displaystyle R}$ такой, что ${ Displaystyle R = P + Q}$; "удвоение" точки состоит из вычисления ${ displaystyle [2] P = P + P}$ (Для получения дополнительной информации об операциях см. Групповой закон ) и ниже.

Точка ${ Displaystyle Р = (х, у)}$ на эллиптической кривой в форме Монтгомери ${ displaystyle By ^ {2} = x ^ {3} + Ax ^ {2} + x}$ можно представить в координатах Монтгомери ${ Displaystyle P = (X: Z)}$, куда ${ Displaystyle P = (X: Z)}$ находятся проективные координаты и ${ displaystyle x = X / Z}$ за ${ Displaystyle Z neq 0}$.

Обратите внимание, что при таком представлении точки теряется информация: действительно, в этом случае нет различия между аффинные точки ${ Displaystyle (х, у)}$ и ${ Displaystyle (х, -у)}$ потому что они оба даны точкой ${ displaystyle (X: Z)}$. Однако с помощью этого представления можно получить кратные точки, то есть заданные ${ Displaystyle P = (X: Z)}$, вычислить ${ displaystyle [n] P = (X_ {n}: Z_ {n})}$.

Теперь, учитывая два момента ${ Displaystyle P_ {n} = [n] P = (X_ {n}: Z_ {n})}$ и ${ displaystyle P_ {m} = [m] P = (X_ {m}: Z_ {m})}$: их сумма дается точкой ${ Displaystyle P_ {m + n} = P_ {m} + P_ {n} = (X_ {m + n}: Z_ {m + n})}$ чей координаты находятся:

${ displaystyle X_ {m + n} = Z_ {mn} ((X_ {m} -Z_ {m}) (X_ {n} + Z_ {n}) + (X_ {m} + Z_ {m}) ( X_ {n} -Z_ {n})) ^ {2}}$

${ displaystyle Z_ {m + n} = X_ {mn} ((X_ {m} -Z_ {m}) (X_ {n} + Z_ {n}) - (X_ {m} + Z_ {m}) ( X_ {n} -Z_ {n})) ^ {2}}$

Если ${ displaystyle m = n}$, тогда операция становится «удвоением»; координаты ${ displaystyle [2] P_ {n} = P_ {n} + P_ {n} = P_ {2n} = (X_ {2n}: Z_ {2n})}$ даются следующими уравнениями:

${ displaystyle 4X_ {n} Z_ {n} = (X_ {n} + Z_ {n}) ^ {2} - (X_ {n} -Z_ {n}) ^ {2}}$

${ Displaystyle X_ {2n} = (X_ {n} + Z_ {n}) ^ {2} (X_ {n} -Z_ {n}) ^ {2}}$

${ Displaystyle Z_ {2n} = (4X_ {n} Z_ {n}) ((X_ {n} -Z_ {n}) ^ {2} + ((A + 2) / 4) (4X_ {n} Z_ {n}))}$

Первая рассмотренная выше операция (добавление ) имеет временные затраты 3M+2S, куда M обозначает умножение двух общих элементы поля, на котором задана эллиптическая кривая, а S обозначает возведение в квадрат генерального элемента поля.

Вторая операция (удвоение) требует затрат времени 2.M + 2S + 1D, куда D обозначает умножение общего элемента на постоянный; обратите внимание, что константа ${ displaystyle (A + 2) / 4}$, так ${ displaystyle A}$ можно выбрать, чтобы иметь небольшойD.

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

Следующий алгоритм представляет собой удвоение точки. ${ Displaystyle P_ {1} = (X_ {1}: Z_ {1})}$ на эллиптической кривой в форме Монтгомери.

Предполагается, что ${ displaystyle Z_ {1} = 1}$. Стоимость этой реализации составляет 1M + 2S + 1 * A + 3add + 1 * 4. Здесь M обозначает необходимое умножение, S указывает квадраты, а a относится к умножению на A.

${ Displaystyle XX_ {1} = X_ {1} ^ {2} ,}$

${ Displaystyle X_ {2} = (XX_ {1} -1) ^ {2} ,}$

${ Displaystyle Z_ {2} = 4X_ {1} (XX_ {1} + aX_ {1} +1) ,}$

Пример

Позволять ${ displaystyle P_ {1} = (2, { sqrt {3}})}$ быть точкой на кривой ${ displaystyle 2y ^ {2} = x ^ {3} -x ^ {2} + x}$.В координатах ${ displaystyle (X_ {1}: Z_ {1})}$, с ${ Displaystyle x_ {1} = X_ {1} / Z_ {1}}$, ${ Displaystyle P_ {1} = (2: 1)}$.

Потом:

${ Displaystyle XX_ {1} = X_ {1} ^ {2} = 4 ,}$

${ Displaystyle X_ {2} = (XX_ {1} -1) ^ {2} = 9 ,}$

${ Displaystyle Z_ {2} = 4X_ {1} (XX_ {1} + AX_ {1} +1) = 24 ,}$

Результат - это точка ${ displaystyle P_ {2} = (X_ {2}: Z_ {2}) = (9:24)}$ такой, что ${ displaystyle P_ {2} = 2P_ {1}}$.

Добавление

Учитывая два очка ${ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$, ${ Displaystyle P_ {2} = (x_ {2}, y_ {2})}$ на кривой Монтгомери ${ displaystyle M_ {A, B}}$ в аффинных координатах точка ${ displaystyle P_ {3} = P_ {1} + P_ {2}}$ представляет, геометрически третья точка пересечения между ${ displaystyle M_ {A, B}}$ и линия, проходящая через ${ displaystyle P_ {1}}$ и ${ displaystyle P_ {2}}$. Есть возможность найти координаты ${ displaystyle (x_ {3}, y_ {3})}$ из ${ displaystyle P_ {3}}$, следующим образом:

1) рассмотрим общую линию ${ displaystyle ~ y = lx + m}$ в аффинной плоскости и пропустить ${ displaystyle P_ {1}}$ и ${ displaystyle P_ {2}}$ (наложим условие), таким образом получим ${ displaystyle l = { frac {y_ {2} -y_ {1}} {x_ {2} -x_ {1}}}}$ и ${ displaystyle m = y_ {1} - left ({ frac {y_ {2} -y_ {1}} {x_ {2} -x_ {1}}} right) x_ {1}}$;

2) пересечь прямую с кривой ${ displaystyle M_ {A, B}}$, заменяя ${ displaystyle ~ y}$ переменная в уравнении кривой с ${ displaystyle ~ y = lx + m}$; следующее уравнение третьей степени получается:

${ displaystyle x ^ {3} + (A-Bl ^ {2}) x ^ {2} + (1-2Blm) x-Bm ^ {2} = 0.}$

Как уже отмечалось ранее, это уравнение имеет три решения, которые соответствуют ${ displaystyle ~ x}$ координаты ${ displaystyle P_ {1}}$, ${ displaystyle P_ {2}}$ и ${ displaystyle P_ {3}}$. В частности, это уравнение можно переписать как:

${ Displaystyle (х-х_ {1}) (х-х_ {2}) (х-х_ {3}) = 0}$

3) Сравнивая коэффициенты двух идентичных уравнений, приведенных выше, в частности коэффициенты членов второй степени, получаем:

${ displaystyle -x_ {1} -x_ {2} -x_ {3} = A-Bl ^ {2}}$.

Так, ${ displaystyle x_ {3}}$ можно записать в терминах ${ displaystyle x_ {1}}$, ${ displaystyle y_ {1}}$, ${ displaystyle x_ {2}}$, ${ displaystyle y_ {2}}$, в качестве:

${ displaystyle x_ {3} = B left ({ frac {y_ {2} -y_ {1}} {x_ {2} -x_ {1}}} right) ^ {2} -A-x_ { 1} -x_ {2}.}$

4) Найти ${ displaystyle ~ y}$ координата точки ${ displaystyle P_ {3}}$ достаточно подставить значение ${ displaystyle x_ {3}}$ в соответствии ${ displaystyle ~ y = lx + m}$. Обратите внимание, что это не даст смысла ${ displaystyle P_ {3}}$ напрямую. Действительно, этим методом находятся координаты точки ${ displaystyle ~ R}$ такой, что ${ Displaystyle R + P_ {1} + P_ {2} = P _ { infty}}$, но если нужна итоговая точка суммы между ${ displaystyle P_ {1}}$ и ${ displaystyle P_ {2}}$, то необходимо заметить, что: ${ Displaystyle R + P_ {1} + P_ {2} = P _ { infty}}$ если и только если ${ displaystyle -R = P_ {1} + P_ {2}}$. Итак, учитывая суть ${ displaystyle ~ R}$, необходимо найти ${ displaystyle ~ -R}$, но это легко сделать, изменив знак на ${ displaystyle ~ y}$ координата ${ displaystyle ~ R}$. Другими словами, необходимо будет изменить знак ${ displaystyle ~ y}$ координата, полученная подстановкой значения ${ displaystyle x_ {3}}$ в уравнении линии.

Итак, координаты точки ${ Displaystyle P_ {3} = (x_ {3}, y_ {3})}$, ${ displaystyle P_ {3} = P_ {1} + P_ {2}}$ находятся:

${ displaystyle x_ {3} = { frac {B (y_ {2} -y_ {1}) ^ {2}} {(x_ {2} -x_ {1}) ^ {2}}} - A- x_ {1} -x_ {2} = { frac {B (x_ {2} y_ {1} -x_ {1} y_ {2}) ^ {2}} {x_ {1} x_ {2} (x_ {2} -x_ {1}) ^ {2}}}}$

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

Удвоение

Учитывая точку ${ displaystyle P_ {1}}$ на кривой Монтгомери ${ displaystyle M_ {A, B}}$, смысл ${ displaystyle [2] P_ {1}}$ геометрически представляет собой третью точку пересечения между кривой и прямой, касательной к ${ displaystyle P_ {1}}$; Итак, чтобы найти координаты точки ${ displaystyle P_ {3} = 2P_ {1}}$ достаточно следовать тому же методу, который указан в формуле сложения; однако в этом случае строка у = лк + м должен касаться кривой в точке ${ displaystyle P_ {1}}$, так что если ${ displaystyle M_ {A, B}: f (x, y) = 0}$ с

${ displaystyle f (x, y) = x ^ {3} + Ax ^ {2} + x-By ^ {2},}$

тогда значение л, который представляет собой склон линии, определяется как:

${ displaystyle l = - left. { frac { partial f} { partial x}} right / { frac { partial f} { partial y}}}$

посредством теорема о неявной функции.

Так ${ displaystyle l = { frac {3x_ {1} ^ {2} + 2Ax_ {1} +1} {2By_ {1}}}}$ и координаты точки ${ displaystyle P_ {3}}$, ${ displaystyle P_ {3} = 2P_ {1}}$ находятся:

${ displaystyle { begin {align} x_ {3} & = Bl ^ {2} -A-x_ {1} -x_ {1} = { frac {B (3x_ {1} ^ {2} + 2Ax_ { 1} +1) ^ {2}} {(2By_ {1}) ^ {2}}} - A-x_ {1} -x_ {1} & = { frac {(x_ {1} ^ { 2} -1) ^ {2}} {4By_ {1} ^ {2}}} = { frac {(x_ {1} ^ {2} -1) ^ {2}} {4x_ {1} (x_ {1} ^ {2} + Ax_ {1} +1)}} [8pt] y_ {3} & = (2x_ {1} + x_ {1} + A) l-Bl ^ {3} -y_ {1} & = { frac {(2x_ {1} + x_ {1} + A) (3 {x_ {1}} ^ {2} + 2Ax_ {1} +1)} {2By_ {1} }} - { frac {B (3 {x_ {1}} ^ {2} + 2Ax_ {1} +1) ^ {3}} {(2By_ {1}) ^ {3}}} - y_ {1 }. end {выравнивается}}}$

Эквивалентность скрученным кривым Эдвардса

Позволять ${ displaystyle K}$ - поле с характеристикой, отличной от 2.

Позволять ${ displaystyle M_ {A, B}}$ - эллиптическая кривая в форме Монтгомери:

${ displaystyle M_ {A, B}: Bv ^ {2} = u ^ {3} + Au ^ {2} + u}$

с ${ Displaystyle А в К smallsetminus {- 2,2 }}$, ${ displaystyle B in K smallsetminus {0 }}$

и разреши ${ displaystyle E_ {a, d}}$ - эллиптическая кривая в скрученной форме Эдвардса:

${ displaystyle E_ {a, d} : ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}, ,}$

с ${ displaystyle a, d in K smallsetminus {0 }, quad a neq d.}$

Следующая теорема показывает бирациональная эквивалентность между кривыми Монтгомери и искривленная кривая Эдвардса:^[2]

Теорема (i) Всякая скрученная кривая Эдвардса бирационально эквивалентна кривой Монтгомери над ${ displaystyle K}$В частности, закрученная кривая Эдвардса ${ displaystyle E_ {a, d}}$ бирационально эквивалентна кривой Монтгомери ${ displaystyle M_ {A, B}}$ куда ${ Displaystyle А = { гидроразрыва {2 (а + г)} {а-г}}}$, и ${ displaystyle B = { frac {4} {a-d}}}$.

В карта:

${ displaystyle psi ,: , E_ {a, d} rightarrow M_ {A, B}}$

${ displaystyle (x, y) mapsto (u, v) = left ({ frac {1 + y} {1-y}}, { frac {1 + y} {(1-y) x} }верно)}$

является бирациональной эквивалентностью из ${ displaystyle E_ {a, d}}$ к ${ displaystyle M_ {A, B}}$, с инверсией:

${ displaystyle psi ^ {- 1}}$: ${ displaystyle M_ {A, B} rightarrow E_ {a, d}}$

${ displaystyle (u, v) mapsto (x, y) = left ({ frac {u} {v}}, { frac {u-1} {u + 1}} right), a = { frac {A + 2} {B}}, d = { frac {A-2} {B}}}$

Обратите внимание, что эта эквивалентность двух кривых верна не везде: действительно, карта ${ displaystyle psi}$ не определен в точках ${ displaystyle v = 0}$ или же ${ displaystyle u + 1 = 0}$ из ${ displaystyle M_ {A, B}}$.

Эквивалентность кривым Вейерштрасса

Любую эллиптическую кривую можно записать в форме Вейерштрасса. В частности, эллиптическая кривая в форме Монтгомери

${ displaystyle M_ {A, B}}$: ${ displaystyle By ^ {2} = x ^ {3} + Ax ^ {2} + x,}$

можно преобразовать следующим образом: разделите каждый член уравнения на ${ displaystyle M_ {A, B}}$ к ${ displaystyle B ^ {3}}$, и подставим переменные Икс и у, с ${ displaystyle u = { frac {x} {B}}}$ и ${ displaystyle v = { frac {y} {B}}}$ соответственно, чтобы получить уравнение

${ displaystyle v ^ {2} = u ^ {3} + { frac {A} {B}} u ^ {2} + { frac {1} {B ^ {2}}} u.}$

Чтобы получить отсюда краткую форму Вейерштрасса, достаточно заменить ты с переменной ${ displaystyle t - { frac {A} {3B}}}$:

${ displaystyle v ^ {2} = left (t - { frac {A} {3B}} right) ^ {3} + { frac {A} {B}} left (t - { frac {A} {3B}} right) ^ {2} + { frac {1} {B ^ {2}}} left (t - { frac {A} {3B}} right);}$

наконец, это дает уравнение:

${ displaystyle v ^ {2} = t ^ {3} + left ({ frac {3-A ^ {2}} {3B ^ {2}}} right) t + left ({ frac {2A ^ {3} -9A} {27B ^ {3}}} right).}$

Следовательно, отображение задается как

${ displaystyle psi}$: ${ displaystyle M_ {A, B} rightarrow E_ {a, b}}$

${ displaystyle (x, y) mapsto (t, v) = left ({ frac {x} {B}} + { frac {A} {3B}}, { frac {y} {B} } right), a = { frac {3-A ^ {2}} {3B ^ {2}}}, b = { frac {2A ^ {3} -9A} {27B ^ {3}}} }$

Напротив, эллиптическая кривая над базовым полем ${ Displaystyle mathbb {F}}$ в форме Вейерштрасса

${ displaystyle E_ {a, b}}$: ${ displaystyle v ^ {2} = t ^ {3} + at + b}$

можно преобразовать в форму Монтгомери тогда и только тогда, когда ${ displaystyle E_ {a, b}}$ имеет порядок, кратный четырем, и удовлетворяет следующим условиям:^[3]

1. ${ displaystyle z ^ {3} + az + b = 0}$ имеет хотя бы один корень ${ displaystyle alpha in mathbb {F}}$; и
2. ${ Displaystyle 3 альфа ^ {2} + а}$ является квадратичным вычетом в ${ Displaystyle mathbb {F}}$.

Когда эти условия выполнены, то при ${ displaystyle s = ({ sqrt {3 alpha ^ {2} + a}}) ^ {- 1}}$ у нас есть отображение

${ displaystyle psi ^ {- 1}}$: ${ displaystyle E_ {a, b} rightarrow M_ {A, B}}$

${ displaystyle (t, v) mapsto (x, y) = left (s (t- alpha), sv right), A = 3 alpha s, B = s}$.

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

• Подкрутка25519
• Таблица затрат на операции в эллиптических кривых - информация о необходимом времени работы в конкретном случае

Примечания

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

• Питер Л. Монтгомери (1987). "Ускорение методов факторизации Полларда и эллиптических кривых". Математика вычислений. 48 (177): 243–264. Дои:10.2307/2007888. JSTOR  2007888.
• Дэниел Дж. Бернштейн, Питер Биркнер, Марк Джой, Таня Ланге и Кристиан Петерс (2008). «Скрученные кривые Эдвардса». Прогресс в криптологии - AFRICACRYPT 2008. Конспект лекций по информатике. 5023. Springer-Verlag Berlin Heidelberg. С. 389–405. Дои:10.1007/978-3-540-68164-9_26. ISBN  978-3-540-68159-5.CS1 maint: несколько имен: список авторов (связь)
• Воутер Кастрик; Стивен Гэлбрейт; Реза Резаэян Фарашахи (2008). «Эффективная арифметика эллиптических кривых с использованием смешанного представления Эдвардса-Монтгомери» (PDF). Цитировать журнал требует | журнал = (помощь)

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

• Кривые рода 1 над полями большой характеристики