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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 86
который соответствует точке в проективных координатах. Выигрыш при
использовании проективных координат достигается тем, что при выполнении
операций удвоения или суммирования при вычислении λ по формулам
(5.41) мы ищем обратный элемент, а просто домножаем каждую координату
(X, Y, Z) на этот знаменатель. Уравнение (5.34) перепишется в проективных
координатах как
Y
2
Z = X
3
+ aXZ
2
+ bZ
3
, (5.42)
Бесконечно удаленной точки ∞ будет соответствовать класс (0, 1, 0)
проективной плоскости. Если P = (X, Y, Z) ̸= ∞, тогда сопоставляя
точке P точку X/Z, Y/Z , получим взаимно-однозначное соответствие
между точками между точками кривой в афинных координатах и классами
проективной ЭК.
Для получения формул сложения и удвоения точек в проективных
координатах подставим в формулы (5.34) вместо x
1
и y
1
выражения X
1
/Z
1
и Y
1
/Z
1
соответственно.
Для формул удвоения получим
λ = (3x
2
+ a)/2y = (3X
2
+ aZ
2
)/2Y
1
Z
1
= A
1
/B
1
,
x
2
= λ
2
− 2X
1
/Z
1
= A
2
1
/B
2
1
− 2X
1
/Z
1
y
2
= λ(3X
1
/Z
1
− λ
2
) − Y
1
/Z
1
= A
1
(3X
1
Y
1
B
1
− A
2
1
)/B
3
1
− Y
1
/Z
1
(5.43)
где A
1
= 3X
2
1
+ aZ
2
1
, B
1
= 2Y
1
Z
1
.
Общий знаменатель для координат x
2
и y
2
равен B
3
1
= 8Y
3
1
Z
3
1
,
поэтому для исключения знаменателя домножим координаты x
2
и y
2
на
этот множитель. Получим формулы для вычисления координат удвоенной
точки в проективных координатах, не использующие вычисления обратного
элемента:
A
1
= 3X
2
1
+ aZ
2
1
, B
1
= 2Y
1
Z
1
X
2
= B
1
(A
2
1
− 4X
1
Y
1
B
1
)
Y
2
= A
1
(6X
1
Y
1
B
1
− A
2
1
) − 4Y
2
1
B
2
1
Z
2
= B
3
1
(5.44)
Выпишем последовательность операций для вычисления координат
удвоенной точки и подсчитаем необходимое количество операций умножения
Глава 3. Эллиптические кривые                                               86

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

               Y 2 Z = X 3 + aXZ 2 + bZ 3 ,                              (5.42)

Бесконечно удаленной точки ∞ будет соответствовать класс (0, 1, 0)
проективной плоскости. Если P = (X, Y, Z) ̸= ∞, тогда сопоставляя
точке P точку X/Z, Y /Z , получим взаимно-однозначное соответствие
между точками между точками кривой в афинных координатах и классами
проективной ЭК.
       Для получения формул сложения и удвоения точек в проективных
координатах подставим в формулы (5.34) вместо x1 и y1 выражения X1 /Z1
и Y1 /Z1 соответственно.
     Для формул удвоения получим
  
  
          2             2    2
   λ = (3x + a)/2y = (3X + aZ )/2Y1 Z1 = A1 /B1 ,
    x2 = λ2 − 2X1 /Z1 = A21 /B12 − 2X1 /Z1                               (5.43)
  
  
   y2 = λ(3X1 /Z1 − λ2 ) − Y1 /Z1 = A1 (3X1 Y1 B1 − A2 )/B 3 − Y1 /Z1
                                                      1    1

где A1 = 3X12 + aZ12 , B1 = 2Y1 Z1 .
       Общий знаменатель для координат x2 и y2 равен B13 = 8Y13 Z13 ,
поэтому для исключения знаменателя домножим координаты x2 и y2 на
этот множитель. Получим формулы для вычисления координат удвоенной
точки в проективных координатах, не использующие вычисления обратного
элемента:
       
       
         A1 = 3X12 + aZ12 , B1 = 2Y1 Z1
       
       
        X = B (A2 − 4X Y B )
            2    1   1       1 1 1
                                                                         (5.44)
       
         Y2 = A1 (6X1 Y1 B1 − A21 ) − 4Y12 B12
       
       
       
          Z2 = B13
       Выпишем последовательность операций для вычисления координат
удвоенной точки и подсчитаем необходимое количество операций умножения

Страницы