Математические основы защиты информации. Ишмухаметов Ш.Т - 84 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 3. Эллиптические кривые 85
операцию выполняют с использованием операций сложения, вычитания и
удвоения точки. Для этого надо представить число k в двоичной системе
исчисления k = b
t
b
t−1
... b
0
, b
i
∈ {0, 1}, потом вычислить все точки 2Q, 4Q,
... , 2
t
· Q и подсчитать сумму тех точек 2
i
· Q, для которых b
i
= 1.
Пример. Пусть k = 13. В двоичной системе k = 1 1 0 1
2
, тогда,
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 = AddP oints(B, P );}
}
return B;
}
5.2. Эллиптические кривые в проективных координатах
Нахождение суммы и кратного точек ЭК требует вычисления
обратного элемента в конечном поле. Это трудоемкая операция, требующая
использование обобщенного алгоритма Евклида. Можно однако избавиться
от частого использования этой операции, если рассматривать уравнение
эллиптической кривой в трехмерных проективных координатах. Исходные
координаты называются афинными. Точке P (x, y) в афинных координатах
будет соответствовать класс эквивалентности
(X : Y : Z) = {(kx, ky, k) |k ∈ F
p
, k ̸= 0},
Глава 3. Эллиптические кривые                                              85

операцию выполняют с использованием операций сложения, вычитания и
удвоения точки. Для этого надо представить число k в двоичной системе
исчисления k = bt bt−1 ... b0 , bi ∈ {0, 1}, потом вычислить все точки 2Q, 4Q,
... , 2t · Q и подсчитать сумму тех точек 2i · Q, для которых bi = 1.
      Пример. Пусть k = 13. В двоичной системе k = 1 1 0 12 , тогда,
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 = AddP oints(B, P );}
        }
      return B;
}


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

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

Страницы