Перспективы развития и использования асимметричных алгоритмов в криптографии (стр. 2 из 4)

Теоретико-числовые проблемы

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

.
Следует отметить, что многие из асимптотических оценок носят эвристический характер, часть из которых доказана в предположении истинности гипотезы (расширенной) Римана. Ряд исследователей проводят работы по строгому доказательству этих эвристических оценок.
По-прежнему актуальной остается задача получения не асимптотических, а точных оценок трудоемкости для ряда разработанных алгоритмов.

1. Задача вычисления дискретного логарифма в мультипликативной группе конечного поля

Практически сразу после опубликования работы У. Диффи и М. Хеллмана Дж. Поллард публикует вероятностные алгоритмы решения задачи дискретного логарифмирования, имеющие корневую оценку сложности и не требующие большого объема памяти [18]. Этот метод называют r-методом Полларда (вариация метода - l-метод Полларда, общая идея известна также под названием "baby step, giant step").
В дальнейшем основные идеи построения эффективных алгоритмов для решения задачи дискретного логарифмирования были связаны с, так называемым, методом решета. Долгое время асимптотически наиболее эффективным (асимптотическая оценка сложности -

, оставался метод Д. Копперсмита, А. Одлыжко, Р. Шрёппеля [19]. Метод был реализован и применен для логарифмирования в простых полях при p длиной до 67 десятичных знаков.
Последним существенным достижением в этой области является метод решета числового поля Д. Гордона [20]. Асимптотически метод более эффективен, чем все предыдущие: оценка его трудоемкости . Однако его практическая реализация сложнее: пока имеется сообщение, что этим методом удалось решить задачу дискретного логарифмирования в простом поле при p длиной 40 десятичных знаков. Для этого специалистам немецкого университета Universitat des Saarlandes в Саарбрюккене потребовались 21 час работы рабочей станции Sparc и 40 минут работы суперкомпьютера Cray [21]. По последним данным 1997 года немецким исследователям удалось реализовать процедуру логарифмирования для чисел длиной 85 десятичных знаков.
За каждым из названных методов стоит целый спектр их модификаций и вариантов. Из отечественных исследователей, работающих в этом направлении необходимо назвать О. Н. Василенко и И. А. Семаева. В тезисах выступлений последнего на конференциях по теории чисел и ее приложениям (Тула, Воронеж) содержатся весьма интересные новые идеи в развитие метода решета.
Исследователи постоянно предпринимают попытки поиска принципиально иных подходов (отличных от идей метода решета) к задаче дискретного логарифмирования. Из опубликованного здесь следует упомянуть работы, связанные с попыткой использования частных Ферма [22], [23], однако, пока успешное логарифмирование этим методом требует большего объема информации, чем "классическая" постановка задачи.
Также следует упомянуть о том, что с середины 1997 года в научной среде циркулируют слухи о том, что российскому ученому С. А. Степанову удалось построить полиномиальный алгоритм дискретного логарифмирования. Однако, вплоть до сегодняшнего дня убедительные подтверждения этому факту отсутствуют, впрочем, как и убедительные опровержения.

2. Задача разложения целых чисел на множители

По сравнению с задачей дискретного логарифмирования задача факторизации чисел или разложения их на множители имеет более длительную историю, ведомую обычно с античных времен от Эратосфена (предположительно 284 - 202 гг. до н.э.), а в дальнейшем связанную с именами таких великих математиков, как Фибоначчи (предположительно 1180-1250 гг.), Ферма (1601-1665 гг.), Эйлер (1707-1783 гг.), Лежандр (1752-1833 гг.), Гаусс (1777-1855 гг.). В большинстве случаев удается разложить число на множители с помощью пробных делений на первые (маленькие) простые числа. Задача становится содержательной, когда требуется разложить число, равное произведению двух больших простых чисел (например, число Блюма). В 70-х годах был предложен (p-1)-метод Полларда [24], эффективный для случая, когда p-1 раскладывается на маленькие простые множители, где p - один из делителей факторизуемого числа. Вскоре, как развитие данного решения появился (p+1)-метод Полларда. Следующим шагом в этом направлении стала идея использования псевдослучайных отображений (r-метод Полларда). Этим методом было разложено на множители 8-ое число Ферма (

- число длиной 77 десятичных знаков). Дальнейшее развитие этих идей вылилось в методы с использованием группы точек эллиптической кривой [25].
На сегодняшний день, как и для задачи дискретного логарифмирования, основные продвижения в проблеме факторизации связаны с развитием методов решета, в которых выделяют следующие этапы развития: методы линейного решета, методы квадратичного решета [26] и метод решета числового поля [27], [28]. Сегодня практически наиболее эффективным для факторизации чисел длиной до 130 десятичных знаков остается метод квадратичного решета. Его асимптотическая оценка трудоемкости - , где . Именно этим методом был решен предложенный Райвестом практический пример вскрытия системы RSA [29], для чего потребовалось разложить на множители число длиной 129 десятичных знаков.
Методы решета числового поля асимптотически более эффективны (оценка трудоемкости: ), но применимы только для чисел вида n=re-s, где r и s сравнительно малы. На практике считается, что рассматриваемые методы следует применять для чисел из интервала 10130<n<10160. Именно таким образом в 1993 году были получены рекордные разложения: 9-ое число Ферма (2512+1 - длина 155 десятичных знаков); 2523-1 - длина 159 десятичных знаков.
Как уже было сказано выше, новые идеи в развитие метода решета содержатся в работах И. А. Семаева, что позволяет надеяться на дальнейший прогресс в данной проблематике.

3. Задача построения больших простых чисел с некоторыми дополнительными условиями

Для нужд практической криптографии актуальна проблема построения быстрых алгоритмов нахождения "случайных" простых чисел заданной длины. Скорость работы алгоритмов построения больших простых чисел важна для систем, использующих схему RSA, так как ключами в них собственно и являются большие простые числа. Обычно в этих алгоритмах реализуется какая-либо модификация "решета" с последующей проверкой чисел на простоту. При этом используется тот факт, что простые числа расположены достаточно "густо": результаты о плотности распределения простых чисел среди натуральных образуют отдельное направление в теории чисел. В частности для функции p(x), равной количеству простых чисел меньших x, имеет место асимптотическое равенство: .
На сегодня известно достаточно много алгоритмов проверки чисел на простоту: как правило, ответ на этот вопрос дает уже малая теорема Ферма. Проблема заключается в доказательстве того, что проверяемое число действительно является простым. Несмотря на то, что большинство из таких алгоритмов имеет субэкспоненциальную оценку сложности, на практике они показывают вполне приемлемую скорость работы. Из отечественных ученых существенный вклад в эту проблематику внес Ю. В. Нестеренко [22].
Существуют вероятностные алгоритмы, имеющие полиномиальные оценки сложности [30]: подробные обзоры публикаций по этой теме подготовлены О. Н. Василенко.
Важной особенностью известных методов дискретного логарифмирования является существенная зависимость их трудоемкости от мощности простого поля, в котором решается задача. Отсюда возникает необходимость разработки как алгоритма проверки простого числа на "слабость", так и алгоритма, позволяющего гарантированно избегать построения "слабых" чисел. Более подробно эти вопросы рассмотрены в [31].

4. Задача вычисления дискретного логарифма в группе точек эллиптической кривой над конечным полем

Помимо методов, применимых для логарифмирования в произвольной конечной группе, здесь известны работы И. А. Семаева [32], в одной из которых рассматривается метод, идейно близкий методам логарифмирования в конечном поле Адлемана Л. [33]. В другой работе для эллиптических кривых специального вида (накладываются некоторые условия на модуль арифметики и на мощность группы точек) И. А. Семаев указал способ сведения с полиномиальной сложностью задачи логарифмирования в группе точек эллиптической кривой к задаче логарифмирования в некотором расширении простого поля. При этом используется, так называемое, спаривания Вейля, после чего можно применять известные субэкспоненциальные методы. Аналогичные результаты были опубликованы и за рубежом [34].

5. Задача вычисления мощности группы точек эллиптической кривой над конечным полем

Точные формулы для мощностей групп точек эллиптической кривой известны только для достаточно узкого класса кривых. На практике актуальна задача построения систем асимметричной криптографии, где сама кривая является "долговременным" ключом. Таким образом возникает проблема построения эффективных алгоритмов вычисления мощности группы точек эллиптической кривой произвольного вида. Здесь известен вероятностный алгоритм Шенкса [35], основанный на идее типа "baby step, giant step". Метод имеет оценку сложности , где q - мощность конечного поля. Из детерминированных алгоритмов известен метод Скуфа [36], основанный на использовании эндоморфизма Фробениуса и имеющий оценку сложности , где q - мощность конечного поля. Однако для практических вычислений метод, по-видимому, мало пригоден. Хороший обзор по этому вопросу содержится в работе Х. В. Ленстры младшего [37].