В математике , то кривые Edwards представляют собой семейство эллиптических кривых , изученных Harold Edwards в 2007 году концепцию эллиптических кривых над конечными полями широко используется в эллиптической кривой криптографии . Приложения кривых Эдвардса к криптографии были разработаны Дэниелом Дж. Бернстайном и Таней Ланге : они указали на несколько преимуществ формы Эдвардса по сравнению с более известной формой Вейерштрасса .
Определение
Уравнение кривой Эдвардса над полем K , не имеющим характеристики 2, имеет следующий вид:
для некоторого скаляра . Также следующая форма с параметрами c и d называется кривой Эдвардса:
где c , d ∈ K с cd (1 - c 4 · d ) ≠ 0.
Каждая кривая Эдвардса бирационально эквивалентна эллиптической кривой в форме Вейерштрасса и, таким образом, допускает закон алгебраической группы, как только кто-то выбирает точку, которая будет служить нейтральным элементом. Если K конечно, то значительная часть всех эллиптических кривых над K может быть записана как кривые Эдвардса. Часто эллиптические кривые в форме Эдвардса определяются как имеющие c = 1, без потери общности. В следующих разделах предполагается, что c = 1.
Групповой закон
(См. Также групповой закон кривой Вейерштрасса )
Каждая кривая Эдвардса над полем K характеристики не равной 2 с бирационально эквивалентна эллиптической кривой над тем же полем: , где и точка отображается на бесконечность O . Это бирациональное отображение индуцирует группу на любой кривой Эдвардса.
Закон Эдвардса сложения
На любой эллиптической кривой сумма двух точек задается рациональным выражением координат точек, хотя в общем случае может потребоваться несколько формул, чтобы охватить все возможные пары. Для кривой Эдвардса, принимая нейтральный элемент за точку (0, 1), сумма точек а также дается формулой
Инверсия любой точки является . Точка имеет порядок 2, а точки имеет порядок 4. В частности, кривая Эдвардса всегда имеет точку порядка 4 с координатами в K .
Если d не квадрат в K и, то исключительных точек нет: знаменатели а также всегда отличны от нуля. Таким образом, закон сложения Edwards завершается , когда d не квадрат в K . Это означает, что формулы работают для всех пар входных точек на кривой Эдвардса без исключений для удвоения, без исключения для нейтрального элемента, без исключения для отрицательных элементов и т. Д. [1] Другими словами, он определен для всех пар входные точки на кривой Эдвардса над K, и результат дает сумму входных точек.
Если d - квадрат в K , то одна и та же операция может иметь исключительные точки, т.е. могут быть пары точек такой, что один из знаменателей становится равным нулю: либо или же .
Одной из привлекательных особенностей закона Эдвардса является то, что он сильно унифицирован, то есть его также можно использовать для удвоения точки, что упрощает защиту от атак по побочным каналам . Приведенная выше формула сложения быстрее, чем другие унифицированные формулы, и обладает сильным свойством полноты [1]
Пример закона сложения :
Рассмотрим эллиптическую кривую в форме Эдвардса с d = 2
и точка в теме. Можно доказать, что сумма P 1 с нейтральным элементом (0,1) снова дает P 1 . Действительно, используя приведенную выше формулу, координаты точки, заданной этой суммой, равны:
Аналог по кругу
Чтобы лучше понять концепцию "сложения" точек на кривой, приведем хороший пример классической группы окружностей:
возьмем круг радиуса 1
и рассмотрим на нем две точки P 1 = (x 1 , y 1 ), P 2 = (x 2 , y 2 ). Пусть α 1 и α 2 - такие углы, что:
Сумма P 1 и P 2 , таким образом, определяется суммой «их углов». То есть точка P 3 = P 1 + P 2 - это точка на окружности с координатами (x 3 , y 3 ), где:
Таким образом, формула сложения точек на окружности радиуса 1 выглядит так:
- .
Геометрический смысл сложения точек на кривых Эдвардса
Точки на эллиптической кривой образуют абелеву группу: можно складывать точки и брать целые числа, кратные одной точке. Когда эллиптическая кривая описывается невырожденной кубического уравнения, то сумма двух точек P и Q , обозначается P + Q , имеет непосредственное отношение к третьей точке пересечения между кривой и линией, проходящей через P и Q .
Бирациональное отображение между кривой Эдварда и соответствующей эллиптической кривой переводит прямые линии в конические сечения [2]. Другими словами, для кривых Эдвардса три точки, а также лежать на гиперболе .
Учитывая две различные неидентичные точки , коэффициенты квадратичной формы (с точностью до скаляров) равны:
,
,
В случае удвоения балла обратная точка лежит на конике, который касается кривой в точке . Коэффициенты квадратичной формы, определяющей конику, равны (с точностью до скаляров):
,
,
Проективные однородные координаты
В контексте криптографии однородные координаты используются для предотвращения инверсий полей, которые появляются в аффинной формуле. Чтобы избежать инверсий в исходных формулах сложения Эдвардса, уравнение кривой можно записать в проективных координатах как:
.
Проективная точка соответствует аффинной точке на кривой Эдвардса.
Элемент идентичности представлен . Обратное является .
Формула сложения в однородных координатах имеет вид:
где
Алгоритм
Добавление двух точек на кривой Эдвардса может быть вычислено более эффективно [3] в расширенной форме Эдвардса. , где :
Удвоение
Удвоение может быть выполнено по той же формуле, что и сложение. Удвоение относится к случаю, когда входы ( x 1 , y 1 ) и ( x 2 , y 2 ) равны.
Удвоение очка :
Знаменатели были упрощены на основе уравнения кривой . Дальнейшее ускорение достигается за счет вычисления в виде . Это снижает стоимость удвоения в гомоморфных координатах до 3 M + 4 S + 3 C + 6 a , в то время как общее сложение стоит 10 M + 1 S + 1 C + 1 D + 7 a . Здесь M - умножение полей, S - квадраты полей, D - стоимость умножения на параметр кривой d , а a - сложение полей.
- Пример удвоения
Как и в предыдущем примере для закона сложения, рассмотрим кривую Эдвардса с d = 2:
и точка . Координаты точки находятся:
Таким образом, точка, полученная удвоением P, есть.
Смешанное сложение
Смешанное сложение - это случай, когда известно, что Z 2 равно 1. В таком случае A = Z 1 . Z 2 можно устранить, а общая стоимость уменьшится до 9 M +1 S +1 C +1 D +7 a
Алгоритм
А = Z 1 . Z 2 // другими словами, A = Z 1
В = Z 1 2
С = Х 1 .X 2
D = Y 1 . Y 2
E = d . C . D
F = BE
G = B + E
Х 3 = А . F ((X I + Y 1 ) . (X 2 + Y 2 ) -CD)
У 3 = А . G . (ОКРУГ КОЛУМБИЯ)
Z 3 = С . F . грамм
Утроение
Можно утроить результат, сначала удвоив точку, а затем добавив результат к самому себе. Применяя уравнение кривой, как при удвоении, получаем
Есть два набора формул для этой операции в стандартных координатах Эдвардса. Первый стоит 9 M +- S в то время как вторые потребностях в 7 М +- S . Если отношение S / M очень мало, особенно ниже 2/3, то лучше второй набор, а для больших отношений предпочтительнее первый. [4] Используя формулы сложения и удвоения (как указано выше), точка ( X 1 : Y 1 : Z 1 ) символически вычисляется как 3 ( X 1 : Y 1 : Z 1 ) и сравнивается с ( X 3 : Y 3 : Z 3 )
- Пример утроения
Учитывая кривую Эдвардса с d = 2 и точку P 1 = (1,0), точка 3P 1 имеет координаты:
Итак, 3P 1 = (- 1,0) = P- 1 . Этот результат также можно найти, рассматривая пример удвоения: 2P 1 = (0,1), поэтому 3P 1 = 2P 1 + P 1 = (0, -1) + P 1 = -P 1 .
- Алгоритм
А = Х 1 2
B = Y 1 2
С = (2Z 1 ) 2
D = А + В
E = D 2
F = 2D. (AB)
G = EB.C
H = EA.C
Я = F + H
J = FG
X 3 = GJX1
Y 3 = HIY1
Z 3 = IJZ1
Эта формула стоит 9 M + 4 S
Перевернутые координаты Эдвардса
Бернштейн и Ланге ввели еще более быструю систему координат для эллиптических кривых, названную перевернутыми координатами Эдварда [5], в которой координаты ( X : Y : Z ) удовлетворяют кривой ( X 2 + Y 2 ) Z 2 = ( dZ 4 + X 2 Y 2 ) и соответствует аффинной точке ( Z / X , Z / Y ) на кривой Эдвардса x 2 + y 2 = 1 + dx 2 y 2 с XYZ 0.
Перевернутые координаты Эдвардса , в отличие от стандартных координат Эдвардса, не имеют полных формул сложения: некоторые точки, такие как нейтральный элемент, должны обрабатываться отдельно. Но формулы сложения по-прежнему обладают преимуществом сильной унификации: их можно использовать без изменений, чтобы удвоить балл.
Для получения дополнительной информации об операциях с этими координатами см. Http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html.
Расширенные координаты кривых Эдварда
Есть еще одна система координат, с помощью которой можно представить кривую Эдвардса; эти новые координаты называются расширенными координатами [6] и даже быстрее, чем инвертированные координаты. Для получения дополнительной информации о временных затратах, необходимых для операций с этими координатами, см .: http://hyperelliptic.org/EFD/g1p/auto-edwards.html
Смотрите также
Для получения дополнительной информации о времени выполнения, необходимом в конкретном случае, см. Таблицу затрат на операции в эллиптических кривых .
Заметки
- ^ а б Даниил. Дж. Бернштейн, Таня Ланге, стр. 3, более быстрое сложение и удвоение эллиптических кривых
- ^ Кристоф Арен; Таня Ланге; Майкл Нериг; Кристоф Ритценталер (2009). «Более быстрое вычисление пары Тейт» . arXiv : 0904.0854 . Bibcode : 2009arXiv0904.0854A . Проверено 28 февраля 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Гусейн HiSil, Кеннет Кун-Хо Вонг, Гэри Картер и Ed Dawson. Пересмотр закрученных кривых Эдвардса . В ASIACRYPT 2008, страницы 326–343, 2008
- ^ Бернштейн и др., Оптимизация односкалярного умножения на эллиптической кривой с двойной базой
- ^ Даниэль Дж Бернштейн. Таня Ланге, стр.2, Перевернутые координаты Эдварда
- ^ Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон Более быстрые групповые операции на эллиптических кривых
Рекомендации
- Бернштейн, Даниэль ; Ланге, Таня (2007),Более быстрое сложение и удвоение эллиптических кривых (PDF) CS1 maint: обескураженный параметр ( ссылка )
- Эдвардс, Гарольд М. (9 апреля 2007), "Нормальная форма для эллиптических кривых", Бюллетень Американского математического общества , 44 (3): 393-422, DOI : 10,1090 / s0273-0979-07-01153-6 , ISSN 0002-9904
- Более быстрые групповые операции над эллиптическими кривыми , Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон
- DJBernstein, P.Birkner. Т. Ланге, К. Питерс,Оптимизация односкалярного умножения на эллиптической кривой с двойной базой (PDF)CS1 maint: несколько имен: список авторов ( ссылка )
- Вашингтон, Лоуренс К. (2008), Эллиптические кривые: теория чисел и криптография , дискретная математика и ее приложения (2-е изд.), Chapman & Hall / CRC, ISBN 978-1-4200-7146-7 CS1 maint: обескураженный параметр ( ссылка )
- Бернштейн, Даниэль ; Ланге, Таня, перевернутые координаты Эдвардса (PDF) CS1 maint: обескураженный параметр ( ссылка )
Внешние ссылки
- http://hyperelliptic.org/EFD/g1p/index.html
- http://hyperelliptic.org/EFD/g1p/auto-edwards.html