Эффективные вычисления на кривых Гаусса

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:43, 7 ноября 2015.
Эффективные вычисления на кривых Гаусса
AlgebraicCryptanalysis.png
Авторы Reza R. Farashahi[@: 1] и
Marc Joye[@: 2]
Опубликован 2010 г.
Сайт Computer science research laboratory
Перевели ‎Constantine Pervov
Год перевода 2015 г.
Скачать оригинал


Эффективные вычисления на кривых Гаусса

Аннотация. Эта статья рассматривает обобщенную форму кривых Гаусса. Семейство обобщенных кривых Гаусса покрывает более изоморфные классы эллиптических кривых. Для конечного поля , показана эквивалентность семейству эллиптических кривых с торсионной подгруппой изоморфной . Эта статья представляет эффективные унифицированные формулы сложения для обобщенных кривых Гаусса. Особенность формул в их полноте для соответственно выбранных параметров.

Эта статья также представляет очень быстрые формулы сложения для обобщенных бинарных кривых гаусса. Самые быстрые проективные формулы сложения требуют , где – стоимость умножения поля, а – стоимость возведения поля в квадрат. Более того, формулы дифференциального сложения и удвоения, которые при условии, что нужно только , при выборе кривой с небольшими параметрами кривизны, очень быстры.

Ключевые слова: Эллиптические кривые, кривые Гаусса, криптография.

Введение

Эллиптическая кривая над полем может быть задана уравнением Вейерштрасса: , где коэффициенты . Коблитц [1] и Миллер [2] были первыми, кто показал, что группа рациональных точек на эллиптической кривой над конечным полем могут быть использованы для проблемы дискретного логарифма в криптосистеме с открытым ключом.

Существует множество других методов представления эллиптических кривых, например, уравнение Лежандра, кубические уравнения, уравнения 4 степени и пересечение двух плоскостей 4 степени [3][4][5]. Несколько форм эллиптических кривых над конечными полями с несколькими координатными системами были изучены для усовершенствования эффективности и скорости вычислений на законе группы (в основном, формулы сложения и удвоения) [3][6].

Некоторые унифицированные формулы сложения, которые так же работают для точечного удвоения, были представлены для нескольких форм эллиптических кривых, смотрите, например [7][8][9][10][11][12]. Обзоры могут быть найдены [3][13]. Более того, завершенные формулы сложения, которые работают для всех пар входных значений, были представлены для кривых Эдвардса над нечетными характеристическими полями [12], и для бинарных кривых Эдвардса [14].

Кривая Гаусса над полем F определена симметричным кубическим уравнением: , где и . Использование кривых Гаусса в криптографии было изучено в [15][7][16][17][18]. Формулы сложения Гауссиан, или формулы Сильвестра, могут тоже быть использованы для точечного удвоения после перестановки входных координат, обеспечивая слабую форму унификации. Более того, те же формулы могут быть использованы для удвоения, сложения, и вычитания точек, которые делают кривые Гаусса интересными по отношению к атакам по сторонним каналам.

В этой статье, мы рассматриваем семейство кривых, обозначаемых как обобщенные кривые Гаусса над полем F, определенным уравнением , где , и . Конечно, это семейство покрывает более изоморфные классы эллиптических кривых, чем кривые Гаусса. Отметим, что формула сложения Сильвестра работает для семейства обобщенных Гауссиан. Но эти формулы не унифицированы. Из формул Сильвестра и после подходящих преобразований входных координат, мы представляем быстрые и эффективные унифицированные формулы сложения для обобщенных кривых Гаусса.

Тем не менее, унифицированные формулы для кривых Гаусса не завершены. Другими словами, есть исключительные случаи, когда формулы не дают результата на выходе. Мы изучили исключения формул сложения для обобщенных кривых Гаусса. Мы обнаружили, что унифицированные формулы завершены для большинства обобщенных кривых Гаусса, то есть, формулы сложения работают для всех пар на входе. В частности, группа -рациональных точек на обобщенной кривой Гаусса имеет завершенные формулы сложения, если, и только если, не является кубом в . Также, унифицированные формулы действительны для всех входных точек в рациональных подгруппах обобщенных кривых Гаусса над конечным полем всякий раз, когда

