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

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

В математике , при заданных действительных чисел и б , то логарифм журнал _Ь представляет собой число х такое , что б ^х = . Аналогично, в любой группе G степени b ^k могут быть определены для всех целых чисел k , а дискретный логарифм log _b a - это целое число k такое, что b ^k = a . В теории чисел чаще используется термин   Индекс : можно записать х = Ind _г а ( по модулю  т ) (читать «индекс к базовому г по модулю  т ») для г ^х ≡ ( по модулю  т ) , если г является первообразным корнем из м и НОДА ( , м ) = 1.

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

Определение

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

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

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

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

Примеры

Степени 10

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

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

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

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

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

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

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

Дискретный логарифм - это просто обратная операция. Например, рассмотрим уравнение 3 ^k ≡ 13 (mod 17) для k . Из приведенного выше примера одно решение - 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 . Другими словами, функция

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

определяется F ( K ) = Ь ^к является групповым гомоморфизмом из целых чисел Z при добавлении на на подгруппы H из G , генерируемой с помощью б . Для всех a в H существует log _b  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 .

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

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

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

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

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

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

Хотя вычисление дискретных логарифмов и разложение целых чисел на множители представляют собой разные проблемы, они обладают некоторыми общими свойствами:

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

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

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

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

Популярный выбор для группы G в дискретной логарифм криптография (DLC) являются циклическими группами ( Z _р ) ^× (например ElGamal шифрования , обмена ключами Диффи-Хеллмана , и алгоритм цифровой подписи ) и циклические подгруппы эллиптических кривых над конечными полями ( смотри Криптография на эллиптических кривых ).

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

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

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

использованная литература

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

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

Смотрите также

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