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

Пример 13.13

Для какого значения n группа имеет примитивные корни: 17, 20, 38 и 50 ?

Решение

a. имеет примитивные корни, потому что 17 - простое число (p t , где t равно 1 ).

b. не имеет никаких примитивных корней.

c. и 19 - простое число.

d. имеет первообразные корни, потому что , а 5 - простое число.

Если группа имеет примитивный корень, то обычно она имеет несколько таких корней. Число примитивных корней может быть вычислено как - . Например, число примитивных корней - это - . Обращаем внимание, что нужно сначала проверить, имеет ли группа какой-либо примитивный корень, прежде чем находить число корней.

Если группа G = < Z n* , x > имеет хотя бы один примитивный корень, то число примитивных корней - ( (n))

Рассмотрим три вопроса:

1. Если дан элемент a и группа , как можно определить, является ли a примитивным корнем G ? Это не такая легкая задача.

а. Мы должны найти , - эта задача по сложности подобна задаче разложения на множители числа n .

б. Мы должны найти .

2. Если дана группа , как найти все примитивные корни ? Эта задача более трудная, чем первая задача, потому что мы должны повторить вычисления по п.1.б для всей группы.

3. Если дана группа , то как выбирать примитивный корень G ? В криптографии мы должны найти, по крайней мере, один примитивный корень в группе. Однако в этом случае значение n выбирается пользователем, и пользователь знает . Пользователь пробует последовательно несколько элементов, пока не находит первый из них.

Циклическая группа . Циклические группы уже обсуждались в лекциях 5-6. Обратите внимание на то, что, если группа имеет примитивные корни, то они циклически повторяются. Каждый примитивный корень - генератор и может использоваться для создания целого набора. Другими словами, если g - примитивный корень в группе, мы можем генерировать набор Z n * как

Пример 13.14

Группа имеет два примитивных корня, потому что и . Можно найти примитивные корни - это 3 и 7 . Ниже показано, как можно создать целый набор Z 10* , использующий каждый примитивный корень.

g = 3 -> g 1 mod 10 = 3 g 2 mod 10 = 9 g 3 mod 10 = 7 g 4 mod 10 = 1 g = 7 -> g 1 mod 10 = 7 g 2 mod 10 = 9 g 3 mod 10 = 3 g 4 mod 10 = 1

Обратите внимание, что группа всегда циклическая, потому что p - простое.

Группа G = < Z n * , x > является циклической группой, если она имеет примитивные корни. Группа G = < Z p * , x > всегда является циклической.

Идея дискретного логарифма . Группа имеет несколько интересных свойств.

Решение модульного логарифма с использованием дискретных логарифмов

Теперь рассмотрим, как решаются задачи типа y = a x (mod n) , т. е. дано y , а мы должны найти x .

Табулирование дискретных логарифмов . Один из способов решения вышеупомянутой проблемы - использовать таблицу для каждого Z p* и различных оснований. Этот тип таблицы может быть предварительно рассчитан и сохранен. Например, таблица 13.4 показывает значения дискретного логарифма для Z 7* . Мы знаем, что мы имеем два примитивных корня или основания в данном множестве.

Таблица 13.4. Дискретный логарифм для G =

y	1	2	3	4	5	6
x = L 3 y	6	2	1	4	5	3
x = L 5 y	6	4	5	2	1	3

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

Пример 13.15

Найдите x в каждом из следующих случаев:

a.

b.

Мы можем легко использовать таблицу 13.4 дискретного логарифма .

Группа исследователей из EPFL и Университета Лейпцига смогла посчитать логарифм по основанию простого числа размером 768 бит . Для этого им понадобилось 200 ядер и время с февраля 2015 года. Использовали они вариант цифрового решета. Таким образом логарифмирование сравнялось с факторизацией где рекорд для обычных чисел тоже 768 бит

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

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

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

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

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

А теперь - собственно, определение логарифма:

Логарифм по основанию a от аргумента x - это степень, в которую надо возвести число a , чтобы получить число x .

Обозначение: log a x = b , где a - основание, x - аргумент, b - собственно, чему равен логарифм.

Например, 2 3 = 8 ⇒ log 2 8 = 3 (логарифм по основанию 2 от числа 8 равен трем, поскольку 2 3 = 8). С тем же успехом log 2 64 = 6 , поскольку 2 6 = 64 .

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

2 1	2 2	2 3	2 4	2 5	2 6
2	4	8	16	32	64
log 2 2 = 1	log 2 4 = 2	log 2 8 = 3	log 2 16 = 4	log 2 32 = 5	log 2 64 = 6

К сожалению, далеко не все логарифмы считаются так легко. Например, попробуйте найти log 2 5 . Числа 5 нет в таблице, но логика подсказывает, что логарифм будет лежать где-то на отрезке . Потому что 2 2 < 5 < 2 3 , а чем больше степень двойки, тем больше получится число.

Такие числа называются иррациональными: цифры после запятой можно писать до бесконечности, и они никогда не повторяются. Если логарифм получается иррациональным, его лучше так и оставить: log 2 5 , log 3 8 , log 5 100 .

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

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

С определением разобрались - осталось научиться считать логарифмы, т.е. избавляться от знака «log». Для начала отметим, что из определения следует два важных факта:

1. Аргумент и основание всегда должны быть больше нуля. Это следует из определения степени рациональным показателем, к которому сводится определение логарифма.
2. Основание должно быть отличным от единицы, поскольку единица в любой степени все равно остается единицей. Из-за этого вопрос «в какую степень надо возвести единицу, чтобы получить двойку» лишен смысла. Нет такой степени!

