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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 100
3.5. Спаривание Вейля-Тейта
Широкое использование эллиптических кривых в криптографии
основано на том свойстве, что задача дискретного логарифмирования на
эллиптических кривых (задача ДЛЭК) является более трудоемкой, чем
задача дискретного логарифмирования в конечных полях ДЛКП. Это
позволяет использовать ключи меньшей длины по сравнению с ключами
методов RSA и Эль–Гамаля (160 бит против 1024 бит), что уменьшает
требования на вычислительные системы, выполняющие шифрование.
Однако, в 1993 году А. Менезес, Т. Окамото и С. Вэнстоун [34]
показали, что задача ДЛЭК сводится к задаче ДЛКП в некотором конечном
расширении исходного поля GF (q) эллиптической кривой. Идея сведения
основана на спаривании Вейля (Weil’s Pairing) по имени выдающегося
французского математика Андре Вейля (1906–1998), известного своими
трудами в области алгебраической геометрии.
Пусть задано уравнение ЭК E : y
2
= x
3
+ax+b над полем F
q
, q = p
m
.
Напомним, что алгебраическим замыканием поля K называется множество
корней уравнений с коэффициентами из этого поля (обозначается K ).
Пусть n–целое положительное число, взаимно-простое с p.
Определим множество E[n] как множество точек кривой E порядка n
над алгебраическим замыканием F
q
исходного поля F
q
, т.е. множество
точек P (x, y) ∈ EC(F
q
), удовлетворяющих nP = ∞.
Хотя исходное поле F
q
конечно, его замыкание бесконечно. Однако,
множество E[n] содержит конечное число элементов (можно доказать, что
оно изоморфно группе Z
n
⊕Z
n
) и, значит, содержится в некотором конечном
расширении F
q
k
исходного поля. Степень k называется степенью вложения.
Эта степень может быть определена как наименьшее положительное число
со свойством n |(q
k
− 1). Определим µ
n
как множество корней n-й степени
из 1, содержащихся в F
q
k
.
Отображение Вейля представляет собой билинейное отображение
e : E[n] ⊕E[n] → µ
n
, (3.68)
обладающее следующими свойствами:
Спаривание Вейля-Тейта                                                   100

3.5. Спаривание Вейля-Тейта
       Широкое использование эллиптических кривых в криптографии
основано на том свойстве, что задача дискретного логарифмирования на
эллиптических кривых (задача ДЛЭК) является более трудоемкой, чем
задача дискретного логарифмирования в конечных полях ДЛКП. Это
позволяет использовать ключи меньшей длины по сравнению с ключами
методов RSA и Эль–Гамаля (160 бит против 1024 бит), что уменьшает
требования на вычислительные системы, выполняющие шифрование.
      Однако, в 1993 году А. Менезес, Т. Окамото и С. Вэнстоун [34]
показали, что задача ДЛЭК сводится к задаче ДЛКП в некотором конечном
расширении исходного поля GF (q) эллиптической кривой. Идея сведения
основана на спаривании Вейля (Weil’s Pairing) по имени выдающегося
французского математика Андре Вейля (1906–1998), известного своими
трудами в области алгебраической геометрии.
      Пусть задано уравнение ЭК E : y 2 = x3 +ax+b над полем Fq , q = pm .
Напомним, что алгебраическим замыканием поля K называется множество
корней уравнений с коэффициентами из этого поля (обозначается K ).
      Пусть    n–целое   положительное   число,   взаимно-простое    с    p.
Определим множество E[n] как множество точек кривой E порядка n
над алгебраическим замыканием Fq исходного поля Fq , т.е. множество
точек P (x, y) ∈ EC(Fq ), удовлетворяющих nP = ∞.
      Хотя исходное поле Fq конечно, его замыкание бесконечно. Однако,
множество E[n] содержит конечное число элементов (можно доказать, что
оно изоморфно группе Zn ⊕ Zn ) и, значит, содержится в некотором конечном
расширении Fqk исходного поля. Степень k называется степенью вложения.
Эта степень может быть определена как наименьшее положительное число
со свойством n | (q k − 1). Определим µn как множество корней n-й степени
из 1, содержащихся в Fqk .
      Отображение Вейля представляет собой билинейное отображение

      e : E[n] ⊕ E[n] → µn ,                                         (3.68)

обладающее следующими свойствами:

Страницы