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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 84
Таким образом, данная кривая содержит 28 точек.
Порядок точки A = ord(A) — это наименьшее натуральное число k
такое, что kA = ∞. Поскольку по теореме Лагранжа порядок любой точки
является делителем порядка группы, то порядок любой точки на кривой из
нашего примера принадлежит множеству {1, 2, 4, 7, 14, 28}.
Пример. Найти сумму точек 3P = (3, −10) и 7P = (11, 3).
Решение. Вычислим λ = (y
2
− y
1
)/(x
2
− x
1
): y
2
− y
1
= 3 − (−10) =
13, x
2
− x
1
= 11 − 3 = 8. Поскольку 8
−1
≡ 3 (mod 23), то λ = 13/8 =
13 ·3 mod 23 = 16. Теперь, x
3
= λ
2
−x
1
−x
2
= (16
2
−3 −11) mod 23 = 12, а
y
3
= λ(x
1
− x
3
) −y
1
= 16(3 − 12) − (−10)) mod 23 = 4.
Ответ: (3, −10) + (11, 3) = (12, 4).
Замечание. При выполнении удвоения точки или вычислении суммы
необходимо вычисление обратного элемента в поле F
q
. Эта операция
выполняется с помощью обобщенного алгоритма Евклида (см.разд.2.5).
Вычисление множества точек эллиптической кривой
Чтобы найти множество точек эллиптической кривой над простым
полем F
p
, можно использовать следующий алгоритм:
for(int x = 0; x < p; x + +){
int t = x(x
2
+ a) + b;
if ((t/p) == −1) continue;
printf(”(x, y) = (%d, %d) x, ±
√
x )
}
В этом цикле выражение (t/p) используется для обозначения символа
Лежандра.
Вычисление кратного kQ заданной точки Q
Поскольку, арифметика эллиптических кривых не содержит прямых
формул для вычисления кратного kQ для заданной точки Q(x
1
, y
1
), то эту
Глава 3. Эллиптические кривые                                             84

      Таким образом, данная кривая содержит 28 точек.
      Порядок точки A = ord(A) — это наименьшее натуральное число k
такое, что kA = ∞. Поскольку по теореме Лагранжа порядок любой точки
является делителем порядка группы, то порядок любой точки на кривой из
нашего примера принадлежит множеству {1, 2, 4, 7, 14, 28}.

      Пример. Найти сумму точек 3P = (3, −10) и 7P = (11, 3).

      Решение. Вычислим λ = (y2 − y1 )/(x2 − x1 ): y2 − y1 = 3 − (−10) =
13, x2 − x1 = 11 − 3 = 8. Поскольку 8−1 ≡ 3 (mod 23), то λ = 13/8 =
13 · 3 mod 23 = 16. Теперь, x3 = λ2 − x1 − x2 = (162 − 3 − 11) mod 23 = 12, а
y3 = λ(x1 − x3 ) − y1 = 16(3 − 12) − (−10)) mod 23 = 4.
      Ответ: (3, −10) + (11, 3) = (12, 4).

      Замечание. При выполнении удвоения точки или вычислении суммы
необходимо вычисление обратного элемента в поле Fq . Эта операция
выполняется с помощью обобщенного алгоритма Евклида (см.разд.2.5).

Вычисление множества точек эллиптической кривой

     Чтобы найти множество точек эллиптической кривой над простым
полем Fp , можно использовать следующий алгоритм:

      for(int x = 0; x < p; x + +){
       int t = x(x2 + a) + b;
       if ((t/p) == −1) continue;
                                        √
          printf(”(x, y) = (%d, %d) x, ± x )
      }
В этом цикле выражение (t/p) используется для обозначения символа
Лежандра.

Вычисление кратного kQ заданной точки Q

      Поскольку, арифметика эллиптических кривых не содержит прямых
формул для вычисления кратного kQ для заданной точки Q(x1 , y1 ), то эту

Страницы