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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 125
3. Z = (24, 28). Выполним операцию удвоения т.Z : λ = 22, l
2,2
=
9x + y + 4, 2Z = (2; 22), v
4
= x − 2. Отсюда
f
4,P
= f
2
2,P
·
9x + y + 4
x − 2
=
(−11x + y + 13)
2
(9x + y + 4)
(x + 7)
2
(x − 2)
Т.к. n
i
= 1, то выполняем вторую часть шага 3 алгоритма Миллера.
Это вычисление приводит к т.5P = ∞ и l = x − 2, v = 1, откуда
f
5,P
= f
4,P
· (x − 2) =
(−11x + y + 13)
2
(9x + y + 4)
(x + 7)
2
Вычислим значение преобразования Тейта τ(P, Q), взяв Q = (3; 10).
Для этого потребуется вспомогательная точка R. Возьмем, например, R =
Q. Вычислим сумму S = 2Q = (−1; 14). Вычислим функцию Вейля в точках
S и R:
f(S) = f(−1; 14) = 20, f(Q) = f(3; 10) = 10. τ(P, Q) = 20/10( mod 31) = 2.
Снова вычислим значение преобразования Тейта τ( P, Q), взяв R =
2Q. Возьмем, например, R = 2Q = (−1; 14). Вычислим сумму S = 2Q+Q =
(−1, 17). Тогда
f(S) = f(−1; 17) = 23, f(2Q) = 20. τ(P, Q) = 23/20 = 12( mod 31) = 2.
Мы видим, что значение преобразования Тейта зависит от выбора
точки R. Для получения уникального значения необходимо полученное
значение возвести в степень (q
k
− 1)/n. В нашем примере оно равно (31 −
1)/5 = 6. Имеем,
2
6
( mod 31) = 2, 12
6
( mod 31) = 2.
Пример 2. Даны две точки P = (2; 9) и xP = (24; 3). Найти кратное
x на эллиптической кривой y
2
= x
3
+ 11( mod 31) из предыдущего примера.
Решение. Определим функцию f
P, 5
так же, как в предыдущем
примере. Вычислим τ(P, P ), взяв R = (15, 10):
S = P + R = (2; 9) + (15, 10) = (3, 10), f
P, 5
(S) = 30, f
P, 5
(R) = 7,
Спаривание Вейля-Тейта                                                           125

      3. Z = (24, 28). Выполним операцию удвоения т.Z : λ = 22, l2,2 =
9x + y + 4, 2Z = (2; 22), v4 = x − 2. Отсюда
                           9x + y + 4 (−11x + y + 13)2 (9x + y + 4)
         f4,P =    2
                  f2,P   ·           =
                             x−2            (x + 7)2 (x − 2)
      Т.к. ni = 1, то выполняем вторую часть шага 3 алгоритма Миллера.
Это вычисление приводит к т.5P = ∞ и l = x − 2, v = 1, откуда
                                    (−11x + y + 13)2 (9x + y + 4)
         f5,P = f4,P · (x − 2) =
                                              (x + 7)2
      Вычислим значение преобразования Тейта τ (P, Q), взяв Q = (3; 10).
Для этого потребуется вспомогательная точка R . Возьмем, например, R =
Q. Вычислим сумму S = 2Q = (−1; 14). Вычислим функцию Вейля в точках
S и R:

f (S) = f (−1; 14) = 20, f (Q) = f (3; 10) = 10. τ (P, Q) = 20/10( mod 31) = 2.

      Снова вычислим значение преобразования Тейта τ (P, Q), взяв R =
2Q. Возьмем, например, R = 2Q = (−1; 14). Вычислим сумму S = 2Q+Q =
(−1, 17). Тогда

f (S) = f (−1; 17) = 23, f (2Q) = 20. τ (P, Q) = 23/20 = 12( mod 31) = 2.

      Мы видим, что значение преобразования Тейта зависит от выбора
точки R . Для получения уникального значения необходимо полученное
значение возвести в степень (q k − 1)/n. В нашем примере оно равно (31 −
1)/5 = 6. Имеем,

           26 ( mod 31) = 2,       126 ( mod 31) = 2.


      Пример 2. Даны две точки P = (2; 9) и xP = (24; 3). Найти кратное
x на эллиптической кривой y 2 = x3 + 11( mod 31) из предыдущего примера.

      Решение. Определим функцию fP, 5 так же, как в предыдущем
примере. Вычислим τ (P, P ), взяв R = (15, 10):

   S = P + R = (2; 9) + (15, 10) = (3, 10), fP, 5 (S) = 30,     fP, 5 (R) = 7,

Страницы