Лекция: Дискретных логарифмов
Пусть G конечная циклическая группа порядка m, g – образующий элемент G.
Вычет такой, что для заданного называется дискретным логарифмом (показателем) элемента группы h по основанию g. Проблема дискретного логарифмирования заключена в эффективном вычислении по g, h. Эта задача является фундаментальной для криптоанализа многих криптографических протоколов. Однако, существуют группы, для которых задача вычисления дискретных логарифмов имеет очень простое решение. Например, это так для группы. Действительно, для любого а, при котором, и для любого легко решить сравнение .
Для криптоанализа шифров основанных на проблеме логарифмирования центральными являются следующие циклические группы:
1. мультипликативная группа конечного простого поля порядка p, .
2. Подгруппа простого порядка q мультипликативной группы поля, где при некотором .
3. Циклическая подгруппа порядка m группы точек эллиптической кривой, где .
Метод сведения к собственным подгруппам. Чтобы осуществить сведение проблемы логарифмирования в группе к собственным подгруппам, они должны существовать. Для этого необходимо и достаточно, чтобы число m было составным. Если m составное, то
либо 1), где, ,
либо 2), r – простое число, .
Рассмотрим сначала первый случай. Пусть,. Тогда G содержит две циклических подгруппы,,. Нетрудно видеть, что,. Вычислим – дискретный логарифм по основанию,. Так как, то и. Значит, вычет может быть найден по китайской теореме об остатках.
Во втором случае представим неизвестный показатель в r-ичной системе счисления, где,. Алгоритм вычисления состоит в последовательном вычислении .
Найдем x0. Для этого вычислим и. Тогда легко видеть, что. Элемент g0порождает подгруппу G0порядка r в G. Вычислив каким-то образом, получим следующее уравнение в подгруппе G’ порядка относительно
,
где и. Таким образом, выполнив одно логарифмирование в G0, мы свели задачу к вычислению дискретного логарифма в группе G’ меньшего порядка. Продолжая так действовать далее, вычислим, проделав l логарифмирований в G0.
Пример. Вычислим логарифм. Так как 37-1=36=4×9, то группа содержит подгруппы порядков 4 и 9. Найдем и из сравнений
или .
Вычислим сначала. Представим,. Тогда
,, x10=1,
,, x10=1.
Значит,. Вычислим теперь. Представим,. Тогда
,, x20=0,
,, x20=2.
Значит,. Теперь по китайской теореме об остатках находим. Равенство проверяется непосредственно.
Алгоритм Гельфонда-Шенкса.Этот алгоритм использует идею голосования. Входные данные алгоритма. Конечная циклическая группа G=<g> порядка m, элемент .
Выходные данные алгоритма. Вычет такой, что .
Шаг 1. Вычислить. Вычислить элементы gа,, упорядочить массив пар по второй координате.
Шаг 2. Вычислить. Для каждого b, проверить является ли элемент второй координатой какой-либо пары из упорядоченного массива пар. Если, то. Алгоритм заканчивает свою работу.
Покажем, что алгоритм действительно находит x. Так как, то можно представить, где. При этом .
Сложность алгоритма составляет операций в группе G. Объем использованной памяти составляет ячеек.
r-метод Полларда.Метод Полларда применим к любой группе G, чьи элементы представлены таким образом, что их можно разбить на три примерно равные части. При этом должно быть очень просто определить, к какому из этих подмножеств принадлежит данный элемент группы. Например, если, то можно взять
,, .
Интуитивно ясно, что эти множества примерно равны по величине. Но точное доказательство этого факта для в настоящее время не известно.
Определим функцию f на G таким образом, что
. (1)
Функция f обладает двумя свойствами.
Во-первых, функция f является псевдослучайным отображением, во-вторых, если логарифм а по основанию g имеет вид при известных a, b, то логарифм f(a) по основанию g имеет вид при известных a’, b’. Для метода Полларда подойдет любая функция, удовлетворяющая двум этим свойствам. Сформулируем сам алгоритм.
Входные данные алгоритма. Конечная циклическая группа G=<g> порядка m, элемент и функция f, заданная соотношением (1)..
Выходные данные алгоритма. Вычет такой, что .
Шаг 1. Выбрать случайный вычет, вычислить, положить .
Шаг 2. Для выполнить следующие действия: вычислить по формулам
, ,
А также 4 числа, где. Проверить выполнение равенства. Если это равенство не выполнено, то увеличить i на единицу и повторить вычисления шага 2.
Шаг 3. Из равенства следует, что
.
При найти вычет. Здесь дополнительно нужен перебор l вариантов. Если l велико, то перейти к шагу 1.
Замечание. Возможно, что функция, которая зафиксирована равенством (1) является «плохой», в том смысле, что число шагов алгоритма превзойдет разумные пределы (например, ) а неизвестный логарифм не будет вычислен. Тогда следует немного изменить функцию. Можно взять другое разбиение G или, например, при и т.п.
При анализе сложности алгоритма Полларда используют вероятностную модель, в соответствии с которой элементы последовательности появляются независимо с равными вероятностями. Тогда число членов последовательности до первого совпадения не превосходит с вероятностью. Поэтому, минимальное I, для которого, ограничено с вероятностью .
Распараллеливание r-метода Полларда.Пусть имеется Т процессоров, которые могут производить независимые вычисления и один центральный процессор. Зафиксируем и .
Предполагается, что для можно определить, которое обладает следующими свойствами:
1) легко определить принадлежность ;
2), т.е. вероятность попадания в случайного элемента из G равна .
Входные данные алгоритма. Конечная циклическая группа G=<g> порядка m, элемент и функция f, заданная соотношением (1).
Выходные данные алгоритма. Вычет такой, что .
Шаг 1. (вычислить последовательности) r-й процессор выбирает случайный вычет, вычисляет и строит элементы последовательности по правилу
, где, .
Для каждого проверить принадлежность. Если, то в памяти ЦП записать, выбрать новый случайный вычет и повторить вычисления. Если, то увеличить значение i на единицу и продолжить вычисления.
Шаг 2. (сортировка) Через 2к шагов (то есть когда каждый из процессоров вычислит не менее 2к элементов своей последовательности) центральный процессор сортирует массив троек по первой координате. Если для двух троек и выполнено, то переходим к шагу 3. В противном случае алгоритм заканчивает работу, не вычислив дискретный логарифм. Следует повторить весь алгоритм с самого начала.
Шаг 3. (вычисление логарифма) Из равенства получить сравнение
.
При найти вычет. Здесь дополнительно нужен перебор l вариантов. Если l велико, то перейти к шагу 1.
Сложность метода равна операций ( число шагов) при памяти объема О(Т) ячеек.
Индекс-метод логарифмирования в . В современном виде метод впервые сформулирован Адлеманом в работе [1]. Метод основан на использовании основной теоремы арифметики, которая утверждает, что каждое натуральное число однозначно представляется в виде произведения простых чисел. Пусть – множество первых простых чисел, не превосходящих В. Число В является параметром метода, а множество SB называется факторной базой. Из закона распределения простых чисел следует, что
.
Число x называется В-гладким, если оно разлагается в произведение простых чисел из факторной базы SB. Пусть g первообразный вычет по mod p и – произвольный ненулевой вычет. Требуется найти вычет такой, что. Обозначим через такой вычет, что,. Сформулируем алгоритм вычисляющий логарифм .
Входные данные алгоритма. Простое нечетное число p, первообразный вычет, – произвольный ненулевой вычет и число В.
Выходные данные алгоритма. Вычет такой, что .
Шаг 1. (набор линейных сравнений по mod (p-1)) Выбрать случайное число m,, найти вычет, .
Проверить число b на В-гладкость. Если b является В-гладким, то
.
Вывести отсюда сравнение .
Повторять выбор случайных m до тех пор, пока не будут построены линейных соотношений, то есть пока будет получена система линейных сравнений относительно неизвестных
, .
Здесь d – небольшое натуральное число. Заметим, что полученная система заведомо совместна.
Шаг 2. Решить полученную на предыдущем шаге систему линейных сравнений по mod (p-1) методом Гаусса. Если система не имеет однозначного решения, то вернуться на шаг 1 и получить несколько новых линейных соотношений. Затем вернуться к шагу 2.
Шаг 3. (вычисление логарифма) Выбрать случайное m,, найти вычет, .
Проверить число b на В-гладкость. Если b является В-гладким, то
,
и, следовательно,. Алгоритм заканчивает свою работу.
Замечание.
1) Для проверки числа b на В-гладкость надо осуществить пробные деления b на все простые числа и их степени .
2) Для увеличения вероятности В-гладкости вычеты лучше выбирать так, чтобы. Тогда свободные члены уравнений системы, полученных при отрицательных b, изменятся на, так как .
3) На шаге 2 система линейных сравнений решается методом Гаусса. Так как не является полем и имеются ненулевые необратимые элементы в, то не всякий шаг алгоритма Гаусса может быть реализован. Однако, на практике это не является существенным ограничением. Действительно, на главную диагональ можно стремиться ставить обратимые по mod(p-1) вычеты. Другой подход заключается в решении системы по, где – каноническое разложение числа p-1. Для этого достаточно уметь решать систему по простым модулям, то есть над полем. Решения по mod(p-1) тогда легко найти, применив китайскую теорему об остатках.
4) При увеличении В возрастает число неизвестных в системе линейных сравнений, решаемой на шаге 2. С другой стороны, при этом возрастает вероятность получения одного линейного соотношения. Наоборот, с уменьшением В число неизвестных и вероятность получения одного соотношения уменьшаются.
Таким образом, сложность алгоритма существенно зависит от В. Перед реализацией алгоритма стараются выбрать значение В, которое минимизирует сложность вычислений.
Приведем формулу, выражающую сложность этого метода как функцию от В и вычислим значение В при, для которого эта функция принимает свое минимальное значение.
Обозначим через Р(В) вероятность В-гладкости случайного числа b из интервала. Тогда сложность вычислений на шаге 1 оценивается величиной
операций деления чисел b, на простые числа и их степени. Сложность вычислений на шаге 2 оценивается величиной операций умножения чисел по mod p. Сложность вычислений на шаге 3 оценивается величиной операций деления чисел b, на простые числа и их степени .
Сложность всего алгоритма есть сумма. Однако, сложность последнего шага меньше сложности первого шага в раз. Поэтому считают, что сложность метода выражается суммой .
Асимптотическая оценка сложности приведенного выше индекс-метода
выражается формулой
(2)
двоичных операций.
Сравним оценку сложности индекс – метода с оценкой сложности методов Гельфонда-Шенкса и Полларда. Последние два метода имеют оценку сложности порядка операций при и фиксированном числе процессоров, которые могут работать параллельно. С другой стороны, функцию (2) можно записать в виде, где
при. Отсюда следует, что индекс – метод имеет субэкспоненциальную оценку сложности, в то время как сложность методов Гельфонда – Шенкса и Полларда экспоненциальна при .
Пример [2]. Пусть p=229. Первообразным вычетом в является. Решим уравнение. Выберем В=11,. Имеют место следующие шесть соотношений относительно логарифмов простых по основанию, которые получены случайным выбором показателей m (сравнения, которые не дают гладких вычетов ниже не приводятся)
,
,
,
,
,
.
Обозначим логарифмы вычетов по основанию 6 через. Тогда имеем систему линейных сравнений по mod 228
.
Решение этой системы имеет вид
.
Для вычисления выберем m=77. Тогда
.