План:

Введение

• 1 Постановка задачи
• 2 Пример
• 3 Алгоритмы решения
  • 3.1 В произвольной мультипликативной группе
  • 3.2 В кольце вычетов по простому модулю
    • 3.2.1 Алгоритмы с экспоненциальной сложностью
    • 3.2.2 Субэкспоненциальные алгоритмы
  • 3.3 В произвольном конечном поле
  • 3.4 В группе точек на эллиптической кривой
• 4 Вычислительная сложность и приложения в криптографии

Введение

Дискретное логарифмирование (DLOG) – задача обращения функции g x в некоторой конечной мультипликативной группе G .

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

Для заданных g и a решение x уравнения g x = a называется дискретным логарифмом элемента a по основанию g . В случае, когда G является мультипликативной группой кольца вычетов по модулю m , решение называют также индексом числа a по основанию g . Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m .

1. Постановка задачи

Пусть в некоторой конечной мультипликативной абелевой группе G задано уравнение

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x , удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху - алгоритм полного перебора нашел бы решение за число шагов не выше порядка данной группы.

Чаще всего рассматривается случай, когда , то есть группа является циклической, порождённой элементом g . В этом случае уравнение всегда имеет решение. В случае же произвольной группы вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

2. Пример

Проще всего рассмотреть задачу дискретного логарифмирования в кольце вычетов по модулю простого числа.

Пусть задано сравнение

Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 3 3 ≡27 - остаток от деления на 17 равен 10).

Теперь легко увидеть, что решением рассматриваемого сравнения является x=4 , поскольку 3 4 ≡13.

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

3. Алгоритмы решения

3.1. В произвольной мультипликативной группе

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья J. Buchmann, M. J. Jacobson и E. Teske. В алгоритме используется таблица, состоящая из пар элементов и выполняется умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.

3.2. В кольце вычетов по простому модулю

Рассмотрим уравнение

где p - простое, b не делится на p . Если a является образующим элементом группы , то уравнение (2) имеет решение при любых b . Такие числа a называются ещё первообразными корнями, и их количество равно φ(p − 1) , где φ - функция Эйлера. Решение уравнения (2) можно находить по формуле:

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

Следующий алгоритм имеет сложность

Алгоритм

Конец алгоритма

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

3.2.1. Алгоритмы с экспоненциальной сложностью

3.2.2. Субэкспоненциальные алгоритмы

Данные алгоритмы имеют сложность арифметических операций, где и - некоторые константы. Эффективность алгоритма во многом зависит от близости c к 1 и d - к 0.

Наилучшими параметрами в оценке сложности на данный момент является , .

Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут , . За счёт того, что константа c достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с .

3.3. В произвольном конечном поле

Задача рассматривается в поле GF(q) , где q = p n , p - простое.

3.4. В группе точек на эллиптической кривой

Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда m P - это . Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа m , что

для заданных точек P и A .

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии, Менезес (Alfred J. Menezes), Окамото (Tatsuaki Okamoto) и Венстон (Scott A. Vanstone) предложили алгоритм, использующий спаривание Вейля. Для эллиптической кривой, определённой над полем G F (q ) , данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле G F (q k ) . Однако, данное сведение полезно, только если степень k мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.

4. Вычислительная сложность и приложения в криптографии

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Идея, лежащая в основе подобных систем, опирается на высокую вычислительную сложность обращения некоторых числовых функций. В данном случае, операция дискретного логарифмирования является обратной к показательной функции. Последняя вычисляется достаточно просто, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.

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

Дискретное логарифмирование (DLOG) - задача обращения функции g x {\displaystyle g^{x}} в некоторой конечной мультипликативной группе G {\displaystyle G} .

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

Для заданных g и a решение x уравнения называется дискретным логарифмом элемента a по основанию g . В случае, когда G является мультипликативной группой кольца вычетов по модулю m , решение называют также индексом числа a по основанию g . Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m .

Энциклопедичный YouTube

1 / 5

✪ Задача вычисления дискретного логарифма

