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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 114
однораундового протокола выработки общего секретного ключа на
основе метода Диффи-Хеллмана. Далее были найдены и другие, не
менее интересные приложения такие, как, например, построение открытого
ключа пользователя на основе его общеизвестных идентификационных
данных таких, как, например, имя или адрес электронной почты (identity
based open keys) (см. Advances in Elliptic Curve [?]).
6.2. Вычисление кратного точки ЭК с помощью MOV–
алгоритма
Описание этого алгоритма можно найти в главе 5 книги Л. Вашингтона [36].
Пусть заданы эллиптическая кривая EC : y
2
= x
3
+ ax + b (modp
r
),
и точки P , Q ∈ EC порядка n, где n–простое число, причем существует
m такое, что Q = mP . Требуется найти множитель m. Отображение Вейля
будем обозначать через e(X, Y ). Алгоритм вычисления m заключается в
следующем:
1. Находим случайную точку T ∈ EC(F
q
k
).
2. Находим порядок M точки T .
3. Находим d =Н.О.Д.(n, M). Если d = 1, то возвращаемся к п.1.
Иначе, перейдем к следующему пункту. Определим, что в этом случае т.T
имеет порядок n.
4. Вычислим a = e(P, T ) и с = e(Q, T).
5. Вычисляя дискретный логарифм в поле F
q
k
, найдем искомый
множитель m.
Отметим, что можно выполнять этот алгоритм с составным n, тогда
число d может оказаться собственным делителем n и найденный множитель
окажется равным m mod d. В этом случае можно повторять вычисление
с различными точками T
i
, вычисляя m
i
= m mod d
i
до тех пор, пока
произведение различных d
i
не станет больше или равно n. После этого можно
найти m с помощью китайской теоремы об остатках.
Замечание. Если речь идет о произвольной точке Q, то прежде,
Спаривание Вейля-Тейта                                                        114

однораундового     протокола   выработки     общего      секретного   ключа   на
основе метода Диффи-Хеллмана. Далее были найдены и другие, не
менее интересные приложения такие, как, например, построение открытого
ключа пользователя на основе его общеизвестных идентификационных
данных таких, как, например, имя или адрес электронной почты (identity
based open keys) (см. Advances in Elliptic Curve [?]).


6.2. Вычисление кратного точки ЭК с помощью MOV–
      алгоритма
Описание этого алгоритма можно найти в главе 5 книги Л. Вашингтона [36].
      Пусть заданы эллиптическая кривая EC : y 2 = x3 + ax + b (modpr ),
и точки P , Q ∈ EC порядка n, где n–простое число, причем существует
m такое, что Q = mP . Требуется найти множитель m. Отображение Вейля
будем обозначать через e(X, Y ). Алгоритм вычисления m заключается в
следующем:
      1. Находим случайную точку T ∈ EC(Fqk ).
      2. Находим порядок M точки T .
      3. Находим d =Н.О.Д.(n, M ). Если d = 1, то возвращаемся к п.1.
Иначе, перейдем к следующему пункту. Определим, что в этом случае т.T
имеет порядок n.
      4. Вычислим a = e(P, T ) и с = e(Q, T ).
      5. Вычисляя дискретный логарифм в поле Fqk , найдем искомый
множитель m.

      Отметим, что можно выполнять этот алгоритм с составным n, тогда
число d может оказаться собственным делителем n и найденный множитель
окажется равным m mod d. В этом случае можно повторять вычисление
с различными точками Ti , вычисляя mi = m mod di до тех пор, пока
произведение различных di не станет больше или равно n. После этого можно
найти m с помощью китайской теоремы об остатках.

      Замечание. Если речь идет о произвольной точке Q, то прежде,

Страницы