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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 95
Z
i
(modn), где Z
i
– Z –координата точки q
i
P . Тогда, проверку Н.О.Д.(n,
Z
i
) ̸= 1 можно заменить проверкой Н.О.Д.(n, P rodZ) ̸= 1 и выполнять
ее, например, один раз на 100 или более сложений.
Также для ускорения сложения координаты точек δ
i
P следует
представить в афинных координатах, тогда операция сложения двух точек
ЭК потребует 11 умножений элементов Z
n
, а не 14, как при сложении в
проективных координатах (см.формулы 5.52).
В наиболее простом варианте реализации второй стадии можно
вычислить только одну точку 2 P и прибавлять ее к точке q
1
P пока не
получим требуемое условие (5.56).
Пример 1. Пусть требуется разложить число n = 455 839. Выберем
эллиптическую кривую
y
2
= x
3
+ 5x − 5,
точку P = (1, 1) на ней и постараемся вычислить 10! P .
1. Найдем сначала 2P . Тангенс угла наклона касательной λ в т.P
равен λ = (3 · 2 + 5)/(2y) = 4 и координаты P
2
= 2P = (x
2
, y
2
) =
(14, −53) (modn).
2. Вычислим далее, P
3
= 3(2P ) = 3P
2
. Прямой формулы для
вычисления точки 3P
2
нет, поэтому придется вычислить сначала 2P
2
, затем
получить 3P
2
, суммируя точки 2P
2
и P
2
. Получим 2P
2
= (259 851, 116 255),
3P
2
= (195 045, 123 227).
3. Продолжая эту процедуру вычислим 4!P , потом 5!P и т.д.
При вычислении 8!P знаменатель λ станет равным 599 и вычисление
Н.О.Д.(n, 599) даст значение d = 599. Отсюда 599 является делителем n, и
деля n на 599 найдем второй делитель n: 455839 = 599 · 761.
Причина, по которой процесс сошелся при вычислении 8!P , состоит в
том, что кривая y
2
= x
3
+ 5x − 5 ( mod 599) содержит 640 = 27 · 5 точек.
Вторя кривая y
2
= x
3
+5x−5 ( mod 761) содержит 640 = 27·5 точек. Число
8! делится на 640, но не делится на 777. Поэтому первым появился делитель
p = 599.
Глава 3. Эллиптические кривые                                            95

Zi (mod n), где Zi – Z –координата точки qi P . Тогда, проверку Н.О.Д.(n,
Zi ) ̸= 1 можно заменить проверкой Н.О.Д.(n, P rodZ) ̸= 1 и выполнять
ее, например, один раз на 100 или более сложений.
      Также для ускорения сложения координаты точек δi P следует
представить в афинных координатах, тогда операция сложения двух точек
ЭК потребует 11 умножений элементов Zn , а не 14, как при сложении в
проективных координатах (см.формулы 5.52).
      В наиболее простом варианте реализации второй стадии можно
вычислить только одну точку 2 P и прибавлять ее к точке q1 P пока не
получим требуемое условие (5.56).

      Пример 1. Пусть требуется разложить число n = 455 839. Выберем
эллиптическую кривую

              y 2 = x3 + 5x − 5,

точку P = (1, 1) на ней и постараемся вычислить 10! P .

      1. Найдем сначала 2P . Тангенс угла наклона касательной λ в т.P
равен λ = (3 · 2 + 5)/(2y) = 4 и координаты P2 = 2P = (x2 , y2 ) =
(14, −53) (modn).
      2. Вычислим далее, P3 = 3(2P ) = 3P2 . Прямой формулы для
вычисления точки 3P2 нет, поэтому придется вычислить сначала 2P2 , затем
получить 3P2 , суммируя точки 2P2 и P2 . Получим 2P2 = (259 851, 116 255),
3P2 = (195 045, 123 227).
      3. Продолжая эту процедуру вычислим 4!P , потом 5!P и т.д.
При вычислении 8!P знаменатель λ станет равным 599 и вычисление
Н.О.Д.(n, 599) даст значение d = 599. Отсюда 599 является делителем n, и
деля n на 599 найдем второй делитель n: 455839 = 599 · 761.
      Причина, по которой процесс сошелся при вычислении 8!P , состоит в
том, что кривая y 2 = x3 + 5x − 5 ( mod 599) содержит 640 = 27 · 5 точек.
Вторя кривая y 2 = x3 + 5x − 5 ( mod 761) содержит 640 = 27 · 5 точек. Число
8! делится на 640, но не делится на 777. Поэтому первым появился делитель
p = 599.

Страницы