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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 103
C = 0 :
Сложение:
{
X
+
= Z
−
· ((X
1
X
2
− AZ
1
Z
2
)
2
− 4BZ
1
Z
2
(X
1
Z
2
+ X
2
Z
1
)),
Z
+
= Z
−
· (X
1
Z
2
− Z
1
X
2
)
2
.
(5.70)
Удвоение:
{
X
+
= (X
2
1
− AZ
2
1
)
2
,
Z
+
= 4X
1
Z
1
· (X
2
1
+ AZ
2
1
+ BZ
3
1
).
(5.71)
Сложение при C = 0: 10M + 2S
Удвоение при C = 0: 7M + 3S
Из приведенных формул видно, что в проективных координатах
сокращенные формулы Монтгомери особенно эффективны для операции
удвоения при B = 0.
Пример метода Монтгомери
Приведем пример вычисления кратного 13P точки P , взятый из книги
Крендела и Померанса ([14], с. 331):
13P = (2(2P ) + (2P + P )) + 2(2P + P)
1. 2P = doubleh(P ),
2. 3P = addh(2P, P, P),
3. 4P = doubleh(2P ),
4. 6P = doubleh(3P ),
5. 7P = addh(4P, 3P, P),
6. 13P = addh(7P, 6P, P).
Процедура вычисления кратного метода Монтгомери
Приведем теперь алгоритм Монтгомери для произвольных точек
P (X, Z) и кратного k . Предположим, что k = (k
B
k
B−1
k
0
)
2
–двоичное
разложение множителя k :
Point Mont_Mlt_k(Point P(X,Z), long k){
//————————————————————————–
if(k == 0) return O; // Точка в бесконечности.
Глава 3. Эллиптические кривые                                                  103

      C=0:
              {
                  X+ = Z− · ((X1 X2 − AZ1 Z2 )2 − 4BZ1 Z2 (X1 Z2 + X2 Z1 )),
Сложение:
                  Z+ = Z− · (X1 Z2 − Z1 X2 )2 .
              {                                                           (5.70)
                  X+ =     − AZ12 )2 ,
                         (X12
 Удвоение:                                                                (5.71)
                  Z+ = 4X1 Z1 · (X12 +   AZ12 + BZ13 ).
      Сложение при C = 0: 10M + 2S
      Удвоение при C = 0: 7M + 3S
      Из приведенных формул видно, что в проективных координатах
сокращенные формулы Монтгомери особенно эффективны для операции
удвоения при B = 0.

Пример метода Монтгомери

Приведем пример вычисления кратного 13P точки P , взятый из книги
Крендела и Померанса ([14], с. 331):

                   13P = (2(2P ) + (2P + P )) + 2(2P + P )

      1. 2P = doubleh(P ),
      2. 3P = addh(2P, P, P ),
      3. 4P = doubleh(2P ),
      4. 6P = doubleh(3P ),
      5. 7P = addh(4P, 3P, P ),
      6. 13P = addh(7P, 6P, P ).

Процедура вычисления кратного метода Монтгомери

      Приведем теперь алгоритм Монтгомери для произвольных точек
P (X, Z) и кратного k . Предположим, что k = (kB kB−1 k0 )2 –двоичное
разложение множителя k :

Point Mont_Mlt_k(Point P(X,Z), long k){
//————————————————————————–
      if(k == 0) return O; // Точка в бесконечности.

Страницы