Русская Википедия:Дискретное логарифмирование на эллиптической кривой

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Кратная точка на эллиптической кривой.jpg

<math>T+T=S</math>

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

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

История

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

Введение

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

Теория

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

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

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

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

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

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

Теорема

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

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

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

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

Общий случай

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

Теорема

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

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

См. также

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

Литература

Теория

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

История

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