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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Дискретное логарифмирование
• Эллиптическая криптография
• Теория групп

Теория

• Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 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 с.