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

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Октябрь 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 {факторы}}}.}$

Аналогично, пусть 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 \ двоеточие \ mathbf {Z} \ to G}$

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

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

${\ displaystyle \ log _ {b} \ двоеточие H \ to \ mathbf {Z}.}$

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

${\ displaystyle \ log _ {b} \ двоеточие 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 . Затор атака использовал эту уязвимость , чтобы поставить под угрозу целый ряд интернет - услуг , что позволило использование групп, порядок был 512-битное простое число, так называемый экспортный сорт . ^[2]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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