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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 88
формулы для суммы точек в проективных координатах:
A = Y
2
Z
1
− Y
1
Z
2
, B = X
2
Z
1
− X
1
Z
2
, C = X
2
Z
1
+ X
1
Z
2
,
D = 2X
1
Z
2
+ X
2
Z
1
, E = Z
1
Z
2
,
X
3
= B(A
2
E − B
2
C),
Y
3
= A(B
2
D − A
2
E) − Y
1
Z
2
B
3
Z
3
= B
3
E
(5.45)
Для более эффективного вычисления выполним следующее
преобразование. Обозначим T
1
= X
1
Z
2
и T
2
= X
2
Z
1
. Тогда
B
2
C = (T
2
− T
1
)
2
(T
2
+ T
1
) = (T
2
− T
1
)
3
+ 2T
2
(T
1
− T
2
)
2
= B
3
+ 2T
2
B
2
B
2
D = (T
2
− T
1
)
2
(T
2
+ 2T
1
) = (T
1
− T
2
)
3
+ 3T
2
(T
1
− T
2
)
2
= B
3
+ 3T
2
B
2
Тогда,
X
3
= B(A
2
E − B
3
− 2B
2
T
2
),
Y
3
= A(3B
2
T
2
+ B
3
− A
2
E) − Y
1
Z
2
B
3
Z
3
= B
3
E
(5.46)
Выпишем последовательность операций при вычислении суммы точек
и оценим количество умножений и возведений в квадрат.
Expression M S
T
0
= Y
1
Z
2
, T
1
= X
1
Z
2
, T
2
= X
2
Z
1
3 0
A = Y
2
Z
1
− T
0
, B = T
2
− T
1
1 0
A
2
= A
2
, B
2
= B
2
, B
3
= B
3
1 2
T
3
= B
2
T
2
, E = Z
1
Z
2
, 2 0
F = A
2
E − B
3
− 2T
3
1 0
X
3
= BF 1 0
Y
3
= A(T
3
− F ) − T
0
B
3
2 0
Z
3
= B
3
E 1 0
Всего 12 2
Рассмотрим также важный для дальнейшего описания случай
смешанного сложения, когда координаты первой точки заданы в
проективных координатах, а второй – в афинных координатах.
Глава 3. Эллиптические кривые                                                        88

формулы для суммы точек в проективных координатах:
 
 
   A = Y2 Z1 − Y1 Z2 , B = X2 Z1 − X1 Z2 , C = X2 Z1 + X1 Z2 ,
 
 
 
 
 
  D = 2X1 Z2 + X2 Z1 , E = Z1 Z2 ,
    X3 = B(A2 E − B 2 C),                                                      (5.45)
 
 
 
   Y3 = A(B 2 D − A2 E) − Y1 Z2 B 3
 
 
 
  Z = B 3E
      3

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

   B 2 C = (T2 − T1 )2 (T2 + T1 ) = (T2 − T1 )3 + 2T2 (T1 − T2 )2 = B 3 + 2T2 B 2
   B 2 D = (T2 − T1 )2 (T2 + 2T1 ) = (T1 − T2 )3 + 3T2 (T1 − T2 )2 = B 3 + 3T2 B 2

Тогда,
     
     
      X3 = B(A E − B − 2B T2 ),
              2     3    2

        Y3 = A(3B 2 T2 + B 3 − A2 E) − Y1 Z2 B 3                               (5.46)
      
      
       Z3 = B 3 E

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

          Expression                              M S
          T0 = Y1 Z2 , T1 = X1 Z2 , T2 = X2 Z1    3   0
          A = Y2 Z1 − T0 , B = T2 − T1            1   0
          A2 = A2 , B 2 = B 2 , B 3 = B 3         1   2
          T3 = B2 T2 , E = Z1 Z2 ,                2   0
          F = A2 E − B3 − 2T3                     1   0
          X3 = BF                                 1   0
          Y3 = A(T3 − F ) − T0 B3                 2   0
          Z3 = B3 E                               1   0
          Всего                                  12 2

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

Страницы