Задача дискретного логарифмирования

Пусть С — конечная мультипликативная группа. Задача дискретного логарифмирования состоит в решении уравнения а^х = Ь при а_у Ь е С относительно целого х_у где 0 <�х < п и п = огб а. Решение уравнения называют дискретным логарифмом (или индексом) числа Ь по основанию а, обозначается log"& или т?_аЬ.

Для решения данной задачи предложен ряд общих и специальных методов. Простейший общий метод называется методом бюльших-малых шагов, идея метода близка к идее метода согласования. Пусть 7/г = |" л/я" |. Метод состоит в поиске совпадения члена ряда (1, а, а²,…, а^т ~ *) с членом ряда (/?, Ьа~^ту Ьа~^2т,…, Ьа-(т-1)т).

Первый ряд вычисляется и в упорядоченном виде записывается в память размера т. Далее последовательно вычисляются члены второго ряда до совпадения с одним из членов первого ряда. Если а) — Ьаг^1т, то aJ^+im = = b и log_ab = (j + ini) mod п. Алгоритм требует О (т) умножений в группе G и память порядка 0(т). Следовательно, для обеспечения криптографической стойкости системы с открытым ключом, равносильной стойкости блочного шифра со 128-битовым ключом, следует выбирать группы, порядок которых имеет большой простой делитель с длиной записи не меньше 256 бит.

Метод Нечаева — Полит — Хеллмана¹ развивает данный метод.

Пусть п = qr, где q простое, тогда:

• 1) методом болыиих-малых шагов находится решение х_х уравнения (a^ryi = b^r в диапазоне 0 < х_{ < q, где q = orda';
• 2) находится решение х₂ уравнения (a^q)^xi = ha~^xi в диапазоне 0 < х₂ < г, где г = ord a⁽f;
• 3) определяется решение х = x₂q + х_{.

Если г простое, то шаг 2 выполняют методом больших-малых шагов. При составном г уравнение снова заменяется двумя уравнениями и т. д. При известном каноническом разложении числа ord# = п для вычисления.

log_(tb требуется умножений в группе G. Наиболее трудными для метода Нечаева — Пол ига — Хеллмана являются задачи дискретного логарифмирования в группах, порядок которых имеет большой простой делитель.

Для нахождения логарифма в простом поле F_p используют индексметод^[1][2]:

• 1) выбирают базу простых множителей 5= {р_{,…, pj;
• 2) находят пары натуральных чисел (?, т^_у где 1 < m_t < q — 2 и b_t =
• 3) составляют систему из t уравнений относительно Хр где х_} — log₍р_р 7=1,…, 5, и? должно быть достаточным для однозначного решения системы уравнений

• 4) находят пару натуральных чисел (р, р) таких, что 1 < р < q — 2 и ba*¹ modд = p"^{…p^u_s^s
• 5) искомый логарифм есть х = (и_хх_х + … + u_sx_s — р) mod (q — 1).

Сложность индекс-метода L_q( ½, с), где с > 0 — константа. Наиболее эффективная модификация, метод решета числового поля, имеет сложность ?^(1/3, (64/9)V3). Таким образом, для конечных полей предложены алгоритмы логарифмирования за субэкспоненциальное время.

Существует техника дискретного логарифмирования на основе идей Полларда случайного блуждания в группе (p-метод). Такие методы не требуют много компьютерной памяти и имеют среднюю сложность 0(у[у), где у — большой простой делитель порядка группы.

• [1] Нечаев В. И. Элементы криптографии (Основы теории защиты информации): учеб, пособие для университетов и педагогических вузов / под ред. В. А. Садовничего. М.: Высшаяшкола, 1999.
• [2] Adleman L. A subexponential algorithm for the discrete logarithm problem with applicationsto cryptography // IEEE 18th Ann. Symp. on Found, of Comp. Sc. 1979. P. 55—60.