<< Предыдущая

стр. 38
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Следовательно, искомое решение задачи о дискретных логарифмах
будет иметь вид:
X — cjsf — dM (mod^).
Если пересечения путей не произойдет, нам придется увеличить N
и продолжить оба блуждания до их пересечения.
Ожидаемое время работы алгоритма имеет порядок у ^ , и мож­
но показать, что количество требуемой памяти постоянно. Л-метод
возможно использовать и тогда, когда известно лишь, что искомый
логарифм лежит в полном отрезке [О,..., д'—1]. Но тогда асимптотика
сложности алгоритма совпадает со сложностью р-метода.
В качестве примера снова возьмем группу G С F^QT порядка 101
с образующей 64, но задачу выберем другую, а именно, попытаемся
найти ж, при котором
Я = 524 - 64^.
Будем считать известным, что искомое решение лежит на отрезке
[60, . . . , 80]. Возьмем в качестве коэффициентов числа Si — 2^ при
г = О, 1, 2, 3. Подмножества ^о, . . . , S^ группы определим так:
Si = {а е А\ а (mod 4) = г}.
Сначала вычисляем детерминированную случайную последователь­
ность Gi и дискретные логарифмы Ci = log^(Gx) Д^^я^ г = О,..., А/^ = 4:

i Gi Ci

151
0 80
1 537 88
2 391 90
3 478 98
4 64 1
9,4' Методы Лолларда 249

Потом вычисляем вторую псевдо-случайную последовательность.

i di -= logG(^i) - ^
Hi
и 524 0
1 1
151
2 537 9
11
3 391
4 478 19
64
5 23
Получили встречу: Н^ = G^. Поэтому
д: = 1 - 2 3 (mod 101) = 7 9 .
Обратите внимание на то, что при исследовании этих таблиц можно
заметить и более ранние пересечения наших блужданий. Однако мы
их не могли использовать, поскольку не запоминали промежуточных
значений последовательности G^, т.е. элементов Go, Gi, G2 и G3.
Единственное, о чем мы помнили — это G4.

9.4.3. Параллельный р - м е т о д
При применении этих алгоритмов на практике для распределения
вычислений между большим числом компьютеров через Интернет
используют параллельную версию метода. Суть распараллеливания
состоит в следуюш;ем. Допустим, перед нами стоит задача о решении
уравнения


в группе А простого порядка q. Сначала зададим легко вычислимую
функцию
f:A ^{1,...,А;},
где к обычно берут около 20. Затем определим множество коэффи­
циентов гпг по случайным числам а^, Ь^ G [О, . . . , ^ — 1] с помощью
формулы


Чтобы начать случайное блуждание, мы берем произвольную пару
чисел 5о, to G [О, . . . , д — 1] и вычисляем
^
Go = G'oЯ*^
Следуюп1;ие члены yLjri^Sijti) псевдослучайной последовательности
Глава 9. Дискретные логарифмы

получаются рекуррентно:
GiH-i = Gi • rufi^Gi)^ "^^+1 = ^г + ^f{Gi) (modg),
ti^i :=ti-bbf(^Gi) (mod9).
Следовательно, для каждого Gi мы записываем значения Sinti^ удо­
влетворяющие соотношению
Gi = G''H^\
Допустим, что у нас есть т процессоров, каждый из которых вы­
числяет блуждающие последовательности, начинающиеся с разных
элементов, по одному и тому же алгоритму. Когда два процессора
или даже один и тот же найдет элемент последовательности, кото­
рый уже встречался, мы получим уравнение:


