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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 102
опустить, поскольку координаты X и Z могут быть вычислены, без
использования Y . Общие формулы будут иметь вид:
Формулы Монтгомери в проективных координатах
1. Общий случай gY
2
Z = x
3
+ AX
2
Z + BXZ
2
+ CZ
3
P
1
= (X
1
, Y
1
, Z
1
), P
2
= (X
2
, Y
2
, Z
2
), P
1
+P
2
= (X
+
, Y
+
, Z
+
), P
1
−P
2
= (X
−
, Y
−
, Z
−
)
Случай P
1
̸= P
2
.
{
X
+
= Z
−
· ((X
1
X
2
− AZ
1
Z
2
)
2
− 4B(X
1
Z
2
+ X
2
Z
1
+ CZ
1
Z
2
)Z
1
Z
2
),
Z
+
= Z
−
· (X
1
Z
2
− Z
1
X
2
)
2
.
(5.66)
Случай P
1
= P
2
.
{
X
+
= (X
2
1
− AZ
2
1
)
2
− 4B(2X
1
+ CZ
1
)Z
3
1
,
Z
+
= 4Z
1
· (X
3
1
+ CX
2
1
Z
1
+ AX
1
Z
2
1
+ BZ
3
1
).
(5.67)
Подсчитаем количество операций (умножений M и возведений в
квадрат S в конечном поле), необходимых для вычисления суммы точек и
удвоенной точки:
Сложение по Монтгомери: 11M + 2S
Удвоение по Монтгомери: 10M + 3S
В этих формулах не учтена операции сложения и умножения
на константу 4 которые имеют линейную оценку относительно длины
умножаемых чисел.
2. Частные случаи формул Монгомери
B = 0 :
Сложение:
{
X
+
= Z
−
· (X
1
X
2
− AZ
1
Z
2
)
2
,
Z
+
= Z
−
· (X
1
Z
2
− Z
1
X
2
)
2
.
(5.68)
Удвоение:
{
X
+
= (X
2
1
− AZ
2
1
)
2
,
Z
+
= 4X
1
Z
1
· (X
2
1
+ CX
1
Z
1
+ AZ
2
1
).
(5.69)
Сложение при B = 0: 7M + 2S
Удвоение при B = 0: 4M + 3S
Глава 3. Эллиптические кривые                                                        102

опустить, поскольку координаты X и Z могут быть вычислены, без
использования Y . Общие формулы будут иметь вид:

       Формулы Монтгомери в проективных координатах
1. Общий случай gY2 Z = x3 + AX2 Z + BXZ2 + CZ3

P1 = (X1 , Y1 , Z1 ), P2 = (X2 , Y2 , Z2 ), P1 +P2 = (X+ , Y+ , Z+ ), P1 −P2 = (X− , Y− , Z− )

       Случай P1 ̸= P2 .
 {
     X+ = Z− · ((X1 X2 − AZ1 Z2 )2 − 4B(X1 Z2 + X2 Z1 + CZ1 Z2 )Z1 Z2 ),
                                                                                  (5.66)
     Z+ = Z− · (X1 Z2 − Z1 X2 )2 .

       Случай P1 = P2 .
      {
        X+ = (X12 − AZ12 )2 − 4B(2X1 + CZ1 )Z13 ,
                                                                                  (5.67)
         Z+ = 4Z1 · (X13 + CX12 Z1 + AX1 Z12 + BZ13 ).

       Подсчитаем количество операций (умножений M и возведений в
квадрат S в конечном поле), необходимых для вычисления суммы точек и
удвоенной точки:
       Сложение по Монтгомери: 11M + 2S
       Удвоение по Монтгомери: 10M + 3S
       В этих формулах не учтена операции сложения и умножения
на константу 4 которые имеют линейную оценку относительно длины
умножаемых чисел.

2. Частные случаи формул Монгомери
        B=0:
                   {
                       X+ = Z− · (X1 X2 − AZ1 Z2 )2 ,
  Сложение:                                                                       (5.68)
                       Z+ = Z− · (X1 Z2 − Z1 X2 )2 .
                  {
                       X+ = (X12 − AZ12 )2 ,
  Удвоение:                                                                       (5.69)
                       Z+ = 4X1 Z1 · (X12 + CX1 Z1 + AZ12 ).
       Сложение при B = 0: 7M + 2S
       Удвоение при B = 0: 4M + 3S

Страницы