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

в математика из действительные числа, то логарифм бревно_б а это число Икс такой, что б^Икс = а, для заданных чисел а и б. Аналогично, в любом группа г, полномочия б^k можно определить для всех целые числа k, а дискретный логарифм бревно_б а это целое число k такой, что б^k = а. В теория чисел, чаще используется термин показатель: мы можем написать Икс = ind_р а (модм) (прочтите индекс а к базе р по модулюм) за р^Икс ≡ а (модм) если р это первобытный корень из м и gcd (а,м) = 1.

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

Определение

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

${\displaystyle b^{k}=\underbrace {b\cdot b\cdots b} _{k\;{\text{factors}}}.}$

Аналогично пусть б^-k обозначают произведение б⁻¹ с собой k раз. За k = 0 и б ≠ 0, k-я сила - это личность: б⁰ = 1.

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

Примеры

Степени 10

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

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

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

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

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

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

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

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

Полномочия личности

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

Характеристики

Полномочия подчиняются обычному алгебраическому тождеству б^{k + л} = б^k б^л. Другими словами, функция

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

определяется ж(k) = б^k это групповой гомоморфизм из целых чисел Z под дополнением на то подгруппа ЧАС из г генерируется к б. Для всех а в ЧАС, бревно_б а существуют. И наоборот, log_б а не существует для а что не в ЧАС.

Если ЧАС бесконечно, то log_б а также уникален, и дискретный логарифм составляет групповой изоморфизм

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

С другой стороны, если ЧАС имеет конечный размер п, затем войдите_б а уникален только до сравнения по модулю п, а дискретный логарифм составляет групповой изоморфизм

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

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

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

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

Алгоритмы

Смотрите также: Записи дискретного логарифма

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

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

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

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

• Бэби-степ гигантский шаг
• Функциональное поле сито
• Алгоритм расчета индекса
• Сито числового поля
• Алгоритм Полига – Хеллмана
• Алгоритм ро Полларда для логарифмов
• Алгоритм кенгуру Полларда (он же лямбда-алгоритм Полларда)

Есть действенный квантовый алгоритм из-за Петр Шор.^[1]

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

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

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

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

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

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

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

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

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

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

Оказывается, большая часть интернет-трафика использует одну из нескольких групп, имеющих порядок 1024 бит или меньше, например циклические группы с порядком простых чисел Окли, указанным в RFC 2409. В Затор атака использовала эту уязвимость для компрометации различных интернет-сервисов, которые позволяли использовать группы, порядок которых был 512-битным простым числом, так называемым экспортный сорт.^[2]

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

Рекомендации

1. Шор, Питер (1997). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". SIAM Журнал по вычислениям. 26 (5): 1484–1509. arXiv:Quant-ph / 9508027. Дои:10.1137 / s0097539795293172. Г-Н  1471990. S2CID  2337707.
2. Адриан, Дэвид; Бхаргаван, Картикеян; Дурумерик, Закир; Годри, Пьеррик; Грин, Мэтью; Халдерман, Дж. Алекс; Хенингер, Надя; Спринголл, Дрю; Томе, Эммануэль; Валента, Люк; VanderSloot, Бенджамин; Вустров, Эрик; Занелла-Бегелен, Сантьяго; Циммерманн, Пауль (октябрь 2015 г.). "Несовершенная прямая секретность: как Диффи-Хеллман терпит неудачу на практике" (PDF).

• Розен, Кеннет Х. (2011). Элементарная теория чисел и ее применение (6-е изд.). Пирсон. п. 368. ISBN  978-0321500311.
• Вайсштейн, Эрик В. «Дискретный логарифм». MathWorld. Wolfram Web. Получено 1 января 2019.

дальнейшее чтение

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