Введение

Проблема инвертирования возведения в степень в конечных группах

В математике, для заданных вещественных чисел a и b, логарифм logb a – это число x, такое что bx = a. Аналогично, в любой группе G степени bk могут быть определены для всех целых чисел k, и дискретный логарифм logb a – это целое число k, такое что bk = a. В теории чисел более распространенным термином является индекс: мы можем записать x = indr a (mod m) (читается "индекс a по основанию r по модулю m") для r x ≡ a (mod m), если r является примитивным корнем по модулю m и НОД(a, m) = 1. Дискретные логарифмы быстро вычисляются в нескольких частных случаях, однако не существует эффективного метода для их вычисления в общем случае. В криптографии вычислительная сложность задачи дискретного логарифмирования и ее применение впервые были рассмотрены в задаче Диффи — Хеллмана. Несколько важных алгоритмов в криптографии с открытым ключом, таких как ElGamal, основывают свою безопасность на предположении о сложности задачи дискретного логарифма (DLP) для тщательно выбранных групп, то есть на отсутствии эффективного решения.

Определение

Пусть G — произвольная группа. Обозначим групповую операцию умножением, а единичный элемент — 1. Пусть b — произвольный элемент G. Для любого положительного целого числа k выражение bk обозначает произведение b, повторенное k раз:

Аналогично, b−k обозначает произведение b−1, повторенное k раз. При k = 0, k-я степень равна единичному элементу: 1 = b0 = 1. Пусть a также является элементом G. Целое число k, являющееся решением уравнения bk = a, называется дискретным логарифмом (или просто логарифмом) a по основанию b. Обозначают k = logb a.

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

Аналогичный пример справедлив для любого ненулевого действительного числа b. Степени образуют мультипликативную подгруппу G = {…, b⁻³, b⁻², b⁻¹, 1, b¹, b², b³, …} множества ненулевых действительных чисел. Для любого элемента a из G можно вычислить logb a.

Модульная арифметика

Одной из простейших областей применения дискретных логарифмов является группа Zp×. Это группа умножения по модулю p. Её элементы – это ненулевые классы вычетов по модулю p, а групповое произведение двух элементов можно получить, выполнив обычное целочисленное умножение элементов с последующим приведением по модулю p.

k-я степень одного из чисел в этой группе можно вычислить, найдя его k-ю степень как целое число, а затем найдя остаток от деления на p. Когда числа большие, эффективнее выполнять приведение по модулю p несколько раз в процессе вычисления. Независимо от используемого алгоритма, эта операция называется возведением в степень по модулю. Например, рассмотрим Z17×. Чтобы вычислить 3⁴ в этой группе, вычислим 3⁴ = 81, а затем разделим 81 на 17, получив остаток 13. Таким образом, 3⁴ = 13 в группе Z17×. Дискретный логарифм – это обратная операция. Например, рассмотрим уравнение 3ᵏ ≡ 13 (mod 17). Из приведенного выше примера, одно решение – k = 4, но это не единственное решение. Поскольку 3¹⁶ ≡ 1 (mod 17) – что следует из малой теоремы Ферма – также следует, что если n – целое число, то 3⁴ + 16n ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 13 (mod 17). Следовательно, уравнение имеет бесконечно много решений вида 4 + 16n. Кроме того, поскольку 16 – наименьшее положительное целое число m, удовлетворяющее 3ᵐ ≡ 1 (mod 17), это единственные решения. Эквивалентно, множество всех возможных решений можно выразить ограничением k ≡ 4 (mod 16).

Полномочия идентификатора

В особом случае, когда b является единичным элементом 1 группы G, дискретный логарифм logb a не определен для a, отличного от 1, и любое целое число k является дискретным логарифмом для a = 1.

Свойства

Степени подчиняются обычной алгебраической тождественности bk + l = bk bl.

Эффективные классические алгоритмы также существуют в определенных частных случаях. Например, в группе целых чисел по модулю p относительно сложения, степень bk превращается в произведение bk, а равенство означает сравнимость по модулю p. Расширенный алгоритм Евклида быстро находит k. В протоколе Диффи — Хеллмана используется модуль циклической группы, равный простому числу p, что позволяет эффективно вычислять дискретный логарифм с помощью алгоритма Поллига — Хеллмана, если порядок группы (равный p−1) достаточно гладкий, то есть не имеет больших простых множителей.

Криптография

Существуют группы, для которых вычисление дискретных логарифмов представляется сложной задачей. В некоторых случаях (например, подгруппы большого простого порядка в группах Zp×) не только неизвестны эффективные алгоритмы для худшего случая, но и сложность в среднем случае может быть показана примерно равной сложности худшего случая с использованием случайной саморедукции. В то же время, обратная задача – дискретное возведение в степень – не является сложной (её можно эффективно вычислить, например, с помощью возведения в степень в квадрате). Эта асимметрия аналогична асимметрии между факторизацией целых чисел и умножением целых чисел. Обе эти асимметрии (и другие, возможно, односторонние функции) были использованы при построении криптографических систем. Популярными вариантами для группы G в криптографии на основе дискретных логарифмов (DLC) являются циклические группы Zp× (например, шифрование Эль-Гамаля, обмен ключами Диффи — Хеллмана и алгоритм цифровой подписи) и циклические подгруппы эллиптических кривых над конечными полями (см. Криптография на эллиптических кривых). Хотя публично известного алгоритма для решения задачи дискретного логарифма в общем случае не существует, первые три шага алгоритма решета числового поля зависят только от группы G, а не от конкретных элементов G, дискретный логарифм которых требуется найти. Предварительно вычислив эти три шага для конкретной группы, необходимо выполнить только последний шаг, который значительно менее затратен в вычислительном плане, чем первые три, чтобы получить конкретный логарифм в этой группе. В атаке Logjam эта уязвимость была использована для компрометации ряда интернет-сервисов, которые позволяли использовать группы, порядок которых представлял собой 512-битное простое число, так называемый экспортный стандарт.