Для обобщенных бинарных кривых Гаусса, унифицированные формулы сложения являются самыми быстрыми и известными формулами сложения на бинарных эллиптических кривых; например, для расширенного проективного сложения, для смешанного афинно-проектного сложения, и для смешанного сложения и умножения, когда кривые выбраны с маленькими параметрами. Как обычно, мы используем для обозначения поля умножения и для обозначения поля возведения в квадрат. К тому же, формулы сложения завершены для обобщенных кривых гаусса над когда не куб в . Смешанные формулы дифференциального сложения и удвоения так же завершены.

Заметка. В [3], Бернштейн, Коэль, и Ланж определили скрученную форму Гауссианы. Скрученная форма похожа на вышесказанную форму, вплоть до порядка координат. Обе формы имеют преимущества. Нейтральный элемент в скрученной форме является конечной точкой. В афинных координатах, обобщенная форма более симметрична и имеет более простую инверсию. Смотрите также [19].

Обобщенные кривые Гаусса

Кривая Гаусса над полем задана кубическим уравнением: , для некоторых при [20]. Эта глава рассматривает семейство обобщенных кривых Гаусса, которые покрывают более изоморфные классы эллиптических кривых, чем кривые Гаусса. Как будет показано далее, это семейство предоставляет эффективные унифицированные формулы сложения. Более того, унифицированные формулы завершены для некоторых обобщенных кривых Гаусса, то есть формулы сложения работают для всех входных пар.

Определения

TemplateDifinitionIcon.svg Определение «Определение 1.»
Пусть будут элементами , при этом и . Обобщенная кривая Гаусса над полем определяется уравнением:

Очевидно, что кривая Гаусса является обобщенной кривой Гаусса при . Более того, обобщенная кривая Гаусса над , с помощью преобразования определенного как: и (1). C , изоморфна над к кривой Гаусса . Следовательно, для -инварианта мы имеем (2). Мы видим, что кривая над изоморфна к кривой над если . Другими словами, обобщенная кривая Гаусса над изоморфна над кривой Гаусса если, и только если является кубом в . Легко адаптировать формулы сложения и умножения для обобщенных кривых Гаусса (смотрите, например, [19], также известные формулы Сильвестра). Сумма двух (разных) точек на есть точка , где и (3). Удвоение точки , где и (4), Кроме того, инверсия точки на есть точка .

Проективное замыкание кривой есть: . Она имеет точки c при бесконечности. Нейтральный элемент группы -рациональных точек кривой есть точка при бесконечности , которую мы обозначили . Для точки на мы имеем .

Сложение точек. Используя формулу сложения (3) всякий раз, когда определена, сумма точек на есть с (5). Стоимость алгоритмов сложения точек в [15][7][16] будет равна . Более того, эти формулы сложения могут быть выполнены параллельно, смотрите [16]. В частности, можно выполнить формулы сложения (5) параллельно, используя (3), (4) или 6 процессы со стоимостью или , соответственно. Чтобы увеличить скорость, можно использовать расширенные координаты . Алгоритм сложения в [18] использует данную модифицированную систему координат для кривых Гаусса над полем с характеристикой . Этот алгоритм требует .

Удвоение точек. Удвоение точки на есть точка , где (6). Из алгоритма удвоения в [15] имеем, что следующий алгоритм требует , где - стоимость умножения на константу : . (7) Более того, стоимость следующего алгоритма удвоения для кривых над полем с характеристикой равна : . (8) Также, можно изменить формулы удвоения (6) со стоимостью , где обозначает поле куба. Более того, для кривых Гаусса над полем с характеристикой , алгоритмы удвоения в [17][18] используют расширенные координаты, которые требуют .

Универсальность модели

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

