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

редактировать

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

Дискретный логарифмы вычисляются быстро в некоторых особых случаях. Однако в целом не известен эффективный метод их вычисления. Несколько важных алгоритмов в криптографии с открытым ключом основывают свою безопасность на предположении, что проблема дискретного логарифмирования для тщательно выбранных групп не имеет эффективного решения.

Содержание

  • 1 Определение
  • 2 Примеры
    • 2.1 Степень 10
    • 2.2 Степень фиксированного действительного числа
    • 2.3 Модульная арифметика
    • 2.4 Степень идентичности
  • 3 Свойства
  • 4 Алгоритмы
  • 5 Сравнение с целочисленной факторизацией
  • 6 Криптография
  • 7 Ссылки
  • 8 Дополнительная литература

Определение

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

bk = b ⋅ b ⋯ b ⏟ k факторов. {\ displaystyle b ^ {k} = \ underbrace {b \ cdot b \ cdots b} _ {k \; {\ text {factor}}}.}{\ displaystyle b ^ {k} = \ underbrace {b \ cdot b \ cdots b} _ {k \; {\ text {факторы}}}.}

Аналогично, пусть b обозначает произведение b на себя k раз. Для k = 0 и b 0 k-я степень является тождеством: b = 1.

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

Примеры

Степени 10

Степени 10 образуют бесконечное подмножество G = {…, 0,001, 0,01, 0,1, 1, 10, 100, 1000,… } рациональных чисел. Этот набор G является циклической группой при умножении, а 10 является образующей. Для любого элемента a группы можно вычислить log 10 a. Например, log 10 10000 = 4, а log 10 0,001 = −3. Это примеры проблемы дискретного логарифмирования.

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

Степени фиксированного действительного числа

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

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

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

k-я степень одного из чисел в этой группе может быть вычислена путем нахождения его k-й степени как целого числа, а затем нахождения остатка после деления на p. Когда задействованные числа большие, более эффективно уменьшить по модулю p несколько раз во время вычисления. Независимо от конкретного используемого алгоритма, эта операция называется модульным возведением в степень. Например, рассмотрим (Z17). Чтобы вычислить 3 в этой группе, вычислите 3 = 81, а затем разделите 81 на 17, получив остаток 13. Таким образом, 3 = 13 в группе (Z17).

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

Степень идентичности

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

Свойства

Степени подчиняются обычному алгебраическому тождеству b = b b. Другими словами, функция

f: Z → G {\ displaystyle f: \ mathbf {Z} \ rightarrow G}{\ displaystyle f: \ mathbf {Z} \ rightarrow G}

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

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

log b: H → Z. {\ displaystyle \ log _ {b} \ двоеточие H \ rightarrow \ mathbf {Z}.}\ log _ {b} \ двоеточие H \ rightarrow \ mathbf {Z}.

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

log b: H → Z n, {\ displaystyle \ log _ {b} \ двоеточие H \ rightarrow \ mathbf {Z} _ {n}, }\ log _ {b } \ двоеточие H \ rightarrow \ mathbf {Z} _ {n},

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

Известная формула изменения базы для обыкновенных логарифмов остается в силе: если c - еще один генератор H, то

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

Алгоритмы

Question, Web Fundamentals.svg Нерешенная проблема в информатике :. Можно ли вычислить дискретный логарифм за полиномиальное время на классическом компьютере? (другие нерешенные проблемы в информатике)

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

Общий алгоритм для вычисления log b a в конечных группах G состоит в возведении b в все большие и большие степени k, пока не будет найдено желаемое a. Этот алгоритм иногда называют пробным умножением. Для этого требуется время работы, линейное по размеру группы G и, следовательно, экспоненциальное по количеству цифр в размеру группы. Следовательно, это алгоритм экспоненциального времени, применимый только для небольших групп G.

Существуют более сложные алгоритмы, обычно основанные на аналогичных алгоритмах для целочисленной факторизации. Эти алгоритмы работают быстрее, чем наивные алгоритмы, некоторые из них пропорциональны квадратному корню из размера группы и, следовательно, экспоненциально в два раза меньше числа цифр в размере группы. Однако ни один из них не выполняется за полиномиальное время (по количеству цифр в размере группы).

Существует эффективный квантовый алгоритм благодаря Питеру Шору.

Эффективные классические алгоритмы также существуют в некоторых особых случаях. Например, в группе целых чисел по модулю p при сложении степень b становится произведением bk, а равенство означает сравнение целых чисел по модулю p. расширенный алгоритм Евклида быстро находит k.

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

Сравнение с целочисленной факторизацией

При вычислении дискретных логарифмов и разложение целых чисел на множители - разные проблемы, у них есть некоторые общие свойства:

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

Существуют группы, для которых вычисление дискретного логарифа мс видимо сложно. В некоторых случаях (например, большие подгруппы групп простого порядка (Zp)) не только не существует эффективного алгоритма, известного для наихудшего случая, но можно показать, что средняя сложность примерно такая же трудная как наихудший случай с использованием случайной самовосстановимости.

В то же время обратная задача дискретного возведения в степень несложна (например, ее можно эффективно вычислить с помощью возведения в степень возведения в квадрат ). Эта асимметрия аналогична асимметрии между целочисленной факторизацией и целочисленным умножением. Обе асимметрии (и другие, возможно, односторонние функции ) были использованы при построении криптографических систем.

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

Хотя в целом нет общеизвестного алгоритма для решения задачи дискретного логарифмирования, первые три шага алгоритма числового поля решета зависят только от группы G, а не от конкретных элементов группы G, конечный журнал которой требуется. При предварительном вычислении этих трех шагов для конкретной группы нужно выполнить только последний шаг, который требует гораздо меньше вычислительных ресурсов, чем первые три, чтобы получить конкретный логарифм в этой группе.

Оказывается, большая часть интернет-трафика использует одну из нескольких групп размером порядка 1024 бит или меньше, например циклические группы с порядком простых чисел Оукли, указанным в RFC 2409. Атака Logjam использовала эту уязвимость для компрометации различных интернет-сервисов, которые позволяли использовать группы, порядок которых был 512-битным простым числом, так называемый уровень экспорта.

Авторы Атака Logjam оценивает, что гораздо более сложный предварительный расчет, необходимый для решения проблемы дискретного журнала для 1024-битного простого числа, будет в рамках бюджета крупного национального разведывательного агентства, такого как США Агентство национальной безопасности (АНБ). Авторы Logjam предполагают, что предварительные вычисления против широко используемых 1024 простых чисел DH лежат в основе утверждений в просочившихся документах NSA о том, что NSA способно взломать большую часть текущей криптографии.

Ссылки

Далее чтение

  • Ричард Крэндалл ; Карл Померанс. Глава 5, Простые числа: вычислительная перспектива, 2-е изд., Springer.
  • Стинсон, Дуглас Роберт (2006), Криптография: теория и практика (3-е изд.), Лондон: CRC Press, ISBN 978-1-58488-508-5
Последняя правка сделана 2021-05-17 08:48:02
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте