Групповой закон. 
Криптографические методы защиты информации

На множестве точек эллиптической кривой ?_а, ь можно определить структуру аддитивной абелевой группы. Для этого рассмотрим два вектора (Xi: У: Z) и (Х₂: Y₂: Z₂), удовлетворяющие равенству (9.11).

Будем считать, что вектор (Xi: -Y: Z) является обратным к вектору (Х-[: Y: Z). Далее, если два рассматриваемых вектора принадлежат одной точке эллиптической кривой (в этом случае найдется элемент d ^ О такой, что Х2 = dX 1, Y2 = dY, Zj = dZ), то мы можем определить вектор (Х3: У3: Z3), также удовлетворяющий равенству (9.11), следующим образом:

В противном случае, когда рассматриваемые векторы принадлежат разным точкам кривой, определим.

Соотношения (9.19) принято называть операцией «сложения» двух точек эллиптической кривой, а соотношения (9.18) операцией «удвоения» точки эллиптической кривой. Для записи групповой операции на множестве точек эллиптической кривой, как правило, используется символ +.

Несмотря на то что приведенные соотношения достаточно громоздки, они могут быть эффективно вычислены на ЭВМ. Мы предоставляем заинтересованному читателю самостоятельно проверить, что соотношения (9.18), (9.19) действительно задают на множестве точек эллиптической кривой структуру аддитивной абелевой группы. В частности, легко проверить, что.

Для эллиптической кривой, заданной в аффинной форме записи (9.12), приведенные соотношения принимают простой и хорошо известный вид. Воспользовавшись (9.14), обозначим.

Тогда соотношения (9.18), (9.19) принимают вид.

где, А = для соотношений (9.18) и, А = ³^,^+а для соотно;

Х‘2 Х 1.

шений (9.19). Легко проверить, что величины х^.уз, определенные соотношениями (9.22), удовлетворяют равенствам.

Пусть Р — произвольная точка эллиптической кривой ?_азадан на>1 в проективной или аффинной форме. Определим операцию «скалярного умножения»⁵ натурального числа т на точку Р равенством.

Для вычисления точки [т]Р необязательно последовательно выполнять т операций сложения. Представим натуральное число гп в виде.

и воспользуемся хорошо известным двоичным алгоритмом.

Алгоритм 9.1 (Алгоритм «скалярного умножения»).

Вход: Представление натурального числа тп в виде т = Y^= о^т*2^г и точка эллиптической кривой Р.

Выход: Точка эллиптической кривой Q = [тР.

• 1. Определить точку Q равенством Q = Р.
• 2. Для всех г от г — 1 до 0 выполнить:
• 2.1. Определить Q = [2]Q.
• 2.2. Если nrii = 1, то вычислить Q = Q + Р. ?

Отметим, что при реализации приведенного алгоритма на шаге 2.1 используются соотношения (9.18), используемые для удвоения точки, а на шаге 2.2. — соотношения (9.19).

Упражнение 9.4.1. Покажите, что трудоемкость алгоритма «скалярного умножения» оценивается величиной 0(og₂m) операций «сложения» и «удвоения» точек эллиптической кривой.

^;> В отечественной литературе для данной операции также используются понятия «вычисление кратной точки» или, по аналогии с мультипликативной группой ноля, «возведение в степень».

Если поле К конечно, то группа точек эллиптической кривой ?_а^ь также конечна. Порядок этой группы мы будем обозначать символом €_а, ь- Верна следующая теорема.

Теорема 9.11 (Хассе, см. [6]). Пусть р — простое число и поле К = GF (p). Пусть ?_ах эллиптическая кривая, тогда

Для группы точек эллиптической кривой мы можем определить следующую задачу.

Определение 9.14. Пусть Е_а<�р — эллиптическая кривая и заданы две точки P, Q е ?_а)ь такие, что

для некоторого натурального числа х. Задача вычисления неизвестного значения х по известным значениям точек Р, Q называется задачей дискретного логарифмирования в группе точек эллиптической кривой.

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