TemplateTheoremIcon.svg Теорема Теорема 1.
Пусть будет эллиптической кривой над полем . Если группа имеет точку порядка 3, тогда изоморфна над полем к обобщенной кривой Гаусса. Более того, если имеет элемент с , тогда группа имеет точку порядка 3 если и только если изоморфна над полем к обобщенной кривой Гаусса.
Доказательство

Отметим, что эллиптическая кривая над имеет точку порядка 3 если и только если она имеет модель Вейерштрасса (смотрите пример [21]). Пусть с . Пусть будет характеристикой .

  1. Элемент нумерованного списка

Если , то эллиптическая кривая c помощью преобразования , где , изоморфна над к обобщенной кривой Гаусса с и . С другой стороны, обобщенная кривая Гаусса изоморфна над полем к кривой Вейерштрасса с .

  1. Элемент нумерованного списка

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


Замечание 1. Рассмотрим эллиптическую кривую определенную в доказательстве Теоремы 1. Если и , является кубом в , то пусть и , где . Тогда, преобразование , где будет изоморфизмом над F между и .

TemplateTheoremIcon.svg Теорема Теорема 2.
Пусть будет эллиптической кривой над финитным полем . Тогда, группа имеет точку порядка 3 если и только если изоморфна над к обобщенной кривой Гаусса.
Доказательство

Доказательство. Если . Тогда, каждый элемент будет кубом. Если эллиптическая кривая имеет -рациональную точку порядка 3, тогда Замечание 1 обеспечит изоморфизм между и обобщенной кривой Гаусса. Более того, каждая обобщенная кривая Гаусса над имеет точку порядка 3, где (смотреть Главу 4).


Унифицированные формулы сложения

Пусть будет обобщенной кривой Гаусса над . Напоминаем, что формулы сложения (5) не работают для удвоения точки. В дальнейшем мы дадим несколько унифицированных формул сложения для где формулы удвоения могут быть получены прямо из формул сложения. Унифицированные формулы сложения делают обобщенные кривые Гаусса интересными против атак по сторонним каналам [3][13].

Пусть и будут двумя точками . Пусть также с . Обозначив и , получаем и . Очевидно, что . Вычисляя , мы используем формулы сложения (5) с входными значениями . Делая это, мы видим, что сумма точек на есть точка , где . (9)

Эти формулы работают для удвоения, то есть, они являются унифицированными формулами сложения. Мы отмечаем это с помощью замены порядка точек в формулах сложения (9), которое можно получить следующими унифицированными формулами: . (10)

Следующий алгоритм оценивает формулы сложения (9) с , где обозначает умножение на константу , которая может быть мала: . (11)

Оказывается, что смешанное сложение требует , положив . Более того, формулы сложения (9) могут быть выполнены параллельно, идентично алгоритму для формул сложения (5) в [16].

Когда имеет характеристику , можно использовать модифицированную систему координат, показанную в [18]. Применяя это к формулам сложения (9), сумма двух точек на представленная и с , будет точкой представленной , где . Этот алгоритм требует , где представляет два умножения на константу , которая может быть мала. Более того, формулы смешанного сложения могут быть получены, установив , которые требуют .

Формулы полного сложения

Снова, допустим, что обозначает обобщенную кривую Гаусса над . В этой главе, мы изучим исключительные случаи формул сложения (5), (9) и (10). В частности, мы покажем, что формулы сложения (9), (10) работают для всех пар -рациональных точек на всякий раз, когда не является кубом в .

Рассмотрим набор -рациональных точек при бесконечности на обозначаемый как, .

Отметим, что является подгруппой группы -рациональных точек при бесконечности на . В дальнейшем, будет являться подгруппой 3-торсионной группы , где .

Пусть будут набором -рациональных точек с , соответственно. А именно, . Ясно, что разделен на . Следующие утверждения описывают исключительные случаи формул сложения (5).


Утверждение 1. Формулы сложения (5) работают для всех пар точек на если и только если не являются точкой на бесконечности.

