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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 90
1. Формулы для удвоения точки в якобиановых координатах
P
2
(X
2
, Y
2
) = 2P
1
(X
1
, Y
1
).
A = 3X
2
1
+ aZ
4
1
, B = 2
[
(X
1
+ Y
2
1
)
2
− X
2
1
− Y
4
1
]
,
X
2
= A
2
− 2B,
Y
2
= A(B − X
3
) − 8Y
4
1
Z
2
= (Y
1
+ Z
1
)
2
− Y
2
1
− Z
2
1
,
(5.50)
Стоимость операции удвоения равна 2M+8S (два умножения и 8
возведений в квадрат). Напомним, что аналогичная операция в обычных
проективных координатах оценивается в 6M+5S.
2. Формулы для сложения точек в якобиановых координатах
P
3
(X
3
, Y
3
) = P
1
(X
1
, Y
1
) + P
2
(X
2
, Y
2
).
A = 2(Z
3
1
Y
2
− Z
3
2
Y
1
), B = Z
2
1
X
2
− Z
2
2
X
1
X
3
= A
2
− 4B
2
− 8Z
2
2
X
1
B
2
,
Y
3
= A(4Z
2
2
X
1
B
2
− X
3
) − 8Z
3
2
Y
1
B
3
Z
3
= 2Z
1
Z
2
B
(5.51)
Стоимость этой операции равна 11M+5S, что немного уступает
сложению в обычных проективных координатах (12M+2S). Значительный
выигрыш в быстродействии достигается при смешанном сложении, когда
первая точка задается в якобиановых координатах, а вторая – в афинных.
3. Формулы для смешанного сложения точек в якобиановых и
афинных координатах
P + Q = (X
1
, Y
1
, Z
1
) + (x
2
, y
2
) = (X
3
, Y
3
, Z
3
).
A = Z
3
1
y
2
− Y
1
, B = Z
2
1
x
2
− X
1
,
X
3
= A
2
− B
3
− 2X
1
B
2
Y
3
= A(X
1
B
2
− X
3
) − Y
1
B
3
,
Z
3
= ((Z
1
+ B)
2
− Z
2
1
− B
2
)/2.
(5.52)
Стоимость последнего сложения равна 7M+4S. Это на 21, 5% меньше,
чем стоимость сложения в обычных проективных координатах.
Глава 3. Эллиптические кривые                                        90

1. Формулы для удвоения точки в якобиановых координатах
      P2 (X2 , Y2 ) = 2P1 (X1 , Y1 ).
                                 [                  ]
  
    A = 3X12 + aZ14 , B = 2 (X1 + Y12 )2 − X12 − Y14 ,
  
  
   X = A2 − 2B,
      2
                                                                  (5.50)
  
   Y2 = A(B − X3 ) − 8Y14
  
  
  
    Z2 = (Y1 + Z1 )2 − Y12 − Z12 ,

      Стоимость операции удвоения равна 2M+8S (два умножения и 8
возведений в квадрат). Напомним, что аналогичная операция в обычных
проективных координатах оценивается в 6M+5S.

2. Формулы для сложения точек в якобиановых координатах
      P3 (X3 , Y3 ) = P1 (X1 , Y1 ) + P2 (X2 , Y2 ).
      
      
        A = 2(Z13 Y2 − Z23 Y1 ), B = Z12 X2 − Z22 X1
      
      
       X = A2 − 4B 2 − 8Z 2 X B 2 ,
           3                       2 1
                                                                  (5.51)
      
        Y3 = A(4Z2 X1 B − X3 ) − 8Z23 Y1 B 3
                      2    2
      
      
      
         Z3 = 2Z1 Z2 B

      Стоимость этой операции равна 11M+5S, что немного уступает
сложению в обычных проективных координатах (12M+2S). Значительный
выигрыш в быстродействии достигается при смешанном сложении, когда
первая точка задается в якобиановых координатах, а вторая – в афинных.

3. Формулы для смешанного сложения точек в якобиановых и
афинных координатах

      P + Q = (X1 , Y1 , Z1 ) + (x2 , y2 ) = (X3 , Y3 , Z3 ).
   
   
    A = Z13 y2 − Y1 , B = Z12 x2 − X1 ,
   
   
    X = A2 − B 3 − 2X B 2
       3                 1
                                                                  (5.52)
   
    Y3 = A(X1 B 2 − X3 ) − Y1 B 3 ,
   
   
   
     Z3 = ((Z1 + B)2 − Z12 − B 2 )/2.

      Стоимость последнего сложения равна 7M+4S. Это на 21, 5% меньше,
чем стоимость сложения в обычных проективных координатах.

Страницы