В математике для данных действительных чисел a и b логарифм log b a представляет собой число x такое, что b x = a . Аналогично, в любой группе G степени bk могут быть определены для всех целых чисел k , а дискретный логарифм log b a представляет собой целое число k такое, что b k = a . В теории чисел более часто используемый термин — индекс : мы можем написать x = ind r a (mod m ) (читай «индекс a по основанию r по модулю m ») для r x ≡ a (mod m ), если r является первообразным корнем числа m и НОД ( a , m ) = 1.
Дискретные логарифмы можно быстро вычислить в некоторых особых случаях, однако в целом не известно эффективного метода их вычисления. В криптографии вычислительная сложность задачи дискретного логарифмирования и ее применения была впервые предложена в задаче Диффи-Хеллмана . Некоторые важные алгоритмы в криптографии с открытым ключом , такие как Эль-Гамаль , основывают свою безопасность на предположении о том, что задача дискретного логарифмирования (DLP) над тщательно выбранными группами не имеет эффективного решения. [1]
Пусть G — любая группа. Обозначим его групповую операцию умножением, а его единичный элемент — 1. Пусть b — любой элемент G . Для любого положительного целого числа k выражение b k обозначает произведение b на самого себя k раз: [2]
Аналогично, пусть b − k обозначает произведение b −1 на самого себя k раз. Для k = 0 k -я степень равна единице: b 0 = 1 .
Пусть a также является элементом G . Целое число k , которое решает уравнение b k = a , называется дискретным логарифмом (или просто логарифмом в данном контексте) от a по основанию b . Пишут k = log b a .
Степени числа 10 равны
Для любого числа a в этом списке можно вычислить log 10 a . Например, log 10 10000 = 4 и log 10 0,001 = −3. Это примеры проблемы дискретного логарифма.
Другие логарифмы по основанию 10 в действительных числах не являются примерами проблемы дискретного логарифма, поскольку они включают нецелые показатели степени. Например, уравнение log 10 53 = 1,724276… означает, что 10 1,724276… = 53. Хотя целочисленные показатели степени могут быть определены в любой группе с использованием произведений и обратных величин, произвольные действительные показатели степени, такие как 1,724276…, требуют других понятий, таких как экспоненциальная функция . функция .
С точки зрения теории групп , степени 10 образуют циклическую группу G при умножении, а 10 является генератором этой группы. Дискретный логарифм log 10 a определен для любого a в G .
Аналогичный пример справедлив для любого ненулевого действительного числа b . Степени образуют мультипликативную подгруппу G = {…, b −3 , b −2 , b −1 , 1, b 1 , b 2 , b 3 , …} ненулевых действительных чисел. Для любого элемента a из G можно вычислить log b a .
Одной из простейших настроек дискретных логарифмов является группа Z p × . Это группа умножения по модулю простого числа p . Его элементы представляют собой ненулевые классы конгруэнтности по модулю p , а групповое произведение двух элементов может быть получено обычным целочисленным умножением элементов с последующим сокращением по модулю p .
K - я степень одного из чисел в этой группе может быть вычислена путем нахождения его k -й степени как целого числа, а затем нахождения остатка после деления на p . Когда задействованные числа велики, более эффективно многократно уменьшать модуль p во время вычислений. Независимо от конкретного используемого алгоритма, эта операция называется модульным возведением в степень . Например, рассмотрим Z 17 × . Чтобы вычислить 3 4 в этой группе, вычислите 3 4 = 81, а затем разделите 81 на 17, получив в остатке 13. Таким образом, 3 4 = 13 в группе Z 17 × .
Дискретный логарифм — это просто обратная операция. Например, рассмотрим уравнение 3 k ≡ 13 (mod 17). В приведенном выше примере одно решение — k = 4, но это не единственное решение. Поскольку 3 16 ≡ 1 (mod 17) — как следует из малой теоремы Ферма — отсюда также следует, что если n целое число, то 3 4+16 n ≡ 3 4 × (3 16 ) n ≡ 13 × 1 n ≡ 13 (mod 17). Следовательно, уравнение имеет бесконечно много решений вида 4 + 16 n . Более того, поскольку 16 — это наименьшее целое положительное число m, удовлетворяющее условию 3 m ≡ 1 (по модулю 17), это единственные решения. Эквивалентно, множество всех возможных решений может быть выражено ограничением k ≡ 4 (mod 16).
В частном случае, когда b является единичным элементом 1 группы G , дискретный логарифм log b a не определен для a , отличного от 1, и каждое целое число k является дискретным логарифмом для a = 1.
Степени подчиняются обычному алгебраическому тождеству b k + l = b k b l . [2] Другими словами, функция
определенный как f ( k ) = b k , является групповым гомоморфизмом целых чисел Z при добавлении в подгруппу H группы G , порожденную b . Для всех a в H существует log b a . И наоборот , log b a не существует для a , не входящего в H.
Если H бесконечно , то log b a также уникален, а дискретный логарифм представляет собой групповой изоморфизм
С другой стороны, если H конечна порядка n , то log b a уникален только с точностью до сравнения по модулю n , а дискретный логарифм представляет собой групповой изоморфизм
где Z n обозначает аддитивную группу целых чисел по модулю n .
Знакомая формула замены основания для обыкновенных логарифмов остается в силе: если c — еще один генератор H , то
Можно ли вычислить дискретный логарифм за полиномиальное время на классическом компьютере?
Задача дискретного логарифмирования считается вычислительно неразрешимой. То есть в целом не известен эффективный классический алгоритм вычисления дискретных логарифмов.
Общий алгоритм вычисления log b a в конечных группах G заключается в возведении b во все большую и большую степень k до тех пор, пока не будет найдено искомое a . Этот алгоритм иногда называют пробным умножением . Для этого требуется время работы , линейное по размеру группы G и, следовательно, экспоненциальное по количеству цифр в размере группы. Следовательно, это алгоритм с экспоненциальным временем, практичный только для небольших групп G .
Существуют более сложные алгоритмы, обычно основанные на аналогичных алгоритмах факторизации целых чисел . Эти алгоритмы работают быстрее, чем наивный алгоритм, некоторые из них пропорциональны квадратному корню из размера группы и, таким образом, экспоненциально увеличивают вдвое количество цифр в размере группы. Однако ни один из них не работает за полиномиальное время (по количеству цифр в размере группы).
Питеру Шору принадлежит эффективный квантовый алгоритм . [3]
Эффективные классические алгоритмы существуют и в некоторых частных случаях. Например, в группе сложенных целых чисел по модулю p степень bk становится произведением 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]
