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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 101
При x
1
= x
2
аналогичная формула имеет вид:
x
+
=
(x
2
1
− A)
2
− 4B(2x
1
+ C)
4(x
3
1
+ Cx
2
1
+ Ax
1
+ B)
(5.63)
x
+
=
(x
2
1
− A)
2
4(x
3
1
+ Cx
2
1
+ Ax
1
)
Доказательство. Выпишем формулу для выражения x
+
:
x
+
= g ·
(
y
2
− y
1
x
2
− x
1
)
2
− C − x
1
− x
2
(5.64)
Домножим обе части на (x
2
− x
1
)
2
и выполним преобразования,
исключая gy
2
1
и gy
2
2
с использованием формулы (5.61) и приводя подобные
члены:
x
+
(x
2
− x
1
)
2
= g(y
2
− y
1
)
2
− (C + x
1
+ x
2
)(x
2
− x
1
)
2
=
= −2g · y
1
y
2
+ x
1
x
2
(x
1
+ x
2
+ 2C) + x
1
+ x
2
) =
g(x
2
y
1
− x
1
y
2
)
2
− B(x
2
1
+ x
2
2
)
x
1
x
2
Аналогично,
x
−
(x
2
− x
1
)
2
=
g(x
2
y
1
+ x
1
y
2
)
2
− B(x
2
1
+ x
2
2
)
x
1
x
2
Перемножая обе формулы и деля результат на (x
2
− x
1
)
4
, получим
x
+
x
−
=
(x
2
1
− A)
2
− 4B(x
1
+ x
2
+ C))
(x
2
− x
1
)
2
(5.65)
Теорема доказана.
Идея использования формул (5.65) состоит в том, что имея координаты
точек P
1
, P
2
и P
1
− P
2
можно вычислить координаты точки P
1
+ P
2
быстрее, чем просто вычисляя сумму P
1
+P
2
. При этом координату y можно
не рассматривать, поскольку вычисление формулы для координаты x не
содержат y .
Для того, чтобы уменьшить число операций инвертирования, надо
использовать проективные координаты, однако, координату Y можно
Глава 3. Эллиптические кривые                                                     101

      При x1 = x2 аналогичная формула имеет вид:

                                (x21 − A)2 − 4B(2x1 + C)
                           x+ =                                                (5.63)
                                 4(x31 + Cx21 + Ax1 + B)

                                          (x21 − A)2
                               x+ =
                                    4(x31 + Cx21 + Ax1 )
      Доказательство. Выпишем формулу для выражения x+ :
                          (         )2
                            y2 − y1
                 x+ = g ·              − C − x 1 − x2                          (5.64)
                            x2 − x1

      Домножим обе части на (x2 − x1 )2 и выполним преобразования,
исключая gy12 и gy22 с использованием формулы (5.61) и приводя подобные
члены:

         x+ (x2 − x1 )2 = g(y2 − y1 )2 − (C + x1 + x2 )(x2 − x1 )2 =

                                                   g(x2 y1 − x1 y2 )2 − B(x21 + x22 )
= −2g · y1 y2 + x1 x2 (x1 + x2 + 2C) + x1 + x2 ) =
                                                                 x1 x2
     Аналогично,

                         g(x2 y1 + x1 y2 )2 − B(x21 + x22 )
         x− (x2 − x1 ) =
                      2
                                       x1 x2

      Перемножая обе формулы и деля результат на (x2 − x1 )4 , получим

                   (x21 − A)2 − 4B(x1 + x2 + C))
         x+ x− =                                                               (5.65)
                              (x2 − x1 )2
      Теорема доказана.

      Идея использования формул (5.65) состоит в том, что имея координаты
точек P1 , P2 и P1 − P2 можно вычислить координаты точки P1 + P2
быстрее, чем просто вычисляя сумму P1 + P2 . При этом координату y можно
не рассматривать, поскольку вычисление формулы для координаты x не
содержат y .
      Для того, чтобы уменьшить число операций инвертирования, надо
использовать проективные координаты, однако, координату Y                     можно

Страницы