Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
C(X) = C0 Ца(Х)^\
Один из способов такой проверки — просмотреть все а(Х) Є В, деля с(Х) последовательно на а{Х)а°'а (где аса — наибольшая степень а(А'), на которую делится с(Х) в Fp[X]). Если после всех этих делений от многочлена остается лишь константа C0, то с(Х) имеет указанную выше форму. В противном случае все повторяется для нового случайно выбранного целого t. (Другой — иногда более быстрый — способ проверки того, разлагается ли с(Х) в произведение а(Х) Є В, состоит в нахождении всех делителей с(Х) с помощью какого-нибудь алгоритма разложения элементов Fp[X]. Например, удобный алгоритм Берлекампа описан в § 4.6.2 второго тома книги Кнута.)
Теперь допустим, что найден элемент с(Х) = Ь(Х)1 (mod /(X)), имеющий разложение искомого типа. Взяв дискретный логарифм от обеих частей этого равенства, получаем
indc(X) - indco = ^jP ac>ainda(X),
где равенство должно пониматься как сравнение по модулю q - 1 (так как дискретный логарифм определен только по модулю q — Vj. Левая часть этого равенства известна: indc(X) = t, а дискретные логарифмы констант мы считаем известными. Коэффициенты ас^а в правой части также известны. Неизвестными являются h значений inda(X), a(X) Є В, в правой части.
Таким образом, мы получили линейное уравнение с h неизвестными в Z/(q — I)Z. Представим себе, что мы продолжаем выбирать случайные целые t, пока не получим много разных с(Х), разложимых в произведение многочленов а(Х). Как только мы получим h независимых сравнений вида
t - ind со = ^jP ас>а ind а(Х) (mod q - 1)
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
117
(здесь «независимость» означает, что определитель матрицы {ас<а] взаимно прост с q - 1), мы сможем решить эту систему относительно неизвестных по модулю q — I- (Элементы линейной алгебры по mod N = q — 1 изложены в § III.2.) На этом предварительная стадия индексного алгоритма завершается. Она создала большую «базу данных», а именно, значений дискретных логарифмов для всех а(Х) Є В, с помощью которых можно вычислить дискретный логарифм любого элемента из F,.
Прежде чем приступить к описанию второй фазы индексного алгоритма, обсудим способ выбора т, который не был конкретизирован при определении В С Fp[X] как множества всех нормированных неприводимых многочленов степени не выше т. Размер h множества В быстро растет с ростом т. Например, при простом т (см. следствие из предложения И.1.8) существует (рт — р)/т нормированных неприводимых многочленов только степени т. Так как необходимо найти не менее h различных с(Х), которые дадут систему из h линейных сравнений относительно h неизвестных ind а(Х), и эту систему надо будет решать, то желательно, чтобы h (и, значит, то) были не слишком большими. С другой стороны, если т мало, то «типичный» нормированный многочлен C0 1C(X) степени не выше n — 1, скорее всего, не разложится в произведение многочленов а(Х) степени не выше т и будет иметь, по крайней мере, один неприводимый множитель степени выше т. Таким образом, при малом m придется слишком долго ждать даже первого появления t, при котором с(Х) = Ь(Х)1 (mod /(X)) имеет разложение желаемого вида. Итак, то должно быть, с одной стороны, не слишком мало, а с другой — заметно меньше п. Оптимальный выбор т, зависящий, разумеется, от р и п, требует глубокого исследования вероятностей и оценок трудоемкости, что выходит за рамки данной книги. Ограничимся примером: при р = 2 и п = 127 наилучшим зна-
127
чением является т = 17 (тогда h = 16510). Величина q = 2 берется
* 127
часто, так как #(F2i2t) = 2 - 1 есть простое число Мерсенна.
Теперь вернемся к индексному алгоритму и опишем его заключительный этап. Пусть требуется вычислить дискретный логарифм элемента у(Х) Є Fq и на первом этапе найдены величины inda(X) для всех а(А') Є В. Опять выбираем случайно t между 1 и q — 2 и вычисляем ух = уЬЬ, т.е. единственный многочлен У\(Х) Є Fp[X] степени ниже п, удовлетворяющий условию JZi(X) = у(Х)Ь(Х)1 (mod /(X)). Как и на первом этапе алгоритма, проверяем, разлагается ли 2/і(Х) в произведение константы со и степеней многочленов а(Х) Є В. Если это не так, то случайно выбираем новое t и т.д., пока не будет найдено такое целое t, что т/1 (X) = 2/о Паев а{Х)аа. Как только это произойдет,
118
ГЛ. IV. ОТКРЫТЫЙ ключ
цель достигнута, так как по определению т/і выполняются равенства ind у = ind 2Z1 - ( и ind Jz1 = ind т/0 + YJa0 ind а(Х). Все слагаемые члены в правой части последнего равенства известны. Это завершает описание индексного алгоритма.
Следует заметить, что Д. Копперсмит предложил метод, который в наиболее интересном случае р = 2 значительно ускоряет процесс вычисления дискретного логарифма. Поэтому криптосистемы, использующие дискретное логарифмирование в F2.., считаются ненадежными, если п меньше 1000. Несмотря на это, поля F2» часто используются ввиду удобства для программирования. Хороший обзор этих вопросов (охватывающий то, что было известно к 1985 году) имеется в статье А. Одлыжко (см. приведенный ниже список литературы).
Если q = рп есть степень нечетного простого числа, имеющая длину к бит, то оказывается, что время решения задачи дискретного логарифмирования в F^ сравнимо по порядку со временем работы алгоритмов разложения на множители fc-битового целого числа. Поэтому с эмпирической точки зрения задача дискретного логарифмирования, по-видимому, столь же трудна, как и задача разложения на множители (хотя еще никому не удалось доказать теорему такого рода). Действительно, когда в следующей главе будут рассматриваться алгоритмы разложения на множители, мы увидим, что один из основных методов разложения больших целых чисел поразительно похож на индексный алгоритм дискретного логарифмирования.
