Математические основы защиты информации. Ишмухаметов Ш.Т - 62 стр.

Методы, основанные на задаче дискретного логарифмирования           63

4. Криптографические методы, основанные на
    задаче       дискретного          логарифмирования               в
    конечном поле
     Напомним, что в конечном поле Fq , q = pk , для произвольных
элементов a, b ∈ Fq дискретным логарифмом числа b по основанию a
называется натуральное число k такое, что

                            ak = b в поле Fq

Если степень расширения поля k = 1 т.е. q = p является простым числом,
то последнее условие можно переписать в виде

                             ak mod p = b

       Задача вычисления дискретного логарифма при заданных значениях
p, a, b называется задачей дискретного логарифмирования в конечном поле
ДЛП.
       Существует тривиальный переборный алгоритм вычисления степени
k путем сравнения элементов ax mod p и b для x = 0, 1, 2, . . . до их
совпадения. Этот алгоритм работает очень медленно и имеет сложность
экспоненциальную сложность относительно длины L размерности q .
       В первой главе был описан ρ-алгоритм Полларда, основанный на
парадоксе дня рождения, имеющий сложность O(2L/2 ). Самым быстрым
на сегодняшний день является алгоритм решета числового поля, имеющий
субэкспоненциальную сложность.
       Принято считать, что длина размерности поля, при которой
дискретный логарифм не вычислим, равна 1024 бита или более, что
соответствует длине числа n = p · q в методе RSA. Поэтому методы,
использующие трудноразрешимость задачи ДЛП, имеют ключи той же
длины, что и метод RSA, основанный на трудноразрешимость задачи
факторизации.