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

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

T+T=S

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

S=nT

является

n=2

История

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

Введение

Данный метод основан на сведении дискретного логарифма на эллиптической кривой к дискретному логарифму в конечном поле с некоторым расширением поля, на котором была задана эллиптическая кривая. Это значительно облегчает задачу, так как на данный момент существуют достаточно быстрые субэкспоненциальные алгоритмы решения дискретного логарифма, имеющие сложность $O\left(\exp \left(c\left(\ln p\right)^{k}\left(\ln \ln p\right)^{k-1}\right)\right)$ , или $\rho$ -алгоритм Полларда со сложностью $O({\sqrt {\pi p/2}})$ , разработанные для конечных полей[5].

Теория

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

y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}

Предположим, что коэффициенты $a_{i}\in F_{q}$ таковы, что кривая не имеет особенностей. Точки кривой $E$ вместе с бесконечноудаленной точкой $P_{\infty }$ , которая является нулевым элементом, образуют коммутативную группу, записывающуюся аддитивно, то есть для $\forall A,B\in E(F_{q}),A+B=B+A=C\in E(F_{q})$ . Также известно, что если $F_{q}$ — конечное поле, то порядок такой группы $N_{q}$ по теореме Хассе будет удовлетворять уравнению $|N_{q}-q-1|\leq 2{\sqrt {q}}$ .

Пусть $E(F_{q'})$ — подгруппа точек $E$ , определённых над $F_{q'}\supseteq F_{q}$ . Следовательно, $E(F_{q'})$ — конечная коммутативная группа. Возьмем точку $P\in E(F_{q})$ , порождающую циклическую группу порядка $m$ . То есть $|\langle P\rangle |=m$ [1].

Задача вычисления дискретных логарифмов в $\langle P\rangle$ заключается в следующем. Для данной точки $Q\in \langle P\rangle$ найти $n{\pmod {m}}$ такое, что $nP=Q$ .

Задача вычисления дискретных логарифмов в конечном поле $F_{q}$ заключается в следующем. Пусть $\alpha$ — примитивный элемент поля $F_{q}$ . Для данного ненулевого $\beta$ найти $n{\pmod {(q-1)}}$ такое, что $\alpha ^{n}=\beta$ [6].

Пусть НОК $(m,q)=1$ и расширение поля $F_{q'}\supseteq F_{q}$ такое, что $E(F_{q'})$ содержит подгруппу кручения $E[m]$ , изоморфную $\mathbb {Z} /m\times \mathbb {Z} /m$ , то есть $E[m]=\{P,T\in E(F_{q'}):mP=0,mT=0\}$ . Известно, что такое расширение существует[7]. Из этого следует, что $q'=q^{k}$ для некоторого $k\geqslant 1$ . В этом случае будет выполняться следующая теорема, позволяющая перейти к дискретному логарифму в расширенном конечном поле[6]:

Теорема

Пусть задана точка $T\in E(F_{q'})$ такая, что $\langle P,T\rangle =E[m]$ . Тогда сложность вычисления дискретных логарифмов в группе $\langle P\rangle$ не больше сложности вычисления дискретных логарифмов в $F_{q'}$ .

Чтобы воспользоваться данной теоремой, необходимо знать степень $k$ расширения поля $F_{q'}$ над $F_{q}$ и точку $T$ , для которой $\langle P,T\rangle =E[m]$ [6].

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

Для суперсингулярной кривой $E$ , $k$ и $T$ легко находятся, при этом $k\leq 6$ . Это было установлено Альфредом Менезесом, Окамото Тацуаки и Скоттом Ванстоуном в 1993 году. В своей статье они описали вероятностный алгоритм вычисления вспомогательной точки $T$ , среднее время работы которого ограничено полиномом от $\log {q'}$ [4].

Общий случай

Пусть $G$ — максимальная подгруппа $E(F_{q'})$ , порядок элементов которой является произведением простых множителей $m$ . Таким образом, $E[m]\subseteq G$ и $G=\mathbb {Z} /m_{1}\times \mathbb {Z} /m_{2}$ , где $m$ делит $m_{1}$ и $m_{2}$ . При этом $m_{1}\neq m_{2}$ (в случае $m_{1}=m_{2}$ , под нахождение точки $T$ можно адаптировать метод для суперсингулярных кривых[6]). Пусть $l$ — минимальное натуральное число, для которого выполняется $q^{l}\equiv 1{\pmod {m}}$ .

Теорема

Пусть НОК $(m,q-1)=1$ . Тогда $k=l$ и если известно разложение $m$ на простые множители, то имеется вероятностный алгоритм вычисления точки $T\in E(F_{q'})$ , для которой $\langle P,T\rangle =E[m]$ . Среднее время работы алгоритма равно $O(log^{c}{q'})$ операций в поле $F_{q'}$ для некоторой постоянной $c$ и $m\rightarrow \infty$ .

В случаях, когда НОК $(m,q-1)\neq 1$ , алгоритм работает слишком медленно, либо не работает вовсе[6].

См. также

Примечания

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

Литература

Теория

Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 1996. — Т. 8, вып. 1. — С. 65–71.
- Дополнение: Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. — Т. 11, вып. 3. — С. 24–28.
Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA). — Certicom Research, Canada. Архивировано 4 марта 2016 года.

История

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An Introduction to Mathematical Cryptography. — Springer. — 530 с.

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

[autogenerated1-1] Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 1996. — Т. 8, вып. 1. — С. 65–71.

[autogenerated2-2] ЭП ГОСТ Р 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf

[autogenerated3-3] Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An Introduction to Mathematical Cryptography. — Springer. — 530 с.

[autogenerated6-4] Menezes A., Okamoto T., Vanstone S.,. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE. — Trans. Inform. Theory, 1993. — С. 1639—1646.

[autogenerated4-5] Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA). — Certicom Research, Canada. Архивировано 4 марта 2016 года.

[autogenerated7-6] Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. — Т. 11, вып. 3. — С. 24–28.

[autogenerated5-7] Silverman J. H. The Arithmetic of Elliptic Curves.. — Springer, Berlin, 1986. — 522 с.