В математике для заданных действительных чисел a и b логарифм log b a — это число x, такое что b x = a . Аналогично, в любой группе G степени b k могут быть определены для всех целых чисел k , а дискретный логарифм log b a — это целое число k, такое что b k = a . В теории чисел более часто используемый термин — индекс : мы можем записать x = ind r a (mod m ) (читается «индекс a по основанию r по модулю m ») для r x ≡ a (mod m ), если r — примитивный корень из m и gcd ( a , m ) = 1.
Дискретные логарифмы быстро вычисляются в нескольких особых случаях. Однако не известно эффективного метода для их вычисления в общем случае. В криптографии вычислительная сложность задачи дискретного логарифма, вместе с ее применением, была впервые предложена в задаче Диффи–Хеллмана . Несколько важных алгоритмов в криптографии с открытым ключом , такие как ElGamal , основывают свою безопасность на предположении о сложности , что задача дискретного логарифма (DLP) над тщательно выбранными группами не имеет эффективного решения. [1]
Пусть G — любая группа. Обозначим ее групповую операцию умножением, а ее единичный элемент — 1. Пусть b — любой элемент группы G. Для любого положительного целого числа k выражение b k обозначает произведение b на себя k раз: [2]
Аналогично, пусть b − k обозначает произведение b −1 на себя k раз. При k = 0 степень k является тождеством: b 0 = 1 .
Пусть a также будет элементом G. Целое число k , которое решает уравнение b k = a, называется дискретным логарифмом (или просто логарифмом в данном контексте) числа a по основанию b . Записывается как k = log b a .
Степени числа 10 :
Для любого числа a в этом списке можно вычислить log 10 a . Например, log 10 10000 = 4 и log 10 0,001 = −3. Это примеры задачи дискретного логарифма.
Другие десятичные логарифмы в действительных числах не являются примерами проблемы дискретного логарифма, поскольку они включают нецелые показатели. Например, уравнение log 10 53 = 1,724276… означает, что 10 1,724276… = 53. В то время как целые показатели могут быть определены в любой группе с использованием произведений и обратных величин, произвольные действительные показатели, такие как 1,724276…, требуют других понятий, таких как показательная функция .
В терминах теории групп степени числа 10 образуют циклическую группу G при умножении, а число 10 является генератором этой группы. Дискретный логарифм log 10 a определен для любого a из G.
Аналогичный пример справедлив для любого ненулевого действительного числа b . Степени образуют мультипликативную подгруппу G = {…, b −3 , b −2 , b −1 , 1, b 1 , b 2 , b 3 , …} ненулевых действительных чисел. Для любого элемента a из G можно вычислить log b a .
Одной из простейших установок для дискретных логарифмов является группа Z p × . Это группа умножения по модулю простого числа p . Ее элементы являются ненулевыми классами конгруэнтности по модулю p , а групповое произведение двух элементов может быть получено обычным целочисленным умножением элементов с последующим сокращением по модулю p .
Степень k одного из чисел в этой группе можно вычислить, найдя ее степень k как целое число, а затем найдя остаток после деления на p . Когда задействованные числа большие, более эффективно несколько раз уменьшать по модулю p во время вычисления. Независимо от конкретного используемого алгоритма, эта операция называется модульным возведением в степень . Например, рассмотрим Z 17 × . Чтобы вычислить 3 4 в этой группе, вычислите 3 4 = 81, а затем разделите 81 на 17, получив остаток 13. Таким образом, 3 4 = 13 в группе Z 17 × .
Дискретный логарифм — это просто обратная операция. Например, рассмотрим уравнение 3 k ≡ 13 (mod 17). Из приведенного выше примера одно решение — k = 4, но это не единственное решение. Поскольку 3 16 ≡ 1 (mod 17) — как следует из малой теоремы Ферма — также следует, что если n — целое число, то 3 4+16 n ≡ 3 4 × (3 16 ) n ≡ 13 × 1 n ≡ 13 (mod 17). Следовательно, уравнение имеет бесконечно много решений вида 4 + 16 n . Более того, поскольку 16 — наименьшее положительное целое число m, удовлетворяющее 3 m ≡ 1 (mod 17), это единственные решения. Эквивалентно, множество всех возможных решений можно выразить ограничением, что k ≡ 4 (mod 16).
В частном случае, когда b является единичным элементом 1 группы G , дискретный логарифм log b a не определен для a, отличного от 1, и каждое целое число k является дискретным логарифмом для a = 1.
Степени подчиняются обычному алгебраическому тождеству b k + l = b k b l . [2] Другими словами, функция
определяемый как f ( k ) = b k является гомоморфизмом групп из целых чисел Z при сложении на подгруппу H группы G , порожденную b . Для всех a из H , log b a существует. Обратно , log b a не существует для a , которые не находятся в H .
Если H бесконечно , то log b a также уникален, а дискретный логарифм представляет собой групповой изоморфизм
С другой стороны, если H конечен порядка n , то log b a уникален только с точностью до сравнения по модулю n , а дискретный логарифм представляет собой групповой изоморфизм
где Z n обозначает аддитивную группу целых чисел по модулю n .
Знакомая формула замены основания для обычных логарифмов остается в силе: если c — другой генератор H , то
Задача дискретного логарифма считается вычислительно неразрешимой. То есть, неизвестен ни один эффективный классический алгоритм для вычисления дискретных логарифмов в целом.
Общий алгоритм для вычисления log b a в конечных группах G заключается в возведении b во все большие и большие степени k до тех пор, пока не будет найдено требуемое a . Этот алгоритм иногда называют пробным умножением . Он требует времени выполнения, линейного по размеру группы G и, таким образом, экспоненциального по количеству цифр в размере группы. Следовательно, это алгоритм с экспоненциальным временем, практичный только для небольших групп G .
Существуют более сложные алгоритмы, обычно вдохновленные похожими алгоритмами для факторизации целых чисел . Эти алгоритмы работают быстрее, чем наивный алгоритм, некоторые из них пропорциональны квадратному корню размера группы, и, таким образом, экспоненциальны в половине количества цифр в размере группы. Однако ни один из них не работает за полиномиальное время (по количеству цифр в размере группы).
Эффективный квантовый алгоритм был разработан Питером Шором . [3]
Эффективные классические алгоритмы существуют также в некоторых особых случаях. Например, в группе целых чисел по модулю p при сложении степень b k становится произведением bk , а равенство означает сравнение по модулю p в целых числах. Расширенный алгоритм Евклида быстро находит k .
В случае Диффи–Хеллмана используется циклическая группа по модулю простого числа p , что позволяет эффективно вычислять дискретный логарифм с помощью Полига–Хеллмана, если порядок группы (равный p −1) достаточно гладкий , т.е. не имеет больших простых множителей .
Хотя вычисление дискретных логарифмов и целочисленная факторизация представляют собой разные задачи, у них есть некоторые общие свойства:
Существуют группы, для которых вычисление дискретных логарифмов, по-видимому, затруднительно. В некоторых случаях (например, большие подгруппы простых порядков групп Z p × ) не только не существует эффективного алгоритма, известного для худшего случая, но и сложность в среднем случае может быть показана примерно такой же сложной, как и в худшем случае, используя случайную самоприводимость . [4]
В то же время, обратная задача дискретного возведения в степень не является сложной (например, ее можно эффективно вычислить, используя возведение в степень путем возведения в квадрат ). Эта асимметрия аналогична асимметрии между факторизацией целых чисел и умножением целых чисел. Обе асимметрии (и другие, возможно, односторонние функции ) использовались при построении криптографических систем.
Популярным выбором для группы G в дискретной логарифмической криптографии (DLC) являются циклические группы Z p × (например, шифрование Эль-Гамаля , обмен ключами Диффи–Хеллмана и алгоритм цифровой подписи ) и циклические подгруппы эллиптических кривых над конечными полями ( см. Криптография на эллиптических кривых ).
Хотя не существует общедоступного алгоритма для решения задачи дискретного логарифма в целом, первые три шага алгоритма решета числового поля зависят только от группы G , а не от конкретных элементов G , конечный логарифм которых требуется. Предварительно вычисляя эти три шага для конкретной группы, нужно выполнить только последний шаг, который гораздо менее затратен в вычислительном отношении, чем первые три, чтобы получить конкретный логарифм в этой группе. [5]
Оказывается, что большая часть интернет- трафика использует одну из немногих групп, имеющих порядок 1024 бит или меньше, например, циклические группы с порядком простых чисел Окли, указанным в RFC 2409. [6] Атака Logjam использовала эту уязвимость для компрометации различных интернет-сервисов, которые позволяли использовать группы, порядок которых был 512-битным простым числом, так называемый экспортный класс . [5]
Авторы атаки Logjam оценивают, что гораздо более сложные предварительные вычисления, необходимые для решения задачи дискретного логарифма для 1024-битного простого числа, будут в пределах бюджета крупного национального разведывательного агентства, такого как Агентство национальной безопасности США (АНБ). Авторы Logjam предполагают, что предварительные вычисления против широко используемых 1024 простых чисел DH стоят за утверждениями в просочившихся документах АНБ о том, что АНБ способно взломать большую часть современной криптографии. [5]
