08.04.09.Печать_edit

t i 1 ti t

Вэтой системе имеется s = t – ε неизвестных: log p1, log p2, …, log ps, которые являются индексами простых чисел, входящих в базу разложения.z log p mod p 1.k

2-й шаг. Используя методы линейной алгебры, решается приведенная выше система сравнений, в результате чего определяются значения индексов всех чисел, составляющих базу разложения, т. е. становятся известными зна-

чения log p1, log p2, …, log ps.

Второй шаг является наиболее трудоемкой процедурой, поскольку в базах разложения, которые могут быть использованы, обычно присутствует большое число простых чисел, что задает большое число неизвестных в решаемой системе. После завершения второго шага сравнительно легко может быть вычислен индекс (дискретный логарифм) для произвольных значений y (при основании ; если последнее значение изменится, то потребуется повторить первый и второй шаги). Используется система, число сравнений в которой превышает число неизвестных, поскольку некоторые сравнения могут оказаться зависимыми (тогда при t = s число решений было бы равно или больше p – 1, т. е. было бы практически бесконечным для длин модуля, которые используются в системах ЭЦП).

3-й шаг соответствует процедурам непосредственного вычисления x log y (mod p) . Выбирается случайное значение r, и вычисляется число

Y y r mod p . Затем число Y разлагается на простые множители:

s ( y )

Y pizi . Если значение Y не разлагается по нашей базе разложения, то

i

выбирается другое случайное число r. Если в разложении Y присутствуют только простые множители, входящие в базу разложения, то мы имеем:

71

В последнем сравнении неизвестной величиной является только log y , ко-

торая теперь легко вычисляется по формуле:

или

Заметим, что если основание логарифма не является первообразным корнем, то задача дискретного логарифмирования будет относиться к неко-

торой подгруппе Hβ, порядок которой равен показателю < p – 1, к которому относится основание логарифма по модулю p. Обычно в схемах ЭЦП с сокращенной длиной подписи используется простой показатель , длина которого в несколько раз (4–6 раз) меньше длины модуля числа p, поэтому приведенный выше метод вычисления индексов не может быть непосредственно

модулю p к показателю . Это связано с тем, что числа, входящие в подгруппу Hβ, составляют очень малую долю из множества положительных целых чисел, не превышающих p – 1, и вероятность того, что простые числа некото-

рой выбираемой базы разложения будут входить в Hβ, является пренебрежимо малой. Дискретное логарифмирование методом вычисления индексов может быть выполнено следующим путем.

Используя указанный метод, находим значение индекса u числа β при основании , являющемся первообразным корнем, т. е. имеем β = u mod p. Теперь исходное уравнение преобразуется в сравнение вида:

y x ux x mod p.

С помощью метода вычисления индексов находим значение x ux mod p 1 (*), по которому можно легко вычислить x. Последнее можно сделать, вы-

72

числив значение u log (mod p) (с помощью метода вычисления ин-

дексов). Из (*) получаем формулу для вычисления значения x:

Для значений длины модуля |p| ≥ 1024 и длины порядка подгруппы Hβ

| | ≤ 80 метод логарифмирования «шаг ребенка — шаг гиганта» является более эффективным.

При оптимизации выбора значения ε описанный в этом разделе метод имеет трудоемкость, которая оценивается величиной

где c — небольшая положительная константа. Дальнейшее развитие этого подхода позволило разработать методы дискретного логарифмирования, трудоемкость которых оценивается формулой

которая в настоящее время и служит ориентиром при выборе длины модуля в криптосистемах, основанных на сложности задачи дискретного логарифмирования. Заметим, что лучшие методы разложения RSA-модуля n имеют трудоемкость, оцениваемую по аналогичной формуле:

2.6.3. Метод Полларда

Метод больших и малых шагов требует использования чрезвычайно большой памяти. С целью устранения проблемы этой проблемы Поллард предложил оригинальный метод дискретного логарифмирования, трудоемкость которого также пропорциональна квадратному корню из порядка группы, в которой решается задача дискретного логарифмирования, но который не требует использования большой памяти. Этот метод получил название рометода Полларда (он использует «случайную» функцию, которая принимает последовательность значений образующих хвост и цикл, т. е. напоминает

73

греческую букву «ро»). Достоинством ро-метода Полларда является его универсальность, т. е. он применим к нахождению дискретных логарифмов в циклических группах произвольной природы и его трудоемкость определяется главным образом значением порядка группы.

В этом методе множество допустимых значений функции разбивается на три подмножества S1, S2 и S3 , причем подмножество S2 не содержит единицу, и используется следующая функция, задающая «случайное блуждание»:

где x0 1, основание логарифма и x (значение x требуется найти). С этой функцией связаны следующие две последовательности: a0 , a1, a2, a3, ... и b0 , b1, b2 , b3, ... , которые вычисляются по следующим формулам

где a0 b0 0 и порядок группы. Легко заметить, что для всех i 1 имеет место соотношение

xi 1 xi ai 1 bi ai 1 bi 1 . Таким образом, для всех трех случаев из выполнимости (1) следует, что xi 1 ai 1 bi 1 , следовательно, согласно методу математической индукции (1) верно для всех значений i 0 .

74

Значение дискретного логарифма находится следующим образом. Используя метод Флойда (см. раздел 2.5.2), находим значение m, такое, что xm x2m . Выражая правую и левую часть последнего равенства с помощью соотношения, получаем

am bm a2m b2m bm b2m a2m am

