Это не официальный сайт wikipedia.org 01.01.2023

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

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

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

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

ИсторияПравить

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

ВведениеПравить

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

ТеорияПравить

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


y 2 + a 1 x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6  

Предположим, что коэффициенты a i F q   таковы, что кривая не имеет особенностей. Точки кривой E   вместе с бесконечноудаленной точкой P  , которая является нулевым элементом, образуют коммутативную группу, записывающуюся аддитивно, то есть для A , B E ( F q ) , A + B = B + A = C E ( F q )  . Также известно, что если F q   — конечное поле, то порядок такой группы N q   по теореме Хассе будет удовлетворять уравнению | N q q 1 | 2 q  .

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

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

Задача вычисления дискретных логарифмов в конечном поле F q   заключается в следующем. Пусть α   — примитивный элемент поля F q  . Для данного ненулевого β   найти n ( mod ( q 1 ) )   такое, что α n = β  [6].

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

ТеоремаПравить

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

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

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

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

Общий случайПравить

Пусть G   — максимальная подгруппа E ( F q )  , порядок элементов которой является произведением простых множителей m  . Таким образом, E [ m ] G   и G = Z / m 1 × Z / m 2  , где m   делит m 1   и m 2  . При этом m 1 m 2   (в случае m 1 = m 2  , под нахождение точки T   можно адаптировать метод для суперсингулярных кривых[6]). Пусть l   — минимальное натуральное число, для которого выполняется q l 1 ( mod m )  .

ТеоремаПравить

Пусть НОК ( m , q 1 ) = 1  . Тогда k = l   и если известно разложение m   на простые множители, то имеется вероятностный алгоритм вычисления точки T E ( F q )  , для которой P , T = E [ m ]  . Среднее время работы алгоритма равно O ( l o g c q )   операций в поле F q   для некоторой постоянной c   и m  .

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

См. такжеПравить

ПримечанияПравить

  1. 1 2 Семаев И. А. О вычислении логарифмов на эллиптических кривых. — Дискрет. матем., 1996. — Т. 8, вып. 1. — С. 65–71.
  2. ЭП ГОСТ Р 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf Архивная копия от 5 марта 2016 на Wayback Machine
  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. Архивировано 4 марта 2016 года.
  6. 1 2 3 4 5 Семаев И. А. К вопросу о сведении вычисления дискретных логарифмов на эллиптической кривой к вычислению дискретных логарифмов в конечном поле. — Дискрет. матем., 1999. — Т. 11, вып. 3. — С. 24–28.
  7. Silverman J. H. The Arithmetic of Elliptic Curves.. — Springer, Berlin, 1986. — 522 с.

ЛитератураПравить

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