Доказательство. Пусть будут точками на . Сначала, предположим, что формулы сложения (5) не работают для входных значений , то есть, имеем , где . Выделим два случая, чтобы показать, что .

1 Элемент нумерованного списка Если , тогда . Видим, что , поскольку . Итак, . Это значит, что лежат в бесконечности. Следовательно, будет точкой на бесконечности.

2 Элемент нумерованного списка Предположим теперь, что . Напишем , где . Из , Получаем . Тогда, . Более того, из уравнения получаем, что . Если , тогда . Далее, предположим, что . Если , тогда . Из , отметим, что . Тогда предполагает, что . Следовательно, во всех случаях, мы получаем и . Итак, мы можем написать , где являются кубическим корнем из 1. Соотношение станет . Если , тогда и таким образом . Если , тогда и . Наконец, если , то и . Проанализировав вышесказанное, мы всегда будем получать, что .

Теперь, мы изучим другое направление. Мы предположим, что где . Тогда , где кубический корень из единицы. Легко увидеть, что формулы сложения (5) не работают для таких .

Отметим, что формулы сложения (5) работают для всех отдельных пар -рациональных входных значений, если кривая над имеет только одну -рациональную точку на бесконечности, то есть, если имеет только один кубический корень из единицы. Это происходит на кривых Гаусса над и, в частности, для бинарных кривых над с нечетными .

Утверждение 2. Формулы сложения (9) работают для всех пар точек на если и только если не принадлежит . Доказательство. Пусть будут точками на . Пусть будет точкой . Пусть . Отметим, что выход формул (9) для пары значений эквивалентен выходу формул (5) для пар точек . Из Утверждения 1, видим, что формулы (9) не работают для пар точек если и только если . Это эквивалентно .

Аналогично, формулы сложения (10) работают для всех пар точек на c . Поскольку наборы пересекаются, если формулы сложения (9) не могут сосчитать сумму двух точек, тогда формулы сложения (10) смогут сделать это. Очевидно, что это верно для перевернутых пар значений. Другими словами, если формулы сложения (9) не работают для пары значений , тогда они работают для пар значений .

Следствие 1. Формулы удвоения (6) для обобщенной кривой Гаусса работают для все пар входных значений.

Доказательство. Формулы удвоения (6) могут быть получены из формул сложения (9), если . Тогда, из Утверждения 2, мы видим, что эти формулы удвоения работают для всех точек на .

Следствие 2. Предположим является подгруппой , которая пересекается с . Тогда, формулы сложения (9) и (10) работают для всех пар точек в .

Доказательство. Очевидно, что и пересекаются. Тогда, Утверждение 2 выводит доказательство.

Далее, мы выразим семейство полных обобщенных кривых Гаусса. Под полной кривой, мы подразумеваем кривую с полными формулами сложения, то есть, кривую над полем с формулами сложения, которые действуют для каждой пары -рациональных точек.

TemplateTheoremIcon.svg Теорема Теорема 3.
Пусть будут элементами , при этом . Пусть будет обобщенной кривой Гаусса над с формулами сложения (9). Тогда, будет полной над если и только если не является кубом в .
Доказательство

Из определения , мы видим, что набор -рациональных точек будет пустым если и только если не является кубом в . Из Утверждения 2, формулы сложения (9) работают для всех пар -рациональных точек если и только если набор -рациональных точек пуст, что завершает доказательство.


Ниже, мы даем два примера обобщенных кривых Гаусса над финитным полем с полными формулами сложения.

Пример 1. Пусть будут элементами финитного поля с такой, что и не является кубом в . Тогда, обобщенная кривая Гаусса над будет полной с формулами сложения (9) и (10).

Пример 2. Пусть будут элементами поля такими, что и . Пусть будут подгруппой с . Тогда, будет полной над с формулами сложения (9) и (10).

Явные формулы с характеристикой 2

В этой главе, мы представим быстрые и эффективные формулы сложения, удвоения, утроения и дифференциального сложения для обобщенных бинарных кривых Гаусса над полем с характеристикой .

