Эллиптические кривые в проективных координатах

Пусть GF(q), представляет собой конечное поле с характеристикой p. Эллиптическая кривая определяется уравнением

Если характеристика p>3, то это уравнение эквивалентно следующему

(*)

Математическое свойство, которое делает эллиптические кривые полезными для криптографии, состоит в том, что если взять две различных точки на кривой, то соединяющая их хорда пересечет кривую в третьей точке (так как мы имеем кубическую кривую). Зеркально отразив эту точку по оси Х, мы получим еще одну точку на кривой (так как кривая симметрична относительно оси X). Если мы обозначим две первоначальных точки как P и Q, то получим последнюю – отраженную – точку P+Q. Это «сложение» удовлетворяет всем известным алгебраическим правилам для целых чисел.

Нахождение суммы и кратного точек ЭК требует вычисления обратного элемента в конечном поле. Это трудоемкая операция, требующая использование обобщенного алгоритма Евклида. Можно однако избавиться от частого использования этой операции, если рассматривать уравнение эллиптической кривой в трехмерных проективных координатах. Исходные координаты называются афинными. Точке P(x, y) в афинных координатах будет соответствовать класс эквивалентности

(X : Y : Z) = {(kx, ky, k) |k ϵ Fp, k ̸= 0},

который соответствует точке в проективных координатах. Выигрыш при использовании проективных координат достигается тем, что при выполнении операций удвоения или суммирования при вычислении λ по формулам (5.41) мы ищем обратный элемент, а просто домножаем каждую координату

(X, Y,Z) на этот знаменатель. Уравнение (5.34) перепишется в проективных координатах как

(5.42)

Бесконечно удаленной точки ∞ будет соответствовать класс (0, 1, 0) проективной плоскости. Если P = (X, Y,Z) ≠ ∞, тогда сопоставляя точке P точку X/Z, Y/Z, получим взаимно-однозначное соответствие между точками между точками кривой в афинных координатах и классами проективной ЭК. Для получения формул сложения и удвоения точек в проективных координатах подставим в формулы (5.34) вместо x1 и y1 выражения X1/Z1и Y1/Z1 соответственно Для формул удвоения получим

Общий знаменатель для координат x2 и y2 равен поэтому для исключения знаменателя домножим координаты x2 и y2 на этот множитель. Получим формулы для вычисления координат удвоенной точки в проективных координатах, не использующие вычисления обратного элемента:

Выпишем последовательность операций для вычисления координат удвоенной точки и подсчитаем необходимое количество операций умножения и возведения в квадрат элементов поля. Операцию умножения будем обозначать буквой M (от англ. multiplication), а возведение в квадрат буквой S (от англ. squaring). Умножения на небольшую константу и сложения мы не учитываем, поскольку эти операции имеют линейную сложность относительно длины элементов поля в то время, как операции умножения и возведения в квадрат имеют квадратичную сложность относительно длины элементов поля. Операция возведения в квадрат выполняется быстрее, чем операция умножения, и ее сложность составляет примерно от 0,6 до 0,8 от сложности умножения.

Выполним те же расчеты для суммы точек.

Умножая координаты x3 и y3 на общий знаменатель , получим формулы для суммы точек в проективных координатах:

Для более эффективного вычисления выполним следующее преобразование. Обозначим T1 = X1Z2 и T2 = X2Z1 . Тогда

Тогда,

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

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

11. Вычисление кратного kQ заданной точки Q

Поскольку, арифметика эллиптических кривых не содержит прямых

формул для вычисления кратного kQ для заданной точки Q( , ), то эту

операцию выполняют с использованием операций сложения, вычитания и

удвоения точки. Для этого надо представить число k в двоичной системе

исчисления k = ... , ∈ {0, 1}, потом вычислить все точки 2Q, 4Q,

... , · Q и подсчитать сумму тех точек · Q, для которых = 1.

Пример. Пусть k = 13. В двоичной системе k = , тогда,

13Q = 8Q + 4Q + Q. Эту же точку можно вычислить как 16Q − 2Q − Q.

Приведем здесь фрагмент процедуры вычисления кратного kP точки

P , предполагая что процедуры удвоения Double(P) и сложения точек Add-

Points(P,Q) уже определены:

long Mult_k(Point P, long k) {

Point B = P ;

while (k) {

if (k%2 == 0)

{ k/ = 2; B = Double(B);}

else

{ k − −; B = AddPoints(B, P);}

}

return B;

}