Дискретный логарифм
В математике для данных действительных чисел a и b логарифм что log b a — это число x такое, b Икс = а . Аналогично, в любой группе G степени b к может быть определен для всех целых чисел k , а дискретный логарифм log b a представляет собой целое число k такое, что b к = а . В теории чисел более часто используемый термин — индекс : мы можем написать x = ind r a (mod m ) (читай «индекс a по основанию r по модулю m ») для r Икс ≡ a (mod m ), если r — примитивный корень из m и НОД ( a , m ) = 1.
Дискретные логарифмы можно быстро вычислить в некоторых особых случаях, однако в целом не известно эффективного метода их вычисления. В криптографии вычислительная сложность задачи дискретного логарифмирования и ее применения была впервые предложена в задаче Диффи-Хеллмана . Некоторые важные алгоритмы в криптографии с открытым ключом , такие как Эль-Гамаль , основывают свою безопасность на предположении о том, что задача дискретного логарифмирования (DLP) над тщательно выбранными группами не имеет эффективного решения. [1]
Определение [ править ]
Пусть G — любая группа. Обозначим его групповую операцию умножением, а его единичный элемент — 1. Пусть b — любой элемент G . Для любого положительного целого числа k выражение b к обозначает произведение b на самого себя k раз: [2]
Аналогично, пусть b - к обозначим произведение b −1 сам с собой k раз. При k = 0 k -я степень равна единице: b 0 = 1 .
Пусть a также является элементом G . Целое число k , которое решает уравнение b к = a называется дискретным логарифмом (или просто логарифмом в данном контексте) a по основанию b . Пишут k = log b a .
Примеры [ править ]
Степени 10 [ править ]
Степени числа 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 , б −2 , б −1 , 1, б 1 , б 2 , б 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 к ≡ 13 (по модулю 17). В приведенном выше примере одно решение — k = 4, но это не единственное решение. С 3 16 ≡ 1 (mod 17) — как следует из малой теоремы Ферма — отсюда также следует, что если n — целое число, то 3 4+16 н ≡ 3 4 × (3 16 ) н ≡ 13 × 1 н ≡ 13 (по модулю 17). Следовательно, уравнение имеет бесконечно много решений вида 4 + 16 n . Более того, поскольку 16 — это наименьшее положительное целое число m, удовлетворяющее условию 3 м ≡ 1 (по модулю 17), это единственные решения. Эквивалентно, множество всех возможных решений может быть выражено ограничением k ≡ 4 (mod 16).
Полномочия личности [ править ]
В частном случае, когда b является единичным элементом 1 группы G , дискретный логарифм log b a не определен для a , отличного от 1, и каждое целое число k является дискретным логарифмом для a = 1.
Свойства [ править ]
Степени подчиняются обычному алгебраическому тождеству b к + л = б к б л . [2] Другими словами, функция
определяется как f ( k ) = b к является групповым гомоморфизмом целых чисел Z при на подгруппу , H группы G порожденную b . добавлении Для всех a в H существует log b a . И наоборот , log b a не существует для a не входящего в H. ,
Если H бесконечно , то log b a также уникален, а дискретный логарифм представляет собой групповой изоморфизм
С другой стороны, если H конечна порядка n n , то log b a уникален только с точностью до сравнения по модулю , а дискретный логарифм представляет собой групповой изоморфизм
где Z n обозначает аддитивную группу целых чисел по модулю n .
Знакомая формула замены основания для обыкновенных логарифмов остается в силе: если c — еще один генератор H , то
Алгоритмы [ править ]
Можно ли вычислить дискретный логарифм за полиномиальное время на классическом компьютере?
Задача дискретного логарифмирования считается вычислительно неразрешимой. То есть в целом не известен эффективный классический алгоритм вычисления дискретных логарифмов.
Общий алгоритм вычисления log b a в конечных группах G заключается в возведении b во все большую и большую степень k искомое a до тех пор, пока не будет найдено . Этот алгоритм иногда называют пробным умножением . Для этого требуется время работы , линейное по размеру группы G и, следовательно, экспоненциальное по количеству цифр в размере группы. Следовательно, это алгоритм с экспоненциальным временем, практичный только для небольших групп G .
Существуют более сложные алгоритмы, обычно основанные на аналогичных алгоритмах факторизации целых чисел . Эти алгоритмы работают быстрее, чем наивный алгоритм, некоторые из них пропорциональны квадратному корню из размера группы и, таким образом, экспоненциально увеличивают вдвое количество цифр в размере группы. Однако ни один из них не работает за полиномиальное время (по количеству цифр в размере группы).
- Бэби-шаг, гигантский шаг
- Функциональное поле сита
- Алгоритм расчета индекса
- Сито числового поля
- Алгоритм Полига – Хеллмана
- Ро-алгоритм Полларда для логарифмов
- Алгоритм кенгуру Полларда (он же лямбда-алгоритм Полларда)
эффективный квантовый алгоритм принадлежит Питеру Шору . [3]
Эффективные классические алгоритмы существуют и в некоторых частных случаях. Например, в группе сложенных целых чисел по модулю p степень b к становится произведением 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]
См. также [ править ]
Ссылки [ править ]
- ^ Менезес, AJ; ван Ооршот, ПК; Ванстон, С.А. «Глава 8.4 Шифрование с открытым ключом Эль-Гамаля» (PDF) . Справочник по прикладной криптографии . ЦРК Пресс .
- ^ Перейти обратно: а б Лам; Шпарлинский; Ван; Син (2001). Лам, Квок-Ян; Шпарлинский, Игорь; Ван, Хуасюн; Син, Чаопин (ред.). Криптография и вычислительная теория чисел . Прогресс в области информатики и прикладной логики (1-е изд.). Биркхойзер Базель . стр. 54–56. дои : 10.1007/978-3-0348-8295-8 . eISSN 2297-0584 . ISBN 978-3-7643-6510-3 . ISSN 2297-0576 .
- ^ Шор, Питер (1997). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». SIAM Journal по вычислительной технике . 26 (5): 1484–1509. arXiv : Quant-ph/9508027 . дои : 10.1137/s0097539795293172 . МР 1471990 . S2CID 2337707 .
- ^ Блейк, Ян Ф.; Гарефалакис, Тео (1 апреля 2004 г.). «О сложности дискретного логарифма и задач Диффи–Хеллмана» . Журнал сложности . Festschrift для Харальда Нидеррайтера, специальный выпуск по кодированию и криптографии. 20 (2): 148–170. дои : 10.1016/j.jco.2004.01.002 . ISSN 0885-064X .
- ^ Перейти обратно: а б с Адриан, Дэвид; Бхаргаван, Картикеян; Дурумерик, Закир; Годри, Пьеррик; Грин, Мэтью; Халдерман, Дж. Алекс; Хенингер, Надя ; Спринголл, Дрю; Томе, Эммануэль; Валента, Люк; ВандерСлот, Бенджамин; Вустроу, Эрик; Занелла-Бегелен, Сантьяго; Циммерманн, Пол (октябрь 2015 г.). «Несовершенная прямая секретность: как Диффи-Хеллман терпит неудачу на практике» (PDF) .
- ^ Харкинс, Д.; Каррел, Д. (ноябрь 1998 г.). «Интернет-обмен ключами (IKE)» . Сетевая рабочая группа . дои : 10.17487/RFC2409 . ISSN 2070-1721 .
- Розен, Кеннет Х. (2011). Элементарная теория чисел и ее применение (6-е изд.). Пирсон. п. 368. ИСБН 978-0321500311 .
- Вайсштейн, Эрик В. «Дискретный логарифм» . Математический мир . Вольфрам Веб . Проверено 1 января 2019 г.
Дальнейшее чтение [ править ]
- Ричард Крэндалл ; Карл Померанс . Глава 5, Простые числа: вычислительная перспектива , 2-е изд., Springer.
- Стинсон, Дуглас Роберт (2006). Криптография: теория и практика (3-е изд.). Лондон, Великобритания: CRC Press . ISBN 978-1-58488-508-5 .