из которого мы можем извлечь дискретный логарифм х. Ожида­
ют, что после 0{\/7гд/2/т) итераций этих параллельных блужданий
найдется повторение и удастся вычислить дискретный логарифм.
Однако при таком способе решения проблемы подразумевается,
что каждый из участвующих в процессе компьютеров должен сооб­
щать очередные члены последовательности на центральный сервер,
который будет их хранить и сравнивать. Это весьма неэффектив­
ный метод, поскольку придется запоминать слишком много, а имен­
но 0{у/тщ12) данных. Можно уменьшить требуемое количество па­
мяти. Объясним, как это сделать.
Возьмем функцию d : А • {ОД}? которая принимает еди­
ничные значения примерно один раз из 2^ Ее часто задают так,
что d{a) = 1, если определенное подмножество бит, представляю­
щих элемент а, состоит из нулей. Те элементы а Е А^ для которых
d{a) = 1, называют отмеченными. Теперь на центральный сервер
поступают сведения лишь об отмеченных элементах группы. Это
означает, что случайные блуждания скорее всего продлятся еще на
2^ шагов, прежде чем будет обнаружено пересечение их путей. Сле­
довательно, время вычислений становится теперь равным

оШИ^А.
И требуется



памяти.
9.5. Суб-экспоненциальные методы в числовых полях 251

Такой прием позволяет сократить расходы памяти до любой тре­
буемой величины за счет сравнительно небольшого увеличения вре­
мени работы алгоритма. Мы не будем приводить примера, посколь­
ку это усовершенствование полезно лишь для очень больших групп,
порядок которых превышает 2^^. Но мы советуем читателю проду­
мать свой собственный пример.


9.5. Суб-экспоненциальные методы в числовых
полях
Суш;ествует тесная связь между суб-экспоненциальными методами
разложения на множители и суб-экспоненциальными методами дис­
кретного логарифмирования в конечных полях. Мы рассмотрим слу­
чай поля ?р с простым числом р элементов, отметив, что аналогич­
ные методы применяются и к конечным полям характеристики 2.
Суб-экспоненциальные алгоритмы в конечных полях часто называ­
ют исчислением показателей по причинам, которые станут понят­
ны после знакомства с методами.
Как и прежде, мы считаем, что нам поставлена задача о решении
уравнения


с if, G G F*. Выберем факторбазу Т элементов, состоявшую из ма­
лых простых чисел, и применим одну из просеиваюш;их стратегий,
использовавшихся при факторизации. Получим большое число соот­
ношений вида
Л р^С = 1 (modp).

Эти соотношения переписываются в уравнения дискретного лога­
рифмирования:

Е бг \ogG{pi) = О (mod {р - 1)).
PieT
Как только достаточно уравнений, подобных этому, будет найде­
но, мы сможем решить задачу дискретного логарифмирования для
каждого элемента из факторбазы, т. е. мы сможем найти число
Хг = logfjPu

которое иногда называют показателем элемента pi по отношению
к G. Эти вычисления осуш;ествляются с помош;ью линейной алгебры
по модулю р — 1, более сложной, чем линейная алгебра по модулю 2,
252 Глава 9. Дискретные логарифмы

привлекавшаяся в алгоритмах факторизации. Однако приемы, сни­
жавшие в алгоритмах факторизации требования к памяти компью­
тера до приемлемого уровня, работают и в этом случае. Линейная
алгебра применяется один раз р^ля каждого основания G, а ее ре­
зультаты работают потом р^ля многих элементов Н.
Когда возникает необходимость в вычислении конкретного ло­
гарифма Н — G^^ с помош;ью техники решета или метода пробного
деления выписывают разложение
Я = П р^^ (modp),

Т. е. мы можем вычислить
T = Hjlpf; (modp),

и получить разложение вида
Т = Д p f (modp).

Сделав это, получим
Я=и pf-f' (modp).
Pie:F

Искомый ж, наконец, можно найти, сделав следуюш;ие вычисления:

X = logaiH) = log,, I П РТ
\pieT

= ^ h i logaipi) {modp - 1) =
PieT
= y j hi • Xi (modp — 1).

Это означает, что как только один логарифм будет найден, осталь­
ные вычислить будет легче, поскольку мы уже будем знать все по­
казатели Xi,
Наилучший способ поиска соотношений на факторбазе — реше­
то в числовом поле. Его сложность оценивается функцией
0(Lp(l/3,c))
С некоторой константой с. Она примерно совпадает со сложностью
алгоритма факторизации больших чисел, хотя при дискретном ло­
гарифмировании используется матрица по модулю р — 1, а не по
модулю 2, как это было при факторизации.
9.6. Специальные методы для эллиптической кривой 253

