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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 108
Участник A вычисляет Q = k
A
· P
B
= k
A
k
B
G, а участник B находит
ключ по формуле Q = k
B
·P
A
= k
A
k
B
G. Отметим, что поскольку точка
на ЭК имеет две координаты, то можно в качестве секретного ключа
взять либо только координату x точки Q, либо только координату y ,
либо сумму координат x + y .
Возможный противник, зная известные параметры k
A
, k
B
и G, не
сможет вычислить значение общего ключа, т.к. для этого ему надо решить
задачу дискретного логарифмирования на эллиптической кривой (т.е. найти
кратное k по координатам т. kG и G).
Протокол Диффи-Хеллмана для трех и более участников
Идея алгоритма Диффи-Хеллмана легко может быть обобщена на несколько
участников. Приведем пример для случая n = 3:
1. Каждый из участников A, B , и C вырабатывает секретный ключ
k
A
, k
B
и k
C
соответственно и вычисляет точки P
A
= k
A
G, P
B
= k
B
G и
P
C
= k
C
G, которые пересылает по циклу A к B, B к C, C к A.
2. Далее, участники A, B , и C вычисляют точки Q
A
= k
A
P
C
, Q
B
=
k
B
P
A
, Q
C
= k
C
P
B
соответственно и пересылают по тому же циклу.
3. На последнем шаге вычисляется общая точка R = k
A
k
B
k
C
G,
домножением точки, полученной на предыдущем шаге, на соответствующий
секретный ключ:
R = k
A
k
B
k
C
G = k
a
Q
C
= k
B
Q
A
= k
C
Q
B
Замечание 1. Выполнение протокола Диффи-Хеллмана для двух
участников требует два обмена данными, для трех – уже шести обменов, а
для произвольного n – n! обменов данными, что является слишком большим
числом при сравнительно небольших n. Частично эта проблема может быть
решена путем использования билинейных или полилинейных отображений
типа преобразований Вейля и Тейта, описываемых в следующей главе.
Замечание 2. Для суперсингулярных кривых в 1993 году был
найден алгоритм Менезеса, Окатамо и Ванстоуна (так называемая MOV–
атака) ([28]), основанный на преобразовании Вейля-Тейта, позволяющий
Спаривание Вейля-Тейта                                              108

     Участник A вычисляет Q = kA · PB = kA kB G, а участник B находит
     ключ по формуле Q = kB · PA = kA kB G. Отметим, что поскольку точка
     на ЭК имеет две координаты, то можно в качестве секретного ключа
     взять либо только координату x точки Q, либо только координату y ,
     либо сумму координат x + y .

      Возможный противник, зная известные параметры kA , kB и G, не
сможет вычислить значение общего ключа, т.к. для этого ему надо решить
задачу дискретного логарифмирования на эллиптической кривой (т.е. найти
кратное k по координатам т. kG и G).

Протокол Диффи-Хеллмана для трех и более участников

Идея алгоритма Диффи-Хеллмана легко может быть обобщена на несколько
участников. Приведем пример для случая n = 3:
      1. Каждый из участников A, B , и C вырабатывает секретный ключ
kA , kB и kC соответственно и вычисляет точки PA = kA G, PB = kB G и
PC = kC G, которые пересылает по циклу A к B, B к C, C к A.
      2. Далее, участники A, B , и C вычисляют точки QA = kA PC , QB =
kB PA , QC = kC PB соответственно и пересылают по тому же циклу.
      3. На последнем шаге вычисляется общая точка R = kA kB kC G,
домножением точки, полученной на предыдущем шаге, на соответствующий
секретный ключ:

                  R = kA kB kC G = ka QC = kB QA = kC QB

      Замечание 1. Выполнение протокола Диффи-Хеллмана для двух
участников требует два обмена данными, для трех – уже шести обменов, а
для произвольного n – n! обменов данными, что является слишком большим
числом при сравнительно небольших n. Частично эта проблема может быть
решена путем использования билинейных или полилинейных отображений
типа преобразований Вейля и Тейта, описываемых в следующей главе.
      Замечание 2. Для суперсингулярных кривых в 1993 году был
найден алгоритм Менезеса, Окатамо и Ванстоуна (так называемая MOV–
атака) ([28]), основанный на преобразовании Вейля-Тейта, позволяющий

Страницы