WikiDer > Кривая Якоби - Википедия

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья требует внимания специалиста по математике. Пожалуйста, добавьте причина или разговаривать в этот шаблон, чтобы объяснить проблему со статьей. ВикиПроект по математике может помочь нанять эксперта. (Декабрь 2009 г.) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Кривая Якоби» – Новости · газеты · книги · ученый · JSTOR (Декабрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья может требовать уборка встретиться с Википедией стандарты качества. Нет причина очистки был указан. Пожалуйста помоги улучшить эту статью если вы можете. (Январь 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

В математика, то Кривая Якоби является представлением эллиптическая кривая отличается от обычного (Уравнение Вейерштрасса). Иногда используется в криптография вместо формы Вейерштрасса, потому что она может обеспечить защиту от простой и дифференциальный анализ мощности стиль (SPA) атаки; Действительно, можно использовать общую формулу сложения также для удвоения точки на эллиптической кривой этой формы: таким образом, две операции становятся неотличимыми от некоторой информации из побочного канала.^[1] Кривая Якоби также предлагает более быстрые вычисления по сравнению с кривой Вейерштрасса.

Кривая Якоби бывает двух типов: Перекресток Якоби, который задается пересечением двух поверхностей, а Якоби квартика.

Эллиптические кривые: основы

Учитывая эллиптическую кривую, можно выполнять некоторые «операции» между ее точками: например, можно добавить два очка п и Q получение точки п + Q что принадлежит кривой; учитывая точку п на эллиптической кривой можно «удвоить» P, то есть найти [2]п = п + п (квадратные скобки используются для обозначения [n] P, смысл п добавлен п раз), а также найти отрицание п, что означает найти -п. Таким образом, точки эллиптической кривой образуют группа. Обратите внимание, что единичный элемент групповой операции не является точкой на аффинной плоскости, он появляется только в проективных координатах: тогда О = (0: 1: 0) - «бесконечно удаленная точка», то есть нейтральный элемент в групповой закон. Формулы сложения и удвоения также полезны для вычисления [n] P, то п-я точка, кратная п на эллиптической кривой: эта операция считается самой криптография на основе эллиптических кривых.

Эллиптическая кривая E, через поле K можно поместить в Форма Вейерштрасса у² = Икс³ + топор + б, с а, б в K. Что будет важно позже: по порядку ведения заседания 2, то есть п на E такие, что [2]п = О. Если п = (п, 0) - точка на E, то он имеет порядок 2; в более общем смысле точки порядка 2 соответствуют корням многочлен f (x) = Икс³ + топор + б.

С этого момента мы будем использовать E_{а, б} для обозначения эллиптической кривой с формой Вейерштрасса у² = Икс³ + топор + б.

Если E_{а, б} таков, что кубический многочлен Икс³ + топор + б имеет три различных корня в K мы можем написать E_{а, б} в Нормальная форма Лежандра:

E_{а, б}: у² = х (х + 1) (х + j)

В этом случае мы имеем три точки второго порядка: (0, 0), (–1, 0), (-j, 0). В этом случае мы используем обозначения E [j]. Обратите внимание, что j можно выразить через а, б.

Определение: пересечение Якоби

Эллиптическая кривая в п³(K) можно представить как пересечение из двух квадратичные поверхности:

${ displaystyle Q: {Q_ {1} (X_ {0}, X_ {1}, X_ {2}, X_ {3}) = 0 } cap {Q_ {2} (X_ {0}, X_ {1}, X_ {2}, X_ {3}) = 0 }}$

Можно определить форму Якоби эллиптической кривой как пересечение двух квадрик. Позволять E_{а, б} - эллиптическая кривая в форме Вейерштрасса, применим следующее карта к нему:

${ Displaystyle Phi: (x, y) mapsto (X, Y, Z, T) = (x, y, 1, x ^ {2})}$

Мы видим, что следующие система уравнений держит:

${ displaystyle mathbf {S}: { begin {cases} X ^ {2} -TZ = 0 Y ^ {2} -aXZ-bZ ^ {2} -TX = 0 end {cases}}}$

Кривая E [j] соответствует следующему пересечению поверхности в п³(K):

${ displaystyle mathbf {S} 1: { begin {cases} X ^ {2} + Y ^ {2} -T ^ {2} = 0 kX ^ {2} + Z ^ {2} -T ^ {2} = 0 end {case}}}$.

«Особый случай», E [0], эллиптическая кривая имеет двойную точку и, следовательно, единственное число.

S1 получается путем обращения в E [j] то трансформация:

ψ: E [j] → S1

${ displaystyle (x, y) mapsto (X, Y, Z, T) = (- 2y, x ^ {2} -j, x ^ {2} + 2jx + j, x ^ {2} + 2x + j)}$

${ Displaystyle O = (0: 1: 0) mapsto (0,1,1,1)}$

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

За S1, то нейтральный элемент группы - это точка (0, 1, 1, 1), то есть образ О = (0: 1: 0) при ψ.

Сложение и удвоение

Данный п₁ = (Икс₁, Y₁, Z₁, Т₁) и п₂ = (Икс₂, Y₂, Z₂, Т₂), две точки на S1, то координаты по делу п₃ = п₁ + п₂ находятся:

${ displaystyle X_ {3} = T_ {1} Y_ {2} X_ {1} Z_ {2} + Z_ {1} X_ {2} Y_ {1} T_ {2}}$

${ displaystyle Y_ {3} = T_ {1} Y_ {2} Y_ {1} T_ {2} -Z_ {1} X_ {2} X_ {1} Z_ {2}}$

${ displaystyle Z_ {3} = T_ {1} Z_ {1} T_ {2} Z_ {2} -kX_ {1} Y_ {1} X_ {2} Y_ {2}}$

${ displaystyle T_ {3} = (T_ {1} Y_ {2}) ^ {2} + (Z_ {1} X_ {2}) ^ {2}}$

Эти формулы справедливы и для удвоения: достаточно иметь п₁ = п₂. Таким образом, добавление или удвоение очков в S1 - операции, требующие 16 умножений плюс одно умножение на константу (k).

Также можно использовать следующие формулы для удвоения точки п₁ и найти п₃ = [2]п₁:

${ displaystyle X_ {3} = 2Y_ {1} T_ {1} Z_ {1} X_ {1}}$

${ displaystyle Y_ {3} = (T_ {1} Y_ {1}) ^ {2} - (T_ {1} Z_ {1}) ^ {2} + (Z_ {1} Y_ {1}) ^ { 2}}$

${ displaystyle Z_ {3} = (T_ {1} Z_ {1}) ^ {2} - (T_ {1} Y_ {1}) ^ {2} + (Z_ {1} Y_ {1}) ^ { 2}}$

${ displaystyle T_ {3} = (T_ {1} Z_ {1}) ^ {2} + (T_ {1} Y_ {1}) ^ {2} - (Z_ {1} Y_ {1}) ^ { 2}}$

Используя эти формулы, необходимо 8 умножений, чтобы удвоить очко. Однако есть еще более эффективные «стратегии» удвоения, требующие всего 7 умножений.^[2] Таким образом можно утроить точку с 23 умножениями; действительно [3]п₁ можно получить, добавив п₁ с [2]п₁ со стоимостью 7 умножений для [2]п₁ и 16 для п₁ + [2]п₁^[2]

Пример сложения и удвоения

Позволять K = р или же C и рассмотрим случай:

${ displaystyle mathbf {S} 1: { begin {cases} X ^ {2} + Y ^ {2} -T ^ {2} = 0 4X ^ {2} + Z ^ {2} -T ^ {2} = 0 end {case}}}$

Рассмотрим точки ${ displaystyle P_ {1} = (1, { sqrt {3}}, 0,2)}$ и ${ displaystyle P_ {2} = (1,2,1, { sqrt {5}})}$: легко проверить, что п₁ и п₂ принадлежать S1 (достаточно увидеть, что эти точки удовлетворяют обоим уравнениям система S1).

Используя приведенные выше формулы для добавления двух точек, координаты для п₃, куда п₃ = п₁ + п₂ находятся:

${ displaystyle X_ {3} = T_ {1} Y_ {2} X_ {1} Z_ {2} + Z_ {1} X_ {2} Y_ {1} T_ {2} = 4}$

${ displaystyle Y_ {3} = T_ {1} Y_ {2} Y_ {1} T_ {2} -Z_ {1} X_ {2} X_ {1} Z_ {2} = 4 { sqrt {15}} }$

${ displaystyle Z_ {3} = T_ {1} Z_ {1} T_ {2} Z_ {2} -kX_ {1} Y_ {1} X_ {2} Y_ {2} = - 8 { sqrt {3} }}$

${ displaystyle T_ {3} = (T_ {1} Y_ {2}) ^ {2} + (Z_ {1} X_ {2}) ^ {2} = 16}$

Результирующая точка ${ displaystyle P_ {3} = (4,4 { sqrt {15}}, - 8 { sqrt {3}}, 16)}$.

С помощью приведенных выше формул для удвоения можно найти точку п₃ = [2]п₁:

${ Displaystyle X_ {3} = 2Y_ {1} T_ {1} Z_ {1} X_ {1} = 0}$

${ displaystyle Y_ {3} = (T_ {1} Y_ {1}) ^ {2} - (T_ {1} Z_ {1}) ^ {2} + (Z_ {1} Y_ {1}) ^ { 2} = 12}$

${ displaystyle Z_ {3} = (T_ {1} Z_ {1}) ^ {2} - (T_ {1} Y_ {1}) ^ {2} + (Z_ {1} Y_ {1}) ^ { 2} = - 12}$

${ displaystyle T_ {3} = (T_ {1} Z_ {1}) ^ {2} + (T_ {1} Y_ {1}) ^ {2} - (Z_ {1} Y_ {1}) ^ { 2} = 12}$

Итак, в этом случае п₃ = [2]п₁ = (0, 12, –12, 12).

Отрицание

Учитывая точку п₁ = (Икс₁, Y₁, Z₁, Т₁) в S1, это отрицание это -п₁ = (−Икс₁, Y₁, Z₁, Т₁)

Сложение и удвоение в аффинных координатах

Учитывая две аффинные точки п₁ = (Икс₁, у₁, z₁) и п₂ = (Икс₂, у₂, z₂) их сумма равна точке п₃ с координатами:

${ displaystyle x_ {3} = { frac {y_ {2} x_ {1} z_ {2} + z_ {1} x_ {2} y_ {1}} {(y_ {2} ^ {2} + ( z_ {1} x_ {2}) ^ {2})}}}$

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

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

Эти формулы справедливы и для удвоения с условием п₁ = п₂.

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

Есть еще одна система координат, с помощью которой можно представить точку пересечения Якоби. Дана следующая эллиптическая кривая в форме пересечения Якоби:

${ displaystyle mathbf {S} 1: { begin {cases} x ^ {2} + y ^ {2} = 1 kx ^ {2} + z ^ {2} = 1 end {cases}} }$

то расширенные координаты описать точку п = (х, у, г) с переменными X, Y, Z, T, XY, ZT, куда:

${ displaystyle x = X / T}$

${ displaystyle y = Y / T}$

${ Displaystyle Z = Z / T}$

${ Displaystyle XY = X cdot Y}$

${ Displaystyle ZT = Z cdot T}$

Иногда используются эти координаты, потому что они более удобны (с точки зрения затрат времени) в некоторых конкретных ситуациях. Для получения дополнительной информации об операциях, основанных на использовании этих координат, см. http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html

Определение: квартика Якоби

Якобиевская квартика уравнение ${ displaystyle y ^ {2} = x ^ {4} -1,9x ^ {2} +1}$

Эллиптическая кривая в Якоби квартика форму можно получить из кривой E_{а, б} в форме Вейерштрасса по крайней мере с одним докладом по порядку ведения заседания 2. Следующие трансформация ж отправляет каждую точку E_{а, б} в точку в координатах Якоби, где (X: Y: Z) = (sX: s²Y: sZ).

f: E_{а, б} → J

${ Displaystyle (р, 0) mapsto (0: -1: 1)}$

${ displaystyle (x, y) neq (p, 0) mapsto (2 (x-p) :( 2x + p) (x-p) ^ {2} -y ^ {2}: y)}$

${ Displaystyle О mapsto (0: 1: 1)}$^[3]

Применение ж к E_{а, б}, получается кривая в J следующего вида:

${ displaystyle C: Y ^ {2} = eX ^ {4} -2dX ^ {2} Z ^ {2} + Z ^ {4}}$^[3]

куда:

${ displaystyle e = { frac {- (3p ^ {2} + 4a)} {16}}, d = { frac {3p} {4}}}$.

элементы в K. C представляет собой эллиптическую кривую в Якоби квартика форме в координатах Якоби.

Квартика Якоби в аффинных координатах

Общий вид кривой Якоби квартики в аффинных координатах:

${ displaystyle y ^ {2} = ex ^ {4} + 2ax ^ {2} +1}$,

где часто е = 1 предполагается.

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

Нейтральный элемент группового закона C - проективная точка (0: 1: 1).

Сложение и удвоение в аффинных координатах

Учитывая две аффинные точки ${ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$ и ${ Displaystyle P_ {2} = (x_ {2}, y_ {2})}$, их сумма равна баллу ${ Displaystyle P_ {3} = (x_ {3}, y_ {3})}$, такое, что:

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

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

Как и в случае пересечений Якоби, в этом случае также можно использовать эту формулу для удвоения.

Сложение и удвоение в проективных координатах

Учитывая два очка п₁ = (Икс₁: Y₁: Z₁) и п₂ = (Икс₂: Y₂: Z₂) в C ′, координаты точки п₃ = (Икс₃: Y₃: Z₃), куда п₃ = п₁ + п₂, даны в терминах п₁ и п₂ по формулам:

${ displaystyle X_ {3} = X_ {1} Z_ {1} Y_ {2} + Y_ {1} X_ {2} Z_ {2}}$

${ displaystyle Y_ {3} = left (Z_ {1} ^ {2} Z_ {2} ^ {2} + eX_ {1} ^ {2} X_ {2} ^ {2} right) left ( Y_ {1} Y_ {2} -2dX_ {1} X_ {2} Z_ {1} Z_ {2} right) + 2eX_ {1} X_ {2} Z_ {1} Z_ {2} left ( X_ {1} ^ {2} Z_ {2} ^ {2} + Z_ {1} ^ {2} X_ {2} ^ {2} right)}$

${ displaystyle Z_ {3} = Z_ {1} ^ {2} Z_ {2} ^ {2} -eX_ {1} ^ {2} X_ {2} ^ {2}}$

Эту формулу можно использовать и для удвоения, при условии, что п₂ = п₁: таким образом точка п₃ = п₁ + п₁ = [2]п₁ получается.

Количество умножений, необходимых для сложения двух точек, составляет 13 плюс 3 умножения на константы: в частности, есть два умножения на константу е и один постоянным d.

Есть несколько «стратегий» для сокращения операций, необходимых для сложения и удвоения точек: количество умножений может быть уменьшено до 11 плюс 3 умножения на константы (см. ^[4] раздел 3 для более подробной информации).

Количество умножений можно уменьшить, работая над константами е и d: эллиптическая кривая в форме Якоби может быть изменена, чтобы иметь меньшее количество операций сложения и удвоения. Так, например, если постоянная d в C существенно мало, умножение на d можно отменить; однако лучший вариант - уменьшить е: если она мала, не учитывается не одно, а два умножения.

Пример сложения и удвоения

Рассмотрим эллиптическую кривую E_4,0, в этом есть смысл п порядка 2: п = (п, 0) = (0, 0). Следовательно, а = 4, б = п = 0, поэтому мы имеем е = 1 и d = 1 и ассоциированная форма квартики Якоби:

${ Displaystyle C: Y ^ {2} = X ^ {4} + Z ^ {4}}$

Выбор двух точек ${ displaystyle P_ {1} = (1: { sqrt {2}}: 1)}$ и ${ displaystyle P_ {2} = (2: { sqrt {17}}: 1)}$, можно найти их сумму п₃ = п₁ + п₂ используя формулы для добавления, указанные выше:

${ displaystyle X_ {3} = 1 cdot 1 cdot { sqrt {17}} + { sqrt {2}} cdot 2 cdot 1 = { sqrt {17}} + 2 { sqrt {2 }}}$

${ displaystyle Y_ {3} = left (1 ^ {2} cdot 1 ^ {2} +1 cdot 1 ^ {2} cdot 2 ^ {2} right) left ({ sqrt {2 }} cdot { sqrt {17}} - 2 cdot 0 cdot 1 cdot 2 cdot 1 cdot 1 right) +2 cdot 1 cdot 1 cdot 2 cdot 1 cdot 1 left (1 ^ {2} cdot 1 ^ {2} + 1 ^ {2} cdot 2 ^ {2} right) = 5 { sqrt {34}} + 20}$

${ Displaystyle Z_ {3} = 1 ^ {2} cdot 1 ^ {2} -1 cdot 1 ^ {2} cdot 2 ^ {2} = - 3}$.

Так

${ displaystyle P_ {3} = ({ sqrt {17}} + 2 { sqrt {2}}: 5 { sqrt {34}} + 20: -3)}$.

По тем же формулам точка п₄ = [2]п₁ получается:

${ Displaystyle X_ {3} = 1 cdot 1 cdot { sqrt {2}} + { sqrt {2}} cdot 1 cdot 1 = 2 { sqrt {2}}}$

${ displaystyle Y_ {3} = left (1 + 1 cdot 1 right) left ({ sqrt {2}} cdot { sqrt {2}} - 2 cdot 0 cdot 1 cdot 1 cdot 1 cdot 1 right) +2 cdot 1 left (1 ^ {2} cdot 1 ^ {2} + 1 ^ {2} cdot 1 ^ {2} right) = 8}$

${ Displaystyle Z_ {3} = 1 ^ {2} cdot 1 ^ {2} -1 cdot 1 ^ {2} cdot 1 ^ {2} = 0}$

Так

${ displaystyle P_ {4} = (2 { sqrt {2}}: 8: 0)}$.

Отрицание

Отрицание точки п₁ = (Икс₁: Y₁: Z₁) это: -п₁ = (−Икс₁: Y₁: Z₁)

Альтернативные координаты квартики Якоби

Существуют и другие системы координат, которые можно использовать для представления точки в квартике Якоби: они используются для получения быстрых вычислений в определенных случаях. Для получения дополнительной информации о временных затратах на операции с этими координатами см. http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Учитывая аффинную квартику Якоби

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

то Ориентированный на удвоение XXYZZ координаты ввести дополнительный параметр кривой c удовлетворение а² + c² = 1 и они представляют собой точку (х, у) в качестве (X, XX, Y, Z, ZZ, R), такое, что:

${ displaystyle x = X / Z}$

${ displaystyle y = Y / ZZ}$

${ displaystyle XX = X ^ {2}}$

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

${ Displaystyle R = 2 cdot X cdot Z}$

то Ориентированный на удвоение XYZ координаты, при том же дополнительном предположении (а² + c² = 1), представляют собой точку (х, у) с (X, Y, Z) удовлетворяющие следующим уравнениям:

${ displaystyle x = X / Z}$

${ Displaystyle у = Y / Z ^ {2}}$

С использованием XXYZZ координаты нет дополнительных предположений, и они представляют собой точку (х, у) в качестве (X, XX, Y, Z, ZZ) такой, что:

${ displaystyle x = X / Z}$

${ displaystyle y = Y / ZZ}$

${ displaystyle XX = X ^ {2}}$

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

в то время как Координаты XXYZZR представлять (х, у) в качестве (X, XX, Y, Z, ZZ, R) такой, что:

${ displaystyle x = X / Z}$

${ displaystyle y = Y / ZZ}$

${ displaystyle XX = X ^ {2}}$

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

${ Displaystyle R = 2 cdot X cdot Z}$

с Координаты XYZ смысл (х, у) дан кем-то (X, Y, Z), с:

${ displaystyle x = X / Z}$

${ Displaystyle у = Y / Z ^ {2}}$.

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

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

Примечания

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

• Оливье Билле, Марк Джой (2003). "Модель Якоби эллиптической кривой и анализ боковых каналов". Модель Якоби эллиптической кривой и анализ боковых каналов. Конспект лекций по информатике. 2643. Springer-Verlag Berlin Heidelberg 2003. С. 34–42. Дои:10.1007/3-540-44828-4_5. ISBN 978-3-540-40111-7.
• П.Ю. Лиардет, Н.П. Умная (2001). «Предотвращение SPA / DPA в системах ECC с использованием формы Якоби». Криптографическое оборудование и встроенные системы - CHES 2001. Конспект лекций по информатике. 2162. Springer-Verlag Berlin Heidelberg 2001. С. 391–401. Дои:10.1007/3-540-44709-1_32. ISBN 978-3-540-42521-2.
• http://hyperelliptic.org/EFD/index.html

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

• http://hyperelliptic.org/EFD/g1p/index.html