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

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

Впервые использовать эллиптические кривые в криптографии предложили Нил Коблиц (Neal Koblitz) и Виктор Мюллер (Victor Muller). За последующие годы появились десятки различных схем и протоколов, использующих вычисления на эллиптических кривых, в частности стандарт Российской Федерации на электронную подпись.

В рамках настоящего учебника мы не сможем изложить все свойства эллиптических кривых и остановимся лишь на тех фактах, которые будут необходимы для понимания и реализации криптографических схем. Заинтересованного читателя мы отправляем к книгам [4, 6], содержащим более подробные сведения.

Основные определения

Пусть К - произвольное поле. Мы будем называть двумерным проективным пространством над нолем К множество векторов

координаты которых принадлежат полю К и не все одновременно равны нулю. Введем на пространстве Р2(К) отношение эквивалентности, задаваемое условием

если существует элемент d Е К, d ф 0, такой, что

Множество векторов, эквивалентных друг другу относительно введенной операции, мы будем называть точкой проективного пространства Р2(К).

Определение 9.12. Пусть характеристика[1] поля К отлична от двух и трех. Рассмотрим элементы а,Ь е К такие, что[1] + 27Ь2 ф 0, а также однородное[3] уравнение

Множество точек проективного пространства Р2(К), удовлетворяющих уравнению (9.11), называется эллиптической кривой, определенной над полем К.

Точка проективного пространства, удовлетворяющая уравнению (9.11), называется точкой эллиптической кривой.

Рассмотрим точку проективного пространства Р2(К), все векторы которой эквивалентны вектору (0:1: 0). Каждый вектор, входящий в данную точку, удовлетворяет однородному уравнению (9.11), и его последняя координата равна нулю. Такую точку принято называть бесконечно удаленной точкой эллиптической кривой и обозначать символом О.

У каждой точки эллиптической кривой ?а^, отличной от О, найдется вектор (х : у : 1), у которого последняя координата равна единице. Такой вектор удовлетворяет уравнению

Определение 9.13. Множество решений уравнения (9.12) вместе с бесконечно удаленной точкой О называется эллиптической кривой, определенной над полем К в аффинной форме записи.

Пары (х, у), удовлетворяющие уравнению (9.12), называются аффинными точка эллиптической кривой.

Легко видеть, ч то каждая пара (х, у), удовлетворяющая (9.12), порождает проективную точку кривой ?aj,. Действительно, для любого отличного от нуля d € К такую точку образует множество векторов

С другой стороны, если мы возьмем произвольную проективную точку (X : У : Z) кривой ?а,ь, отличную от О, то всегда можно выбрать пару

такую, что (ж, у) удовлетворяет равенству (9.12). Соотношения (9.13) и (9.14) задают формулы перехода от проективной формы записи кривой ?aj, к аффинной форме, и обратно.

Рассмотрим теперь произвольный, отличный от нуля элемент hК. Домножим правую и левую части равенства (9.11), определяющего эллиптическую кривую ?а_ь, на К6 и получим

Сделав замену

Полученное равенство определяет заданную параметрами а'. У эллиптическую кривую ?аь'- Такая кривая называется кривой, изоморфной кривой ?„ ь, при этом изоморфизм задается равенствами (9.15).

Рассмотрим еще один параметр эллиптической кривой:

который принято называть j-инвариантом эллиптической кривой. Легко проверить, что для все изоморфные кривые обладают одинаковым j-инвариантом. Действительно, подставляя в (9.16) равенства а' = ah4, У = bh6, получим

Величина j(?a,b) может быть использована для определения коэффициентов эллиптической кривой следующим образом. Пусть к G К* произвольный, отличный от нуля элемент ноля К. Тогда определим коэффициенты эллиптической кривой равенствами

Действительно, легко проверить выполнение равенств

Как видно из равенств (9.17), для каждого отличного от нуля элемента к найдется пара коэффициентов а, Ь, определяющих эллиптическую кривую с заданным значением ^-инварианта. Это позволяет определять эллиптическую кривую не только парой коэффициентов а,Ь, но и парой значений j(?a,b),k G К*.

  • [1] Напомним, что характеристикой ноля К называется наименьшее целое неотрицательное число / такое, что для любого элемента а € К выполнено равенство1а = 0. Так, для поля рациональных чисел Q характеристика равна нулю, а дляконечного поля Fpn, где р - простое число, п - натуральное число, характеристика равна р.
  • [2] Напомним, что характеристикой ноля К называется наименьшее целое неотрицательное число / такое, что для любого элемента а € К выполнено равенство1а = 0. Так, для поля рациональных чисел Q характеристика равна нулю, а дляконечного поля Fpn, где р - простое число, п - натуральное число, характеристика равна р.
  • [3] Напомним, что однородным называется многочлен, все мономы которогоимеют одинаковую степень. В случае уравнения (9.11) все мономы, стоящие вправой и левой частях, имеют третью степень.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >