Кривая Монтгомери - Montgomery curve - Wikipedia

В математика в Кривая Монтгомери это форма эллиптическая кривая, отличается от обычного Форма Вейерштрасса, представлен Питер Л. Монтгомери в 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 \in K$ и с $B (А 2 - 4) \neq 0$ .

Обычно это изгиб рассматривается над конечное поле K (например, над конечным полем $q$ элементы, $K = F q$ ) с характеристика отличается от 2 и с $А \neq \pm2$ и $B \neq 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]

${ displaystyle z ^ {3} + az + b = 0}$ имеет хотя бы один корень ${ displaystyle alpha in mathbb {F}}$ ; и
${ 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: несколько имен: список авторов (связь)
^ Кацуюки Окея, Хироюки Куруматани и Коичи Сакураи (2000). Эллиптические кривые с формой Монтгомери и их криптографические приложения. Криптография с открытым ключом (PKC2000). Дои:10.1007/978-3-540-46588-1_17.CS1 maint: несколько имен: список авторов (связь)

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

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

[1] Питер Л. Монтгомери (1987). "Ускорение методов факторизации Полларда и эллиптических кривых". Математика вычислений. 48 (177): 243–264. Дои:10.2307/2007888. JSTOR 2007888.

[2] Дэниел Дж. Бернштейн, Питер Биркнер, Марк Джой, Таня Ланге и Кристиан Петерс (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: несколько имен: список авторов (связь)

[3] Кацуюки Окея, Хироюки Куруматани и Коичи Сакураи (2000). Эллиптические кривые с формой Монтгомери и их криптографические приложения. Криптография с открытым ключом (PKC2000). Дои:10.1007/978-3-540-46588-1_17.CS1 maint: несколько имен: список авторов (связь)

[1]

[2]

[3]