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

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

Это называется обобщенной задачей дискретного логарифмирования (GDLP) и может быть сформулирована следующим образом.

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

Дана конечная циклическая группа G с операцией? и порядком р.

Рассмотрим примитивный элемент б? G и другой элемент в? G.

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

где 1? x ?n, такое, что:

в=б?б???б=б^x

Как и в случае с DLP в, искомое число х должно существовать, так как это примтивній элемент, и, таким образом, каждый элемент из группы G может быть получен путем многократного применения групповой операции на б.

Важно понимать, что есть циклические группы, в которых DLP не является сложнім. Такие группы не могут быть использованы для открытого ключа криптосистемы с DLP не одностороннем порядке.

Рассмотрим следующий пример.

Пример 2.3.

В этот раз мы рассмотрим аддитивную группу целых чисел по простому модулю.

Например, если мы выбираем простое р = 11, G = (,+) является конечной циклической группой с примитивным элементом б= 2.

Порождает группу таким образом:

Мы стараемся сейчас решить DLP для элемента в= 3, то есть мы должны вычислить число 1? x ?11 таким образом, что.

Вот как работает «атака» против DLP. Даже если операция группы адитивна, мы можем выразить отношения между б и в с помощью дискретного логарифма х в терминах умножения:

x· 2 ? 3 mod 11.

Для того чтобы решить для х, мы просто должны инвертировать примитивный элемент:

x ?2?1 3 mod 11.

Используя, например, расширенный алгоритм Евклида, мы можем вычислить.

2?1? 6 mod 11,.

из чего:

x ?2?1 3 ?7 mod 11.

Дискретный логарифм может быть верифицирован глядя на маленький столбик, предоставленный выше. Мы можем обобщить выше проделанный трюк для любой группой (,+) для произвольного n, и элементов б и в?. Следовательно, мы приходим к выводу, что обобщенное DLP является вычислительно простой над. Причина, по которой DLP может быть решена здесь заключается в том, что мы имеем математические операции, которые не являются аддитивными в группе, а именно умножение и инверсия.

После этого контрпримера мы можем указать список групп, для которых применима Задача дискретного логарифмирования:

• 1. мультипликативная группа поля или ее подгруппа. Например, классический Обмен ключами Диффи-Хеллмана использует эту группу, но также шифрование Эль-Гамаля или Алгоритм цифровой подписи (DSA).
• 2. циклическая группа, образованная эллиптической кривой. Эллиптические криптосистемы кривая приводятся в главе 3. Они стали популярны в практике на протяжении последнего десятилетия.
• 3. мультипликативная группа поля Галуа GF (2^m) или ее подгруппа. Эти группы могут быть использованы полностью аналогично мультипликативных групп простых полей и схем, обмен ключами Диффи-Хеллмана могут быть реализованы с ними. Они не так популярны на практике, потому что атаки на них несколько более мощные, чем те, против Задач дискретного логарифмирования в. Следовательно Задачи дискретного логарифмирования более GF (2^m), требуют несколько более длинной передачи данных для обеспечения того же уровня безопасности, чем те, над
• 4. Гиперэллиптические кривые или алгебраические многообразия, которые можно рассматривать как обобщение эллиптических кривых. В настоящее время они редко используются на практике, но, в частности, гиперэллиптические кривые имеют некоторые преимущества, такие как короткие длины операндов.