✪ Дискретное логарифмирование (часть 11)| Криптография | Программирование

✪ Протокол Ди́ффи - Хе́ллмана (часть 12) | Криптография | Программирование

✪ Переносная шифровальная машина «Эни́гма» (часть 6) | Криптография | Программирование

✪ Шифр Вернама (часть 4) | Криптография | Программирование

Субтитры

Нам нужна числовая процедура, которая легко выполняется в одном направлении и гораздо труднее в обратном. Это приводит нас к модульной арифметике, также известной как "арифметика часов" (или "остатков"). Например, для нахождения 46 по модулю 12 можно взять веревку длиной 46 единиц и свернуть ее вокруг часов, которые называют модулем. То место, где веревка заканчивается, и есть решение. То есть 46 по модулю 12 эквивалентно 10-ти. Все просто. Теперь для выполнения этого возьмем простой модуль. 17, к примеру. Затем найдем первообразный корень 17-ти, в этом случае -- три. Он имеет очень важное свойство при возведении в различные степени -- значения равномерно распределяются вокруг часов. 3 называют порождающим элементом или генератором. Если возвести 3 в любую степень x, то результат равновероятно может оказаться любым числом от 1 до 16. То есть обратная процедура довольно сложна. Скажем, какая степень 3 даст в результате 12? Это и есть задача вычисления дискретного логарифма. И теперь у нас есть односторонняя функция. Простая для прямого и сложная для обратного выполнения. Для заданного числа 12 нам приходится прибегнуть к перебору многих ошибочных вариантов, чтобы найти нужный показатель степени. Так насколько это сложно? Ну, с небольшими значениями это просто, но если использован простой модуль длиной в сотни знаков, задача становится практически неразрешимой. Даже если есть доступ ко всем вычислительным мощностям Земли, перебор всех вариантов может занять тысячи лет. Таким образом, сила односторонней функции основана на времени, необходимом для обратного преобразования.

Постановка задачи

Пусть в некоторой конечной мультипликативной абелевой группе G {\displaystyle G} задано уравнение

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x {\displaystyle x} , удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху - алгоритм полного перебора нашел бы решение за число шагов не выше порядка данной группы.

Чаще всего рассматривается случай, когда G = ⟨ g ⟩ {\displaystyle G=\langle g\rangle } , то есть группа является циклической , порождённой элементом g {\displaystyle g} . В этом случае уравнение всегда имеет решение. В случае же произвольной группы вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

Пример

Рассмотрим задачу дискретного логарифмирования в кольце вычетов по модулю простого числа. Пусть задано сравнение

Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут c ≈ 1 , 00475 {\displaystyle c\approx 1,00475} , d = 2 5 {\displaystyle d={\frac {2}{5}}} . За счёт того, что константа c {\displaystyle c} достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с d = 1 3 {\displaystyle d={\frac {1}{3}}} .

В произвольном конечном поле

Задача рассматривается в поле GF(q) , где q = p n {\displaystyle q=p^{n}} , p {\displaystyle p} - простое.

В группе точек на эллиптической кривой

Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда m P {\displaystyle mP} - это P + … + P ⏟ m {\displaystyle \underbrace {P+\ldots +P} \limits _{m}} . Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа m {\displaystyle m} , что m P = A {\displaystyle mP=A} для заданных точек P {\displaystyle P} и A . {\displaystyle A.}

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии, Менезес (Alfred J. Menezes), Окамото (Tatsuaki Okamoto) и Венстон (Scott A. Vanstone) предложили алгоритм, использующий спаривание Вейля . Для эллиптической кривой, определённой над полем G F (q) {\displaystyle GF(q)} , данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле G F (q k) {\displaystyle GF(q^{k})} . Однако, данное сведение полезно, только если степень k {\displaystyle k} мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.

Вычислительная сложность и приложения в криптографии

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом . Классическими криптографическими схемами на её основе являются схема выработки общего ключа Диффи-Хеллмана , схема электронной подписи Эль-Гамаля , криптосистема Мэсси-Омуры для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции. Хотя сама показательная функция вычисляется достаточно эффективно, даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов

