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

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

Задачи дискретного логарифмирования (DLP), непосредственно могут быть объяснены с помощью циклических групп.

Начнем с DLP над, где р простое.

Проблема дискретного логарифмирования (DLP) в

Для начала дадим определение.

Определение. Проблема дискретного логарифмирования

Пусть дана конечная циклическая группа порядка р-1 и примитивный элемент б ?, и другой элемент в? Zp. Проблема дискретного логарифмирования состоит в определении целого 1? x? р-1 такого, что:

б ^x?в mod p

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

x = log_б в mod p

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

Пример 2.1.

Рассмотрим дискретный логарифм в группе, в котором б = 5 является примитивным элементом. Для в= 41 проблема дискретного логарифмирования это:

Найти положительные целые х такие, что.

5^x ?41 mod 47.

Даже для таких маленьких чисел вычисление х не есть однозначным. Используем грубую атаку, то есть переберём все возможные значения для х, мы получим решение х = 15.

На практике часто бывает желательно иметь DLP в группах с простым порядком, чтобы предотвратить атаки Похлига-Хеллмана.

Так как порядок группы равен p?1, который, очевидно, не простой, часто использует DLP в подгруппах из с простым порядком, а не в самой группе. Проиллюстрируем это на примере.

Пример 2.2.

Рассмотрим группу, которая имеет порядок 46. Подгруппы в имеют порядок 23, 2 и 1. б = 2 элемент в подгруппе с Z₂₃ элементами, а так как 23 — простое, б является примитивным элементом в подгруппе.

Возможно проблема дискретного логарифма дается для в= 36 (который также в подгруппе):

Найти натуральное число х, 1 ?x ?23, например,.

2^x ?36 mod 47.

С помощью грубой атаки, мы получим решение для х = 17.