Дискретный логарифм

В математике для заданных действительных чисел a и b логарифм log _b a — это число x, такое что b ^x = a . Аналогично, в любой группе G степени b ^k могут быть определены для всех целых чисел k , а дискретный логарифм log _b a — это целое число k, такое что b ^k = a . В арифметике по модулю целого числа m более часто используемым термином является индекс : можно записать k = ind _b a (mod  m ) (читается «индекс числа a по основанию b по модулю m ») для b ^k ≡ a (mod  m ), если k — примитивный корень числа m и gcd ( a , m ) = 1.    

Дискретные логарифмы быстро вычисляются в нескольких особых случаях. Однако не известно эффективного метода для их вычисления в общем случае. В криптографии вычислительная сложность задачи дискретного логарифма, вместе с ее применением, была впервые предложена в задаче Диффи–Хеллмана . Несколько важных алгоритмов в криптографии с открытым ключом , такие как ElGamal , основывают свою безопасность на предположении о сложности , что задача дискретного логарифма (DLP) над тщательно выбранными группами не имеет эффективного решения. ^[1]

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

${\displaystyle b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{факторы}}}.}$

Аналогично, пусть b ^{− k} обозначает произведение b ⁻¹ на себя k раз. При k = 0 степень k является тождеством: b ⁰ = 1 .

Пусть a также будет элементом G. Целое число k , которое решает уравнение b ^k = a, называется дискретным логарифмом (или просто логарифмом в данном контексте) числа a по основанию b . Записывается как k  = log _b  a .

Степени числа 10 :

${\displaystyle \ldots ,0.001,0.01,0.1,1,10,100,1000,\ldots .}$

Для любого числа a в этом списке можно вычислить log ₁₀  a . Например, log ₁₀  10000 = 4 и log ₁₀  0,001 = −3. Это примеры задачи дискретного логарифма.

Другие десятичные логарифмы в действительных числах не являются примерами проблемы дискретного логарифма, поскольку они включают нецелые показатели. Например, уравнение log ₁₀  53 = 1,724276… означает, что 10 ^1,724276… = 53. В то время как целые показатели могут быть определены в любой группе с использованием произведений и обратных величин, произвольные действительные показатели, такие как 1,724276…, требуют других понятий, таких как показательная функция .

В терминах теории групп степени числа 10 образуют циклическую группу G при умножении, а число 10 является генератором этой группы. Дискретный логарифм log ₁₀  a определен для любого a из G.

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

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

Степень k одного из чисел в этой группе можно вычислить, найдя ее степень k как целое число, а затем найдя остаток после деления на p . Когда задействованные числа большие, более эффективно несколько раз уменьшать по модулю p во время вычисления. Независимо от конкретного используемого алгоритма, эта операция называется модульным возведением в степень . Например, рассмотрим Z ₁₇ ^× . Чтобы вычислить 3 ⁴ в этой группе, вычислите 3 ⁴ = 81, а затем разделите 81 на 17, получив остаток 13. Таким образом, 3 ⁴ = 13 в группе Z ₁₇ ^× .

Дискретный логарифм — это просто обратная операция. Например, рассмотрим уравнение 3 ^k ≡ 13 (mod 17). Из приведенного выше примера одно решение — k  = 4, но это не единственное решение. Поскольку 3 ¹⁶ ≡ 1 (mod 17) — как следует из малой теоремы Ферма — также следует, что если n — целое число, то 3 ^{4+16 n} ≡ 3 ⁴ × (3 ¹⁶ ) ⁿ ≡ 13 × 1 ⁿ ≡ 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] Другими словами, функция

${\displaystyle f\colon \mathbf {Z} \to G}$

определяемый как f ( k ) = b ^k является гомоморфизмом групп из целых чисел Z при сложении на подгруппу H группы G , порожденную b . Для всех a из H , log _b a существует. Обратно , log _b a не существует для a , которые не находятся в H .  

Если H бесконечно , то log _b a также уникален, а дискретный логарифм представляет собой групповой изоморфизм 

${\displaystyle \log _{b}\colon H\to \mathbf {Z} .}$

С другой стороны, если H конечен порядка n , то log _b a уникален только с точностью до сравнения по модулю n , а дискретный логарифм представляет собой групповой изоморфизм 

${\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}$

где Z _n обозначает аддитивную группу целых чисел по модулю n .

Знакомая формула замены основания для обычных логарифмов остается в силе: если c — другой генератор H , то

${\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

Задача дискретного логарифма считается вычислительно неразрешимой. То есть, неизвестен ни один эффективный классический алгоритм для вычисления дискретных логарифмов в целом.

Общий алгоритм для вычисления 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]

• AW Faber Модель 366
• Перси Ладгейт и ирландский логарифм

• Ричард Крэндалл ; Карл Померанс . Глава 5, Простые числа: вычислительная перспектива , 2-е изд., Springer.
• Стинсон, Дуглас Роберт (2006). Криптография: теория и практика (3-е изд.). Лондон, Великобритания: CRC Press . ISBN 978-1-58488-508-5.