Дискретное логарифмирование на эллиптической кривой

Дискретное логарифмирование на эллиптической кривой — решение уравнения относительно при известных и , где  — точки, принадлежащие эллиптической кривой и являющиеся зашифрованным сообщением и начальной точкой соответственно[1]. Иначе говоря — это метод взлома системы безопасности, основанной на данной эллиптической кривой (например российский стандарт ЭП ГОСТ Р 34.10-2012[2]), и нахождения секретного ключа.

В данном случае решением уравнения является

История

Эллиптическая криптография относится к разряду асимметричной, то есть шифрование происходит с помощью открытого ключа. Впервые этот алгоритм был независимо предложен Нилом Коблицем и Виктором Миллером в 1985 году[3]. Это было обосновано тем, что дискретный логарифм на эллиптической кривой оказался сложнее классического дискретного логарифма на конечном поле. До сих пор не существует быстрых алгоритмов взлома сообщения, зашифрованного с помощью эллиптической кривой, в общем случае. В основном уязвимости таких шифров связаны с рядом недочетов при подборе начальных данных[4].

Введение

Данный метод основан на сведении дискретного логарифма на эллиптической кривой к дискретному логарифму в конечном поле с некоторым расширением поля, на котором была задана эллиптическая кривая. Это значительно облегчает задачу, так как на данный момент существуют достаточно быстрые субэкспоненциальные алгоритмы решения дискретного логарифма, имеющие сложность , или -алгоритм Полларда со сложностью , разработанные для конечных полей[5].

Теория

Пусть  — эллиптическая кривая, заданная в форме Вейерштрасса, над конечным полем порядка :

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

Пусть  — подгруппа точек , определённых над . Следовательно,  — конечная коммутативная группа. Возьмем точку , порождающую циклическую группу порядка . То есть [1].

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

Задача вычисления дискретных логарифмов в конечном поле заключается в следующем. Пусть  — примитивный элемент поля . Для данного ненулевого найти такое, что [6].

Пусть НОК и расширение поля такое, что содержит подгруппу кручения , изоморфную , то есть . Известно, что такое расширение существует[7]. Из этого следует, что для некоторого . В этом случае будет выполняться следующая теорема, позволяющая перейти к дискретному логарифму в расширенном конечном поле[6]:

Теорема

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

Чтобы воспользоваться данной теоремой, необходимо знать степень расширения поля над и точку , для которой [6].

Случай суперсингулярной эллиптической кривой

Для суперсингулярной кривой , и легко находятся, при этом . Это было установлено Альфредом Менезесом, Окамото Тацуаки и Скоттом Ванстоуном в 1993 году. В своей статье они описали вероятностный алгоритм вычисления вспомогательной точки , среднее время работы которого ограничено полиномом от [4].

Общий случай

Пусть  — максимальная подгруппа , порядок элементов которой является произведением простых множителей . Таким образом, и , где делит и . При этом (в случае , под нахождение точки можно адаптировать метод для суперсингулярных кривых[6]). Пусть  — минимальное натуральное число, для которого выполняется .

Теорема

Пусть НОК. Тогда и если известно разложение на простые множители, то имеется вероятностный алгоритм вычисления точки , для которой . Среднее время работы алгоритма равно операций в поле для некоторой постоянной и .

В случаях, когда НОК, алгоритм работает слишком медленно, либо не работает вовсе[6].

См. также

Примечания

  1. Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 1996. Т. 8, вып. 1. С. 65–71.
  2. ЭП ГОСТ Р 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf
  3. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An Introduction to Mathematical Cryptography. — Springer. — 530 с.
  4. Menezes A., Okamoto T., Vanstone S.,. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE. — Trans. Inform. Theory, 1993. С. 1639—1646.
  5. Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA). — Certicom Research, Canada. Архивировано 4 марта 2016 года.
  6. Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. Т. 11, вып. 3. С. 24–28.
  7. Silverman J. H. The Arithmetic of Elliptic Curves.. — Springer, Berlin, 1986. — 522 с.

Литература

Теория
История

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.