Кстати, после завтрашнего апдейта можно будет прикручивать бесплатный TLS к dyndns хостам! Это суперкруто, все хомяки теперь будут с сертификатами.

Защищаемся от Side channel атак

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

На этом у меня всё, до новых встреч!

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

Дискретное логарифмирование (DLOG) – задача обращения функции g x в некоторой конечной мультипликативной группе G .

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

Для заданных g и a решение x уравнения g x = a называется дискретным логарифмом элемента a по основанию g . В случае, когда G является группой обратимых элементов кольца вычетов по модулю m , решение называют также индексом числа a по основанию g . Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m .

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x , удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху - алгоритм полного перебора нашел бы решение за число шагов, не выше порядка данной группы.

Чаще всего рассматривается случай, когда , то есть группа является циклической , порождённой элементом g . В этом случае уравнение всегда имеет решение. В случае же произвольной группы, вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

Пример

Проще всего рассмотреть задачу дискретного логарифмирования в кольце вычетов по модулю простого числа.

Пусть задано сравнение

Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 3 3 ≡27 - остаток от деления на 17 равен 10).

Теперь легко увидеть, что решением рассматриваемого сравнения является x=4 , поскольку 3 4 ≡13.

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

Алгоритмы решения

В произвольной мультипликативной группе

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья BuchmannJ., Jacobson M.J., Teske E. On some computational problems in finite abelian groups . В алгоритме используется таблица, состоящая из пар элементов и выполняется умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.

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

Классическими криптографическими схемами, базирующимися на сложности задачи дискретного логарифмирования, являются схема выработки общего ключа Диффи-Хеллмана , схема электронной подписи Эль-Гамаля , криптосистема Мэсси-Омуры для передачи сообщений.

Ссылки

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии . - Москва: МЦНМО , 2003. - 328 с. - ISBN 5-94057-103-4
• Коблиц Н. Курс теории чисел и криптографии . - Москва: ТВПб, 2001. - 254 с. - ISBN 5-85484-014-6
• Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // LNCS . - 1984. - Т. 209. - С. 224-316.
• Buchmann J., Jacobson M.J., Teske E. On some computational problems in finite abelian groups // Mathematics of Computation . - 1997. - Т. 66. - № 220. - С. 1663-1687.
• Статья Дискретное логарифмирование на сайте Научная сеть
• Обзор методов вычисления дискретного логарифма (на английском)
• Нечаев В.И. К вопросу о сложности детерминированного алгоритма для дискретного логарифма // Математические заметки . - 1994. - В. 2. - Т. 55. - С. 91-101.

Wikimedia Foundation . 2010 .

Смотреть что такое "Дискретный логарифм" в других словарях:

дискретный логарифм - В группе два элемента d; g таковы, что имеется целое число r, удовлетворяющее условию gr = d; r называется дискретным логарифмом d по основанию g. Тематики информационные технологии в целом EN discrete logarithm … Справочник технического переводчика

Алгоритм Полига Хеллмана (также называемый алгоритм Сильвера Полига Хеллмана) детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностью алгоритма является то,… … Википедия

- (англ. Baby step giant step; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия

130 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

Запись показателя в виде дроби корректна, поскольку один из сомножителей числителя, а именно u , делится наp , т.е. дробь является обычным целым числом.

Очевидно, r p p , j = b ju = 1 , следовательно, элементыr p , j - корни степениp

из единицы. Аналогичным образом заполним все строки таблицы R .

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

Для каждого такого элемента будет необходимо определить его позицию

таблицы R .

Алгоритм дискретного логарифмирования 131

Обозначим результат через y 1 :y 1 = y 0 b x 0 p 0 и вычислимy 1 u p 2 = b u (x − x 0 ) p 2 .

члены, кроме ux 1 p p 2 , кратныu и на значениеb u (x − x 0 ) p 2 не влияют.

132 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

операции в поле совпадают с операциями в поле вычетов по модулю 37, в частности, деление есть умножение на обратный элемент.

т.е. r 3,0 = 1 ,r 3,1 = 2 36 3 ≡ 26 (37 ) ,r 3,2 = 2 2 36 3 ≡ 2 24 ≡ 10 (37 ) . ТаблицаR имеет следующий вид.

Алгоритм дискретного логарифмирования 133

Таблица 4. Корни из единицы степеней 2 и 3

Вычислим y 0 u p = 28 18 ≡ 1 (37 ) . Позиция единицы в строке 2 таблицыR равна

0, следовательно, x 0 = 0 .

Z p r Z

134 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

x ≡ 34 mod36.

10.3.2. Логарифмирование в группе единиц кольца вычетов по модулю pr .

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

существует первообразный элемент γ , степени которого представляют все вычеты, взаимно простые с модулем. Эти вычеты образуют вмультипликативную группуU (p r ) изϕ (p r ) элементов (т.н. группу единиц).

Можно показать , что если γ p - первообразный корень в поле

GF (p ) , то одно из чиселγ = γ p + kp , гдеk { 0,1 } , удовлетворяет условию

(γ p + kp ) p − 1 ≠ 1 (mod p 2 ) и является первообразным корнем по любому модулюp α ,α > 1 . Заметим, что пары чиселa ,p , для которых выполняется соотношениеa p − 1 = 1mod p 2 , встречаются редко. Поэтому будем считать, что

γ = γp .

Таким образом, любой из ϕ (p r ) = p r − 1 (p − 1 ) вычетовb U (p r ) можно

представить в виде b = γ x mod p r .

Алгоритм дискретного логарифмирования в группе единиц… 135

Соответственно, задача дискретного логарифмирования в группе единиц кольца Z p r Z состоит в определении вычетаx поmod ϕ (p r ) , исходя изb и

γ .

К сожалению, использование модуля p r не дает преимуществ, поскольку

при наличии эффективного алгоритма логарифмирования в простом поле

GF (p ) логарифмирование в группе единиц кольца вычетов по модулюp r ,r > 1 , практически всегда можно осуществить, воспользовавшись свойствами так называемого обобщенного отношения ФермаL m (a ) .

Областью определения отображения L m (a ) является группаU (m )

вычетов по модулю m , взаимно простых с модулем. По теореме Эйлера,

существует λ :a ϕ (m ) − 1 = λ m . ЗначениеL m (a ) определяется как вычет числаλ по модулюm :L m (a ) = a ϕ (m m ) − 1 (mod m ) .

Легко убедиться, что отношение Ферма обладает следующими замечательными свойствами.

Lm (ab) = Lm (a) + Lm (b)(mod m) ,

Lm (a+ mc) = Lm (a) + ϕ (m) ca- 1 (mod m) ,

где a, b U(m) , c ZmZ.

γ ϕ (m ) = 1(modp 2 r − − 2 ≤ r − 1 , т.е.

r ≤ 1 , что противоречит

Если L

(γ )= 0 (mod m ), то

(γ ) = 0( modp r − 1 ) и r ≤ 1 .

Аналогично, при L

(γ ) = pt ( modp r − 1 ) ,

получаем

γ ϕ (m ) = 1( modp r + 1 ) ,

что невозможно, т.к. ϕ (p r + 1 ) > ϕ (m ) .

Таким образом, элемент L m (γ )

p и, следовательно,

обратим по модулю p r − 1 .

Рассмотрим задачу логарифмирования

в группе единиц кольца

Z mZ ,

эффективный алгоритм

логарифмирования в кольце

известен.

Из соотношения b = γ x mod p r

b = γ x mod p,

известно значение x по модулю

p − 1 . Если мы найдемx (mod p r − 1 ) , то

значение

по модулю ϕ (m ) = p r − 1 (p − 1 )

можно вычислить по китайской

теореме об остатках.

Очевидно,

что значение x (mod p r − 1 )

легко определить

из сравнения

L ( b) = xL(γ ) (mod pr − 1 ) .

необходимо

вычислять

значения

h = Lm ( a) (mod pr − 1 ) .