Такие ограничения называются областью допустимых значений (ОДЗ). Получается, что ОДЗ логарифма выглядит так: log a x = b ⇒ x > 0 , a > 0 , a ≠ 1 .

Заметьте, что никаких ограничений на число b (значение логарифма) не накладывается. Например, логарифм вполне может быть отрицательным: log 2 0,5 = −1 , т.к. 0,5 = 2 −1 .

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

Теперь рассмотрим общую схему вычисления логарифмов. Она состоит из трех шагов:

1. Представить основание a и аргумент x в виде степени с минимально возможным основанием, большим единицы. Попутно лучше избавиться от десятичных дробей;
2. Решить относительно переменной b уравнение: x = a b ;
3. Полученное число b будет ответом.

Вот и все! Если логарифм окажется иррациональным, это будет видно уже на первом шаге. Требование, чтобы основание было больше единицы, весьма актуально: это снижает вероятность ошибки и значительно упрощает выкладки. Аналогично с десятичными дробями: если сразу перевести их в обычные, ошибок будет в разы меньше.

Посмотрим, как работает эта схема на конкретных примерах:

Задача. Вычислите логарифм: log 5 25

1. Представим основание и аргумент как степень пятерки: 5 = 5 1 ; 25 = 5 2 ;

Составим и решим уравнение:
log 5 25 = b ⇒ (5 1) b = 5 2 ⇒ 5 b = 5 2 ⇒ b = 2 ;

2. Получили ответ: 2.

Задача. Вычислите логарифм:

Задача. Вычислите логарифм: log 4 64

1. Представим основание и аргумент как степень двойки: 4 = 2 2 ; 64 = 2 6 ;
2. Составим и решим уравнение:
   log 4 64 = b ⇒ (2 2) b = 2 6 ⇒ 2 2b = 2 6 ⇒ 2b = 6 ⇒ b = 3 ;
3. Получили ответ: 3.

Задача. Вычислите логарифм: log 16 1

1. Представим основание и аргумент как степень двойки: 16 = 2 4 ; 1 = 2 0 ;
2. Составим и решим уравнение:
   log 16 1 = b ⇒ (2 4) b = 2 0 ⇒ 2 4b = 2 0 ⇒ 4b = 0 ⇒ b = 0 ;
3. Получили ответ: 0.

Задача. Вычислите логарифм: log 7 14

1. Представим основание и аргумент как степень семерки: 7 = 7 1 ; 14 в виде степени семерки не представляется, поскольку 7 1 < 14 < 7 2 ;
2. Из предыдущего пункта следует, что логарифм не считается;
3. Ответ - без изменений: log 7 14.

Небольшое замечание к последнему примеру. Как убедиться, что число не является точной степенью другого числа? Очень просто - достаточно разложить его на простые множители. Если в разложении есть хотя бы два различных множителя, число не является точной степенью.

Задача. Выясните, являются ли точными степенями числа: 8; 48; 81; 35; 14 .

8 = 2 · 2 · 2 = 2 3 - точная степень, т.к. множитель всего один;
48 = 6 · 8 = 3 · 2 · 2 · 2 · 2 = 3 · 2 4 - не является точной степенью, поскольку есть два множителя: 3 и 2;
81 = 9 · 9 = 3 · 3 · 3 · 3 = 3 4 - точная степень;
35 = 7 · 5 - снова не является точной степенью;
14 = 7 · 2 - опять не точная степень;

Заметим также, что сами простые числа всегда являются точными степенями самих себя.

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

Некоторые логарифмы встречаются настолько часто, что имеют специальное название и обозначение.

Десятичный логарифм от аргумента x - это логарифм по основанию 10, т.е. степень, в которую надо возвести число 10, чтобы получить число x . Обозначение: lg x .

Например, lg 10 = 1; lg 100 = 2; lg 1000 = 3 - и т.д.

Отныне, когда в учебнике встречается фраза типа «Найдите lg 0,01», знайте: это не опечатка. Это десятичный логарифм. Впрочем, если вам непривычно такое обозначение, его всегда можно переписать:
lg x = log 10 x

Все, что верно для обычных логарифмов, верно и для десятичных.

Натуральный логарифм

Существует еще один логарифм, который имеет собственное обозначение. В некотором смысле, он даже более важен, чем десятичный. Речь идет о натуральном логарифме.

Натуральный логарифм от аргумента x - это логарифм по основанию e , т.е. степень, в которую надо возвести число e , чтобы получить число x . Обозначение: ln x .

Многие спросят: что еще за число e ? Это иррациональное число, его точное значение найти и записать невозможно. Приведу лишь первые его цифры:
e = 2,718281828459...

Не будем углубляться, что это за число и зачем нужно. Просто помните, что e - основание натурального логарифма:
ln x = log e x

Таким образом, ln e = 1 ; ln e 2 = 2 ; ln e 16 = 16 - и т.д. С другой стороны, ln 2 - иррациональное число. Вообще, натуральный логарифм любого рационального числа иррационален. Кроме, разумеется, единицы: ln 1 = 0.

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

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

Дискретное логарифмирование (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).

3 1 ≡ 3	3 2 ≡ 9	3 3 ≡ 10	3 4 ≡ 13	3 5 ≡ 5	3 6 ≡ 15	3 7 ≡ 11	3 8 ≡ 16
3 9 ≡ 14	3 10 ≡ 8	3 11 ≡ 7	3 12 ≡ 4	3 13 ≡ 12	3 14 ≡ 2	3 15 ≡ 6	3 16 ≡ 1

Теперь легко увидеть, что решением рассматриваемого сравнения является 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; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия

План:

Введение

• 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. Вычислительная сложность и приложения в криптографии

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

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