Сложение

Напомним, что стоимость алгоритмов сложения в [15][16] для формул сложения (5) равна . Также, алгоритм сложения (11) требует . Можно выбрать константу маленькой для уменьшения стоимости этого алгоритма до . Далее, алгоритм сложения (11) будет унифицированным. Более того, она является полной для обобщенной бинарной кривой Гаусса над , где четное и не является кубом в . Кроме того, можно использовать расширенные координаты . Сумма двух точек на представленная точками и , где и будет точкой представленной , где , . (13) Этот алгоритм требует , где означают умножение на константу . Отмечаем, что алгоритм (13) получен из формул сложения (9), таким образом он является унифицированным и работает для удвоения точек. Более того, он работает для всех пар входных значений на полной кривой (Теорема 3). Также, смешанные формулы сложения требуют , если положить . Если мала, то можно получить алгоритм сложения параллельно используя 3,4 или 6 процессоров, который потребует или , соответственно.

Стоимость формул сложения для различных типов бинарных эллиптических кривых
Тип кривой Представление Проективное сложение Смешанное сложение
Кривая Вейерштрасса

Проективная [14]

Якоби [6]

Лопез-Дахаб [22][6][23]

Расширенный Лопез-Дахаб

При [22][6][23]

При [22][6][23][24]

14M+1S+1D

14M+5S+1D

13M+4S


14M+3S

13M+3S

11M+1S+1D

10M+3S+1D

8M+5S+1D


9M+4S+1D

8M+4S

Бинарная кривая Эдвардса

Проективная [14]

Проективная

При

18M+2S+17


16M+1S+4D

13M+3S+3D


13M+3S+3D

Кривая Гаусса

Проективная [15][7][16]

Проективная, формулы (11)

Расширенные, формулы (13)

12M

12M

9M+3S

10M

10M

8M+3S

Обобщенная кривая Гаусса

Проективная [19]

Проективная, формулы (11)

Расширенные, формулы (13)

12M

12M+1D

9M+3S+2D

10M

10M+1D

8M+3S+2D

Таблица 1 показывает сложность формул сложения для различных типов бинарных эллиптических кривых и различных систем координат. Как показано в таблице, обобщенные кривые Гаусса обладают самыми быстрыми формулами сложения для бинарных эллиптических кривых. Более того, наши формулы для кривых Гаусса являются унифицированными. Они полны для многих обобщенных кривых Гаусса. Отметим, что все формулы сложения для кривых Вейерштрасса не всегда унифицированы. Но, бинарные кривые Эдвардса унифицированы и обладают полными формулами.

Удвоение

Напоминаем, что алгоритм удвоения (7) требует для формул удвоения (6). Из формул удвоения (6), мы видим, что удвоение точки на будет точкой с (14) Следующий алгоритм представляет формулы удвоения (14), который требует : . Более того, удвоение точки math>(X_1 : Y_1 : Z_1)</math> на бинарной кривой , используя представление , где , будет точкой представленной , где .

Стоимость этих алгоритмов удвоения равна . Также отмечаем, что координаты могут быть заданы как: .

Следующий алгоритм удвоения требует меньше умножений: , , , .

Алгоритм удвоения выше требует . Этот алгоритм требует если ,math>c</math> мала и если мала. Наши формулы удвоения немного улучшают текущую скорость удвоения на кривых Гаусса. Более того, формулы удвоения для обобщенных кривых Гаусса быстрее, чем формулы удвоения, использующие расширенные координаты в кривой Вейерштрасса, смотрите [3]. Но, они медленнее, чем различные формулы удвоения, использующие представление Якоба [3], представление Лопеза-Дахаба короткой формы Вейерштрасса [3][25][24][14] и проективного представления бинарных кривых Эдвардса [14].

Мы отмечаем, что только полные формулы удвоения представляются бинарными кривыми Эдвардса [14] и обобщенными бинарными кривыми Гаусса (смотрите Следствие 1).

Утроение

