Эллиптическая кривая

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:31, 19 марта 2016.

Основные асимметричные алгоритмы используют абелевы группы.

Эллиптические кривые - инструмент, с помощью которого можно получить "хорошие" абелевы группы. С его помощью можно получать более стойкие, надежные алгоритмы (например ГОСТ на ЦП (2003 г.))

Описание

Рассмотрим уравнение вида:

- поле, - многочлен степени над полем

Все пары , удовлетворяющие данному уравнению, называются алгебраической' кривой порядка над полем . Любая пара называется точкой. Нас интересуют кривые над конечными полями.

- кривая 2го порядка.

Производная: (вычисляем частные производные чисто формально, как производные степенных рядов)

Пример:

Те точки, в которых хотя бы одна частная производная равна 0, называются особыми точками. Точка , где - алгебраическая кривая, называется особой, если или

TemplateDifinitionIcon.svg Определение «Определение»

Алгебраическая кривая называется гладкой, если все ее точки не являются особыми. Будем рассматривать гладкие кривые 3го порядка, называемые эллиптическими кривыми.

Теорема о представлении в поле

TemplateTheoremIcon.svg Теорема Теорема

Вейерштрасс показал, что любую эллиптическую кривую можно представить в таком виде, если характеристика поля равна , т.е.:

, тогда любая эллиптическая кривая может быть представлена в виде:
, или в таком виде:
Доказательство
Без доказательства


Если , то такую эллиптическую кривую можно представить в виде:

Если и , то любую эллиптическую кривую можно представить в виде:

Далее будем рассматривать этот вид. В криптографии обычно используются поля: или используется наиболее часто.

Дискриминант эллиптической кривой

Можно показать, что: Кривая - гладкая

Инвариант кривой:

для , т.е. для кривой над полем, которой )
TemplateDifinitionIcon.svg Определение «Определение»

Две кривые называются изоморфными, если у них равный инвариант.

Точки эллиптической кривой:

Кроме всех точек, удовлетворяющих , существует точка (бесконечно удаленная точка) аналогия с геометрией. Хотим ввести операцию сложения:

- обратная по сложению (удовлетворяет )

Добавляется еще точка, рассматриваемая отдельно (является нулем):

В общем случае, если кривая имеет вид:

- лежит на той же кривой

Доказательство:

Пусть :

Могут быть следующие случаи:

Введем коэффициент
Тогда

Возьмем

Доказать:

  • Ассоциативность
  • Замкнутость
точки на эллиптической кривой образуют абелеву группу.

Теоретические сведения

TemplateDifinitionIcon.svg Определение «Определение»

Плоской алгебраической кривой называется множество точек, удовлетворяющих уравнению .

TemplateDifinitionIcon.svg Определение «Определение»

Кубическая кривая - плоская алгебраическая кривая, такая, что , где .

TemplateDifinitionIcon.svg Определение «Определение»

Эллиптическая кривая (над полем ) - гладкая кубическая кривая, задаваемая уравнением

Эта формула называется длинной формой Вейерштрасса эллиптической кривой.
TemplateDifinitionIcon.svg Определение «Определение»

Гладкая кривая существующих точек, в которых и , где .

Иными словами, система уравнений

не имеет решения

  • Если , то линейной заменой кривая может быть приведена к виду
  • Если , то кривая может быть приведена к виду - короткая форма Вейерштрасса.

Условие гладкости означает, что многочлен не имеет кратных корней

Другие формы эллиптических кривых

  • Форма Montgomery , условие гладкости:
  • Форма Лежандра , условие гладкости: