Дискретное логарифмирование [Автор Неизвестен] (pdf) читать постранично

27
27.1

Дискретное логарифмирование
Метод больших-малых шагов

Пусть G — циклическая группа, порожденная элементом g, т. е. G = hgi. Будем считать, что G — группа
порядка q, т. е. ord g = q.
Нас будут интересовать методы решения уравнения
g x = y,

y ∈ G,

относительно x ∈ {0, 1, . . . , q − 1}, т. е. методы определения дискретного логарифма (индекса) logg y.
Пример 27.1. В схеме ЭльГамаля G — подгруппа F∗p , hp, g, bi — открытый ключ, hai — личный ключ и задача
дискретного логарифмирования превращается в задачу определения личного ключа по открытому.
¤

Пусть m =
тельности

§√ ¨
q . Метод больших-малых шагов состоит в отыскании совпадения элемента последова1, g, g 2 , . . . , g m−1 ,

с элементом последовательности
y, yg −m , yg −2m , . . . , yg −(m−1)m .
Если найдено совпадение g j = yg −im , то g im+j = y и logg y = (im + j) mod q.
Алгоритм Больших — малых шагов
Вход: (описание G, g, y).
Выход: logg y.
Шаги алгоритма:
1. Построить массив пар (j, g j ), j = 0, 1, . . . , m − 1. Отсортировать пары по второму элементу.
2. Установить c ← y.
3. Для i = 0, . . . , m − 1 выполнить
?

a) искать совпадение c = g j в массиве;
б) если найдено совпадение c = g j , то вернуть im + j;
в) c ← c · g −m .
√
√
Сложность. Требуется выполнить O( q) групповых операций и O( q log q) сравнений элементов группы
при сортировке на шаге 1. Если одна групповая операция является более трудоемкой, чем log n сравнений,
√
то сложность алгоритма — O( q) групповых операций.

27.2

ρ-метод

Мы уже знакомы с ρ-методом факторизации. Рассмотрим теперь ρ-метод логарифмирования, который был
предложен Поллардом в 1978 году.
Идея алгоритма. Проведем следующие построения:
1. Разобъем G на подмножества G1 , G2 и G3 примерно равной мощности.
2. Построим функцию ϕ : G → G,



 yz, z ∈ G1 ,
ϕ(z) =
z 2 , z ∈ G2 ,

 gz, z ∈ G .
3

116

3. Выберем z0 = 1 (1 — единица G) и построим последовательность zt = ϕ(zt−1 ), t = 1, 2, . . ..
Все элементы последовательности имеют вид zt = g ut y vt . Если мы нашли совпадение zt = zt+r , r > 0,
то
g ut y vt = g ut+r y vt+r ⇒ y vt −vt+r = g ut+r −ut ⇒ (vt − vt+r ) logg y ≡ (ut+r − ut ) (mod q).
Таким образом, если число (vt − vt+r ) обратимо по модулю q, то
logg y = (ut+r − ut )(vt − vt+r )−1 mod q.
Шаги алгоритма. Для вычисления дискретного логарифма требуется определить элементы последовательности (zt ) и найти коллизию zt = zt+r (можно воспользоваться алгоритмом Брента). Кроме этого, требуется знать числа ut , vt . Числа можно определять по следующим правилам:




ut−1 , zt−1 ∈ G1 ,

 (vt−1 + 1) mod q, zt−1 ∈ G1 ,
ut =
vt =
2ut−1 mod q, zt−1 ∈ G2 ,
2vt−1 mod q, zt−1 ∈ G2 ,


 (u

vt−1 , zt−1 ∈ G3 .
t−1 + 1) mod q, zt−1 ∈ G3 ,
√
Сложность алгоритма. Для определения дискретного логарифма требуется вычислить O( q) элементов
√
последовательности (zt ), т. е. выполнить O( q) групповых операций (сложения при определении последовательностей (ut ), (vt ) менее трудоемки, чем групповые операции).
Пример 27.2. На сегодняшний день все серьезные достижения по решению задачи дискретного логарифмирования
в группах точек эллиптических кривых (см. следующие лекции) получены с помощью ρ-метода. Компания Certicom
в 1997 году объявила конкурсные ECDLP различной степени сложности. На сегодняшний день решено 10 задач
из списка Certicom. Рекордное достижение — логарифмирование в группе, порядок которой является числом из
109 двоичных разрядов. В октябре 2009 года был начат эксперимент по дискретному логарифмированию в группе
точек эллиптической кривой над полем F2131 . Порядок целевой группы является числом из 130 двоичных разрядов. Эксперимент продолжается. С его промежуточными результатами можно ознакомиться в Интернет по адресу http://ecc-challenge.info.
¤

27.3

Метод Поллига — Хеллмана

Пусть q = q1 q2 , qi > 1. Введем в рассмотрение элементы g1 = g q2 , g2 = g q1 и пусть G1 = hg1 i, G2 = hg2 i.
Имеем: ord gi = qi и |Gi | = qi .
Будем искать решение уравнения g x = y в виде
x = x2 q1 + x1 ,

0 6 x2 < q2 ,

0 6 x1 < q1 .

Если g x2 q1 +x1 = y, то
(g x2 q1 +x1 )q2 = y q2 ⇒ g x1 q2 = bq2 ⇒ g1x1 = bq2 .
Поэтому можно поступить следующим образом:
1. Найти x1 = logg1 y q2 в группе G1 .
2. Найти x2 = logg2 yg −x1 в группе G2 .
3. Определить x = x2 q1 + x1 .
Таким образом, для дискретного логарифмирования в G требуется выполнить логарифмирование в группах
G1 и G2 меньшего порядка и использовать несложные дополнительные вычисления.
Если порядок Gi не является простым числом, то мы снова можем заменить логарифмирование в Gi
на логарифмирования в меньших группах и так далее. При достижении групп простого порядка можно
использовать метод больших-малых шагов.
Q
Если |G| = si=1 qiei , то для определения logg y потребуется выполнить
à s
!
X √
O
αi qi
i=1

групповых операций.
117

Пример 27.3. В первоначальном варианте своей схемы ЭльГамаль предлагал использовать в качестве g примитивный элемент F∗p , т. е. элемент порядка p − 1. Если p − 1 не имеет больших простых делителей, то с помощью метода
Поллига — Хеллмана можно достаточно эффективно находить личный ключ x = logg y. Поэтому требование наличия у p − 1 большого простого делителя q является весьма важным. Кроме этого, вместо