Вывод из анализа суб-экспоненциальных методов говорит о том,
что размер р конечного поля, в котором ставится задача дискрет­
ного логарифмирования, должен быть примерно таким же, как и
модуль системы RSA., т.е. порядка р > 2^^^^.
Даже если р будет очень большим, нам все еще нужно принять
меры против общей атаки. Поэтому простые делители q числар—1
должны быть больше 2^^^, поскольку в случае конечных полей, где
проводится логарифмирование, мы обычно работаем с подгруппами
группы F* порядка q.


9.6. Специальные методы для эллиптической кривой
в случае эллиптических кривых неизвестны суб-экспоненциальные
методы, решающие задачу дискретного логарифмирования, за ис­
ключением некоторых особых случаев. Это означает, что единствен­
ный метод дискретного логарифмирования в общих группах элли­
птических кривых — это параллельная версия р-метода Полларда.
Пусть эллиптическая кривая Е определена над конечным по­
лем F^. Положим
#E{?g) = h-r,
где г — простое число. По теореме Хассе 2.3 значение #E{?q) близко
к q. Таким образом, обычно выбирают кривую Е с параметром г,
мало отличающимся от д, т.е. берут кривую, для которой /г = 1, 2
или 4.
Наилучший из известных алгоритмов дискретного логарифми­
рования на эллиптической кривой — параллельный р-метод Поллар­
да, чья сложность — 0{^)^ близкая к 0{^). Поэтому для обеспече­
ния той же криптостоикости, которая есть у 80-битового блочного
шифра, нам нужно брать q ^ 2^^^, что несколько меньше, чем размер
поля, рекомендованный к использованию в криптосистемах, осно­
вывающихся на дискретном логарифмировании в конечных полях.
Это отражается на пропускной способности и времени вычислений
в системах, базирующихся на эллиптической кривой.
Однако существует несколько специальных случаев, которых сле­
дует избегать. Сейчас мы о них расскажем, но не станем подробно
объяснять причины их нежелательности, поскольку такое объясне­
ние использует слишком сложную математику. Как обычно, будем
предполагать, что q — либо большое простое число, либо степень 2.
- Для любого q нам нужно выбрать кривую, для которой нет
маленьких чисел t, при которых q^ — 1 делится на г, где г —
Глава 9. Дискретные логарифмы

большой простой делитель числа #Е{?д), Такое требование
исключает из рассмотрения суперсингулярные кривые и не­
сколько других. В этом случае есть простое преобразование,
сводящее задачу дискретного логарифмирования над эллипти­
ческой кривой к аналогичной задаче в конечном поле ?gt. Сле­
довательно, в этой ситуации можно получить суб-экспоненци-
альный метод решения задачи дискретного логарифмирования
над эллиптической кривой.
- Если q = р — большое простое число, то нам следует избегать
аномальных кривых, для которых i^E{?p) = р. В этом слу­
чае суш;ествует алгоритм решения задачи, требующий 0{1пр)
операций над точками эллиптической кривой.
- Если g = 2^, то обычно выбирают простое п, чтобы избежать
f
возможных атак, основанных на понятии «спуск Вейля».
Нужно быть предельно внимательным, имея дело с этими тремя
исключениями, примерно так же, как и при генерировании больших
целых чисел для алгоритма RSA. Учитывая (Р — 1)-метод разложе­
ния на множители, в системе RSA^ как правило, выбирают модули
N — pq так, что р представляется в виде 2pi -|- 1 с каким-то дру­
гим простым pi. Другая особенность криптосистемы RSA состоит
в том, что мы применяем модули с двумя простыми множителями,
а не с тремя или четырьмя. Мотивируется это тем, что произве­
дение двух простых чисел разложить на множители сложнее, чем
произведение большего числа множителей.

Краткое содержание главы

<< Предыдущая

стр. 38
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>