Здесь мы покажем быстрые формулы утроения для обобщенных кривых Гаусса. Формулы утроения могут использоваться в двоичных системах счисления, ДСС, смотрите пример [26][27][28]. Для точки на , мы имеем при , .

Для обобщенной бинарной кривой Гаусса, мы предлагаем следующие формулы. Если , пусть . Следующий алгоритм посчитает и требует если или мало), , , , .

Дифференциальное сложение

Сейчас мы разработаем алгоритм дифференциального сложения на бинарной кривой Гаусса используя -координаты, где для точки на бинарной кривой , определена симметричной функцией в выражениях координат . -координаты для дифференциального сложения требуют вычисления данных ; и -координаты для дифференциального удвоения требует вычисления данного . Напоминаем, [29][14], что использование формул дифференциального сложения и удвоения для -координат, можно рекурсивно посчитать за и данных и .

Пусть будет точкой на и пусть . Напишем для . Из формул удвоения (4), мы получаем (15).

Предположим, что будут афинными точками на удовлетворяющие . Напишем при . Используя формулы сложения (3), мы получим .

Далее, мы имеем , (16). Используя афинные формулы, можно достичь быстрых формул проективного и смешанного дифференциального сложения и удвоения. Чтобы ускорить эти формулы, мы рассматриваем -координаты. Напишем , для . Другими словами, . Здесь, . Из (15), получаем Используя формулы (16), мы получили и .

Для получения проективных формул, мы предположили, что определено дробью для . Следующие исключающие формулы дают выход определенный : . (17) Эти формулы требуют . Более того, стоимость смешанного дифференциального сложения с -координатами будет равна при .

Напишем определенной дробью . Тогда, исключающие формулы удвоения (18) требуют . Если , то есть является кривой Гаусса, тогда исключающие формулы удвоения требуют : (19).

В итоге, общая стоимость проективного дифференциального сложения и умножения для -координат требует . Также, формулы смешанного дифференциального сложения и умножения . Для кривых Гаусса , общая стоимость проективного и смешанного сложения и удвоения для -координат равна , соответственно. Более того, если параметр кривой выбран маленьким, тогда общая стоимость проективного и смешанного дифференциального сложения и удвоения для -координат равна , соответственно. Также, из Утверждения 1, можем видеть, что смешанное сложение и удвоения для -координат полное. Таблица 2 показывает стоимость дифференциального сложения и удвоения для различных систем координат на бинарных эллиптических кривых. Из Таблицы 2, мы видим, что наше представление -координатами для обобщенных кривых Гаусса является конкурентно способным с другими представлениями для бинарных эллиптических кривых.

Заключение

В этой статье было рассмотрено семейство обобщенных кривых Гаусса. Это семейство покрывает более изоморфизмные классы эллиптических кривых, чем кривые Гаусса. Для каждой эллиптической кривой над финитным полем найдется точка порядка 3 тогда и только тогда, если изоморфна над к обобщенной кривой Гаусса.

Унифицированные формулы сложения были представлены для обобщенных кривых Гаусса над полем , смотрите формулы (9), (10). В частности, эти формулы являются унифицированными для кривых Гаусса . Формулы являются полными, если не является кубом в .

Стоимость дифференциального сложения и удвоения для семейств бинарных эллиптических кривых
Тип кривой Представление Проективное дифференциальное сложение+умножение Смешанное дифференциальное сложение+умножение
Кривая Вейерштрасса

[30]

[31]

[32]

[32]

7M+5S+1D

6M+5S+1D


7M+4S+1D


6M+5S+2D

5M+5S+1D

5M+5S+1D


5M+4S+1D


5M+5S+2D

Бинарная кривая Эдвардса

[14]

с [14]

8M+4S+4D

7M+4S+2D

6M+4S+4D

5M+4S+2D

Гауссиана

Формулы (17), (19)

7M+4S+2D

5M+4S+2D

Обобщенная кривая Гаусса

Формулы (17), (18)

с маленьким

Формулы (17), (18)

7M+4S+3D