bm b2m log a2m am x log a2m am mod . bm b2m

Наиболее трудоемким этапом рассмотренного метода является выполнение алгоритма Флойда, сложность которого пропорциональна . Таким образом, трудоемкость ро-метода Полларда имеет такой же порядок как метод больших и малых шагов, однако в отличие от последнего в первом используется память существенно меньшего объема (такие методы иногда называют не требующими памяти).

2.6.4.Случай составного порядка

Вразделах 2.6.1 и 2.6.3 были представлены общие методы вычисления дискретного логарифма в группе простого порядка, содержащие элементы произвольной природы. Сложность решения это задачи для группы произвольной природы не превышает числа операций возведения в степень, примерно равного квадратному корню из порядка группы. В общем случае, если основание алгоритма имеет порядок, равный составному числу, то сложность вычисления логарифма определяется значением наибольшего простого делителя порядка основания. Это связано с тем, что указанный общий случай сводится к вычислению дискретных логарифмов по основаниям, являющихся простыми числами. Рассмотрим метод такого сведения на примере мультипликативной группы вычетов по простому модулю p.

Пусть требуется вычислить

x log y (mod p) ,

где порядок ( ) основания является составным числом. Пусть, например, ( ) p 1. Представим значение порядка в виде канонического разложения

s

( ) riei ,

i 1

75

вычисление x j даст значение, которое не превосходит величину ( j ) . Име-

ем

xj xj j mod p x x j mod ( j ) .

Вычислив значения дискретных логарифмов при основаниях j для всех j 1,2,...,s , получим следующую систему сравнений:

в которой все модули являются взаимно простыми числами. В соответствии с китайской теоремой об остатках данная система имеет единственное реше-

j 1,2,..., s при соответствующих основаниях, можно далее легко определить искомый дискретный логарифм x при основании .

Покажем теперь, что логарифмирование по модулю, равному степени простого числа, имеет тот же порядок сложности, что и дискретное логарифмирование по простому модулю. Пусть требуется вычислить логарифм

76

искомое значение x можно представить в виде x Qre 1 xe 1 , где 0 Q r

(поскольку x re ). Таким образом, значение x можно найти методом полного перебора возможных значений Q. Это можно сделать методом больших и ма-

есть ли такое значение в построенном ранее упорядоченном массиве (каждая проверка потребует выполнения log2 d операций сравнения). При некотором j0 найдется i0 , такое что текущее проверяемое значение будет присутствовать в массиве. По найденным значениям j0 и i0 вычисляем Q dj0 i0 , а по Q – искомое значение x. Трудоемкость этой процедуры пропорциональна d r операций возведения в степень по модулю p. Применяя этот способ понижения порядка основания при котором вычисляется логарифм e 1 раз, мы приходим к необходимости вычислить логарифм при основании, имеющем простой порядок r. Трудоемкость вычисления последнего при использовании метода больших и малых шагов (или ро-метода Полларда) пропорцио-

77

нальна r , т. е. имеет оценку O r . Получаем, что трудоемкость вычисле-

ния логарифма при основании, имеющем порядок re пропорциональна er ,

т. е. имеет оценку O r .

Таким образом, вычисление логарифма по модулю p при основании, имеющем порядок re, не только сводится к вычислению логарифма по модулю p при основании, имеющем простой порядок r, но и имеет такую же оценку трудоемкости, как и вторая вычислительная задача, решаемая методом больших и малых шагов. Мы рассмотрели сведение одной задачи к другой на примере подгрупп мультипликативной группы. Однако аналогичное сведение реализуется для групп произвольной природы.

Глава 3. Задачник

В данной главе приведены задачи, рекомендуемые для решения на практических занятиях и в качестве домашних заданий. Задания для лабораторных работ можно найти в [3], а для курсовых работ – в [4].

3.1. Примеры решения задач

Задача 3.1.

Доказать, что для вычета a n-ой степени по модулю p, где n делит число

p 1

p 1, выполняется соотношение a n 1mod p .

Решение: Пусть a – вычет степени n по модулю p. Тогда существует x: x < p и xn a mod p . Возведем обе части последнего сравнения в степень

78

Решение: По простому модулю существуют первообразные корни. Пусть

p 1 ind a 0mod p 1 n | ind a . Значит, для некоторого целого Q имеем n

a gind a gQn mod p x : xn a mod p , т. е. na mod p gQ mod p .

Задача 3.3.

Доказать, что число вычетов степени n | p(p 1) по модулю p2 равно n.

Решение: Рассмотрим сравнение xn a mod p2 , где a – вычет n-й сте-

пени по mod ps и НОД(a, (p2)) = 1 (следовательно имеем также и

НОД(x, (p2)) = 1). Известно, что по модулю p2 имеются первообразные корни. Пусть g – некоторый первообразный корень. Тогда можем переписать

Задача 3.4.

Доказать, что если a – вычет степени n | p(p 1), где p – нечетное про-

Решение: По условию задачи существует некоторое значение x, такое что выполняется сравнение xn a mod p2 , которое можно представить в виде gn ind x gind a mod p2 , g – некоторый первообразный корень, откуда следует

79

n ind x ind a mod ( p2 ) , где (p2) = p(p 1). Поскольку по условию модуль

n по модулю p2.

Решение: Поскольку по модулю p2 имеются первообразные корни, то

xn a mod p2 .

НОД(x, (ps)) = 1). Известно, что по модулю ps имеются первообразные корни. Пусть g – некоторый первообразный корень. Тогда можем переписать

80