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

$T+T=S$

В данном случае решением уравнения $S=nT$ является $n=2$

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

История

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

Введение

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

Теория

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

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

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

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

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

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

Теорема

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

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

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

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

Общий случай

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

Теорема

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

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

См. также

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

Литература

Теория

• Шаблон:Статья
  • Дополнение: Шаблон:Статья
• Шаблон:Статья

История

• Шаблон:Книга