7M+4S+1D

5M+4S+3D


5M+4S+1D

Стоимость проективных формул, использующих алгоритм (11) равна . Также, формулы смешанного сложения требуют . Для обобщенных кривых Гаусса над с характеристикой , проективные формулы сложения (12) используя расширенные координаты стоит . Смешанные формулы требуют .

Когда , обобщенные бинарные кривые Гаусса обеспечивают очень быстрые и эффективные формулы сложения. Проективные формулы (11) требуют и смешанные формулы сложения требуют . Более того, используя расширенные координаты, тогда формулы (13) проективного сложения требуют смешанное сложение требует . Некоторые формулы удвоения и утроения были представлены для обобщенных кривых Гаусса, которые улучшают предыдущие формулы удвоения и утроения на кривых Гаусса. Также, очень хорошо показали себя, представленные в статье, формулы дифференциального сложения и удвоения для обобщенных бинарных кривых Гаусса.

Контакты авторов материала

  1. Macquarie University, Department of Computing, Sydney, NSW 2109, Australia E-mail: reza@science.mq.edu.au
  2. Technicolor, Security Competence Center, 1avenue de Belle Fontaine, 35576 Cesson-Sevigne Cedex, France E-mail: marc.joye@technicolor.com

Примечание

Литература

  1. N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203-209, 1987.
  2. V. S. Miller. Use of elliptic curves in cryptography. In H. C. Williams, editor, CRYPTO'85, volume 218 of LNCS, pages 417-426. Springer, 1986.
  3. 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren.Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.
  4. J. H. Silverman. The Arithmetic of Elliptic Curves. Springer, 1986.
  5. L. C. Washington. Elliptic Curves: Number Theory and Cryptography. CRC Press, 2005.
  6. 6,0 6,1 6,2 6,3 6,4 D. J. Bernstein and T. Lange. Explicit-formulas database. http://www.hyperelliptic.org/EFD/
  7. 7,0 7,1 7,2 7,3 M. Joye and J.-J. Quisquater. Hessian elliptic curves and side-channel attacks. In C . K. Koc, D. Naccache, and C. Paar, editors, CHES 2001, volume 2162 of LNCS, pages 402-410. Springer, 2001.
  8. P.-Y. Liardet and N. P. Smart. Preventing SPA/DPA in ECC systems using the Jacobi form. In C . K. Koc, D. Naccache, and C. Paar, editors, CHES 2001, volume 2162 of LNCS, pages 391-401. Springer, 2001.
  9. O. Billet and M. Joye. The Jacobi model of an elliptic curve and side-channel analysis. In M. P. C. Fossorier, T. Hoholdt, and A. Poli, editors, AAECC-15, volume 2643 of LNCS, pages 34-42. Springer, 2003.
  10. E. Brier and M. Joye. Weierstrass elliptic curves and side-channel attacks. In D. Naccache and P. Paillier, editors, PKC 2002, volume 2274 of LNCS, pages 335-345. Springer, 2002.
  11. E. Brier, I. Dechene, and M. Joye. Unified point addition formulas for elliptic curve cryptosystems. In Embedded Cryptographic Hardware: Methodologies & Architectures, pages 247-256. Nova Science Publishers, 2004.
  12. 12,0 12,1 D. J. Bernstein and T. Lange. Faster addition and doubling on elliptic curves. In K. Kurosawa, editor, ASIACRYPT 2007, volume 4833 of LNCS, pages 29-50. Springer, 2007.
  13. 13,0 13,1 I. F. Blake, G. Seroussi, and N. P. Smart. Advances in Elliptic Curve Cryptography. Cambridge University Press, 2005.
  14. 14,0 14,1 14,2 14,3 14,4 14,5 14,6 14,7 14,8 D. J. Bernstein, T. Lange, and R. R. Farashahi. Binary Edwards curves. In E. Oswald and P. Rohatgi, editors, CHES 2008, volume 5154 of LNCS, pages 244-265. Springer, 2008.
  15. 15,0 15,1 15,2 15,3 15,4 D. V. Chudnovsky and G. V. Chudnovsky. Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Advances in Applied Mathematics, 7(4):385-434, 1986.
  16. 16,0 16,1 16,2 16,3 16,4 16,5 N. P. Smart. The Hessian form of an elliptic curve. In C . K. Koc, D. Naccache, and C. Paar, editors, CHES 2001, volume 2162 of LNCS, pages 118-125. Springer, 2001.
  17. 17,0 17,1 H. Hisil, G. Carter, and E. Dawson. New formul for effocient elliptic curve arithmetic. In K. Srinathan, C. P. Rangan, and M. Yung, editors, INDOCRYPT 2007, volume 4859 of LNCS, pages 138-151. Springer, 2007.
  18. 18,0 18,1 18,2 18,3 H. Hisil, K. K.-H. Wong, G. Carter, and E. Dawson. Faster group operations on elliptic curves. In L. Brankovic and W. Susilo, editors, Australasian Information Security Conference (AISC 2009), volume 98, pages 7-19. Conferences in Research and Practice in Information Technology (CRPIT), 2009.
  19. 19,0 19,1 19,2 J. W. S. Cassels. Lectures on Elliptic Curves. Cambridge University Press, 1991.
  20. O. Hesse. ?Uber die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln. Journal f?ur die reine und angewandte Mathematik, 10:68-96, 1844.
  21. A. Knapp. Elliptic Curves. Princeton University Press, 1992.
  22. 22,0 22,1 22,2 E. Al-Daoud, R. Mahmod, M. Rushdan, and A. Kilicman. A new addition formula for elliptic curves over GF(2n). IEEE Trans. Computers, 51(8):972-975, 2002.
  23. 23,0 23,1 23,2 A. Higuchi and N. Takagi. A fast addition algorithm for elliptic curve arithmetic in GF(2n) using projective coordinates. Inf. Process. Lett., 76(3):101-103, 2000.
  24. 24,0 24,1 K. H. Kim and S. I. Kim. A new method for speeding up arithmetic on elliptic curves over binary fields. Cryptology ePrint Archive, Report 2007/181, 2007.
  25. J. Lopez and R. Dahab. Improved algorithms for elliptic curve arithmetic in GF(2n). In S. E. Tavares and H. Meijer, editors, SAC'98, volume 1556 of LNCS, pages 201-212. Springer, 1999.
  26. V. S. Dimitrov, L. Imbert, and P. K. Mishra. Efficient and secure elliptic curve point multiplication using double-base chains. In B. K. Roy, editor, ASIACRYPT 2005, volume 3788 of LNCS, pages 59-78. Springer, 2005.
  27. R. M. Avanzi, V. S. Dimitrov, C. Doche, and F. Sica. Extending scalar multiplication using double bases. In X. Lai and K. Chen, editors, ASIACRYPT 2006, volume 4284 of LNCS, pages 130-144. Springer, 2006.
  28. C. Doche and L. Imbert. Extended double-base number system with applications to elliptic curve cryptography. In R. Barua and T. Lange, editors, INDOCRYPT 2006, volume 4329 of LNCS, pages 335-348. Springer, 2006.
  29. P. L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation, 48(177):243-264, 1987.
  30. J. Lopez and R. Dahab. Fast multiplication on elliptic curves over GF(2n) without precomputation. In C . K. Koc and C. Paar, editors, CHES '99, volume 1717 of LNCS, pages 316-327. Springer, 1999.
  31. P. Gaudry and D. Lubicz. The arithmetic of characteristic 2 Kummer surfaces. Finite Fields and Applications, 15:246-260, 2009.
  32. 32,0 32,1 M. Stam. On Montgomery-like representationsfor elliptic curves over GF(2n). In Y. Desmedt, editor, Public Key Cryptography, volume 2567 of LNCS, pages 240-253. Springer, 2002. 35. L. C. Washington. Elliptic Curves: Number Theory and Cryptography. CRC Press, 2005.