Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
В данном случае решением уравнения является

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

История[править | править вики-текст]

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

Введение[править | править вики-текст]

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

Теория[править | править вики-текст]

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

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

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

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

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

Теорема[править | править вики-текст]

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

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

Случай суперсингулярной эллиптической кривой[править | править вики-текст]

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

Общий случай[править | править вики-текст]

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

Теорема[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  1. 1 2 Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 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. 1 2 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.
  6. 1 2 3 4 5 Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. — Т. 11, вып. 3. — С. 24–28.
  7. Silverman J. H. The Arithmetic of Elliptic Curves.. — Springer, Berlin, 1986. — 522 с.

Литература[править | править вики-текст]

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

См. также[править | править вики-текст]