Дискретное логарифмирование на эллиптической кривой — решение уравнения относительно при известных и , где — точки, принадлежащие эллиптической кривой и являющиеся зашифрованным сообщением и начальной точкой соответственно. Иначе говоря — это метод взлома системы безопасности, основанной на данной эллиптической кривой (например российский стандарт ЭП ГОСТ Р 34.10-2012ЭП ГОСТ Р 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf ), и нахождения секретного ключа.
История Эллиптическая криптография относится к разряду асимметричной, то есть шифрование происходит с помощью открытого ключа. Впервые этот алгоритм был независимо предложен Нилом Коблицем и Виктором Миллером в 1985 году. Это было обосновано тем, что дискретный логарифм на эллиптической кривой оказался сложнее классического дискретного логарифма на конечном поле. До сих пор не существует быстрых алгоритмов взлома сообщения, зашифрованного с помощью эллиптической кривой, в общем случае. В основном уязвимости таких шифров связаны с рядом недочетов при подборе начальных данных.
Введение Данный метод основан на сведении дискретного логарифма на эллиптической кривой к дискретному логарифму в конечном поле с некоторым расширением поля, на котором была задана эллиптическая кривая. Это значительно облегчает задачу, так как на данный момент существуют достаточно быстрые субэкспоненциальные алгоритмы решения дискретного логарифма, имеющие сложность , или -алгоритм Полларда со сложностью , разработанные для конечных полей.
Теория Пусть — эллиптическая кривая, заданная в форме Вейерштрасса, над конечным полем порядка :
Предположим, что коэффициенты таковы, что кривая не имеет особенностей. Точки кривой вместе с бесконечноудаленной точкой , которая является нулевым элементом, образуют коммутативную группу, записывающуюся аддитивно, то есть для . Также известно, что если — конечное поле, то порядок такой группы по теореме Хассе будет удовлетворять уравнению .
Пусть — подгруппа точек , определённых над . Следовательно, — конечная коммутативная группа. Возьмем точку , порождающую циклическую группу порядка . То есть .
Задача вычисления дискретных логарифмов в заключается в следующем. Для данной точки найти такое, что .
Задача вычисления дискретных логарифмов в конечном поле заключается в следующем. Пусть — примитивный элемент поля . Для данного ненулевого найти такое, что .
Пусть НОК и расширение поля такое, что содержит подгруппу кручения , изоморфную , то есть . Известно, что такое расширение существует. Из этого следует, что для некоторого . В этом случае будет выполняться следующая теорема, позволяющая перейти к дискретному логарифму в расширенном конечном поле:
Теорема Пусть задана точка такая, что . Тогда сложность вычисления дискретных логарифмов в группе не больше сложности вычисления дискретных логарифмов в .
Чтобы воспользоваться данной теоремой, необходимо знать степень расширения поля над и точку , для которой .
Случай суперсингулярной эллиптической кривой Для суперсингулярной кривой , и легко находятся, при этом . Это было установлено Альфредом Менезесом, Окамото Тацуаки и Скоттом Ванстоуном в 1993 году. В своей статье они описали вероятностный алгоритм вычисления вспомогательной точки , среднее время работы которого ограничено полиномом от .
Общий случай Пусть — максимальная подгруппа , порядок элементов которой является произведением простых множителей . Таким образом, и , где делит и . При этом (в случае , под нахождение точки можно адаптировать метод для суперсингулярных кривых). Пусть — минимальное натуральное число, для которого выполняется .
Теорема Пусть НОК. Тогда и если известно разложение на простые множители, то имеется вероятностный алгоритм вычисления точки , для которой . Среднее время работы алгоритма равно операций в поле для некоторой постоянной и .
В случаях, когда НОК, алгоритм работает слишком медленно, либо не работает вовсе.
См. также Дискретное логарифмирование Эллиптическая криптография Теория групп
Примечания
Литература Теория
Дополнение:
История
Категория:Шифры Категория:Криптография Категория:Логарифмы