Глава 2 Криптосистемы на эллиптических кривых

§ 1. Кодирование и дискретное логарифмирование

Большинство продуктов и стандартов, в которых для шифрования и проверки подлинности применяются методы криптографии с открытым ключом, базируется на алгоритме RSA. Однако число битов ключа, необходимое для надежной защиты данных при использовании RSA, за последние годы резко возросло, что обусловило соответствующий рост загрузки систем, использующих RSA. Криптография на основе эллиптических кривых (ECC – Elliptic Curve Cryptography) – появившийся сравнительно недавно подход, способный конкурировать с RSA.

Привлекательность данного подхода в сравнении с RSA заключается в том, что с использованием эллиптических кривых обеспечивается эквивалентный уровень защиты при значительно меньшем числе разрядов, вследствие чего уменьшается загрузка процессора. В то же время степень доверия к методам криптографии с использованием эллиптических кривых еще не настолько высока, как степень доверия к RSA.

Операция сложения в криптографии на основе эллиптических кривых является аналогом операции умножения по модулю простого числа в RSA, а многократное повторное сложение – аналогом возведения в степень. Чтобы построить криптографическую систему, используя эллиптические кривые, нужно найти «трудную проблему», соответствующую разложению на множители произведения двух простых чисел или дискретному логарифмированию.

Опишем построение криптографических систем с открытым ключом, основанных на конечной абелевой группе точек эллиптической кривой, определенной над ^*. Однако прежде чем описывать криптосистемы, нужно обсудить некоторые вспомогательные понятия.

Представление открытого текста. Мы намереваемся кодировать наши открытые тексты точками некоторой заданной эллиптической кривой Е, определенной над конечным полем . Мы хотим это осуществить простым и систематическим способом так, чтобы открытый текст 𝑚 (который можно рассматривать как целое число из некоторого интервала) можно было легко прочитать, зная координаты соответствующей точки . Заметим, что это «кодирование» – не то же самое, что засекречивание. Позднее мы будем рассматривать способы шифрования точек открытого текста. Однако законный пользователь системы должен быть в состоянии восстановить 𝑚 после расшифрования точки шифртекста.

Следует сделать два замечания. Во-первых, не существует детерминированного полиномиального (по logq) алгоритма для выписывания большого числа точек произвольной эллиптической кривой E над . В примере 10 мы выписали все точки, проведя полный перебор всех возможных вариантов, но это невозможно (по крайней мере, за разумное время) для p порядка 2¹⁶⁰, а именно таков должен быть размер p для обеспечения надежности при формировании цифровой подписи. Однако как мы увидим далее, существуют вероятностные алгоритмы с малой вероятностью неудачи. Во-вторых, порождать случайные точки на Е недостаточно: чтобы закодировать большое число возможных сообщений 𝑚, необходим какой-то систематический способ порождения точек, которые были бы связаны с 𝑚 определенным образом, например, чтобы x-координата имела с 𝑚 простую связь.

Приведем один возможный вероятностный метод представления открытых текстов как точек на эллиптической кривой Е, определенной над , где предполагается большим и нечетным^*. Пусть k – достаточно большое целое число, настолько, что можно считать k допустимым, если попытка представить в нужном нам виде элемент («слово») открытого текста 𝑚 оказывается неудачной в одном случае из ; практически достаточно k = 30 или, в крайнем случае, k = 50. Пусть элементы нашего сообщения 𝑚 – целые числа, . Предположим также, что выбранное нами конечное поле имеет q элементов, q > Мk. Записываем целые числа от 1 до Мk в виде где и устанавливаем взаимно однозначное соответствие между такими числами и некоторым множеством элементов из . Например, можно записать такое число, как r-значное число в р-ричной системе счисления и, отождествляя цифры в этой записи с элементами , рассматривать их как коэффициенты многочлена степени не выше r – 1 над , соответствующего элементу поля . Таким образом, числу (здесь ) ставится в соответствие многочлен который, будучи рассмотрен по модулю некоторого фиксированного неприводимого многочлена степени r над , дает элемент .

Итак, при данном 𝑚 для каждого j = 1, 2, …, k мы получаем элемент 𝑥 из , соответствующий mk + j. Для такого 𝑥 вычисляем правую часть уравнения

и пытаемся найти квадратный корень из . Извлечение квадратного корня в поле – это отдельная интересная задача, которой уделено достаточно внимания в соответствующей литературе [13].

Если мы находим такое у, что , то берем . Если не оказывается квадратом, то увеличиваем j на 1 и повторяем попытку с соответствующим значением 𝑥. Если мы находим 𝑥, для которого – квадрат прежде чем j превысит k, то мы можем восстановить 𝑚 по известной точке (𝑥, 𝑦) с помощью формулы , где – целое число, соответствующее 𝑥 при установленном взаимно однозначном соответствии между целыми числами и элементами . Так как – квадрат приблизительно в 50 % случаев (точнее, вероятность того, что есть квадрат, фактически равна N/(2q), однако N/(2q) очень близко к 1/2), то вероятность того, что метод не приведет к результату и мы не найдем точки с x-координатой, соответствующей целому числу между и , равна примерно .

Дискретный логарифм на Е. Опишем задачу дискретного логарифмирования.

Определение. Пусть Е – эллиптическая кривая над , и В – точка на Е. Задачей дискретного логарифмирования на Е (с основанием 𝑃) называется задача нахождения для данной точки 𝑄 Е такого целого числа 𝑛 Z (если оно существует), что 𝑛𝑃 = 𝑄.

Стойкость криптографических систем, определенных на эллиптических кривых, определяется сложностью решения задачи дискретного логарифмирования в группе ее точек, т. е. сложностью решения уравнения 𝑄 относительно n, где точки P и 𝑄 принадлежат одной циклической подгруппе. Как и в любой конечной абелевой группе, эту задачу можно решить за элементарных операций. В этой группе невозможно построить субэкспоненциальные алгоритмы решения этой задачи на тех принципах, использование которых привело к успеху в случае конечных полей.

Вполне возможно, что задача дискретного логарифмирования на эллиптической кривой окажется более трудной для решения, чем задача дискретного логарифмирования в конечных полях. Наиболее сильные методы, разработанные для конечных полей, по-видимому, не работают в случае эллиптических кривых. Это обстоятельство особенно отчетливо проявляется в случае полей характеристики 2. Специальные методы решения задачи дискретного логарифмирования в позволяют сравнительно легко вычислять дискретные логарифмы и, следовательно, вскрывать соответствующие криптосистемы, если r не выбрано очень большим. Аналогичные системы, использующие эллиптические кривые над (см. ниже), судя по всему, являются столь же надежными при значительно меньших значениях r.

До 1990 г. единственными известными алгоритмами дискретного логарифмирования на эллиптических кривых были те, которые работают в любой группе и не используют особенности ее строения. Эти алгоритмы с экспоненциальным временем работы применимы к случаям, когда порядок группы делится на большое простое число. Однако в 1993 г. Менезес (А. Menezes), Окамото (Т. Okamoto) и Вэнстон (S. Vanstone) предложили новый подход к задаче дискретного логарифмирования на эллиптической кривой Е, определенной над , показав, что эта задача сводится к задаче дискретного логарифмирования в некотором расширении исходного конечного поля , т. е. за полиномиальное время можно построить соответствующий изоморфизм. Метод Менезеса–Окамото–Вэнстона основан на том, что так называемое спаривание Вейля позволяет изоморфно вложить группу точек простого порядка 𝑢 (равного большому простому делителю порядка кривой N) в мультипликативную группу расширения основного поля. Необходимое условие для такого вложения, очевидно, следующее: 𝑢 должно делить порядок мультипликативной группы поля вложения, т. е. для некоторого k простое число 𝑢 должно делить . Это и есть условие Менезеса–Окамото–Вэнстона^*. Оно легко проверяется, поэтому всегда можно выбрать кривую с произвольно большим k, и, следовательно, исключить применимость субэкспоненциального алгоритма для решения задачи дискретного логарифмирования на данной кривой. Заметим, что это верно только для несуперсингулярных кривых. Именно по этой причине суперсингулярные кривые непригодны для криптографических применений. Следует упомянуть еще один эффективный алгоритм решения задачи дискретного логарифмирования на кривых со следом 1^**. В этом случае порядок кривой равен порядку основного поля и с помощью аппарата формальных групп исходная задача дискретного логарифмирования сводится к вычислению p-адического логарифма, т. е. очень простой задаче. Таких кривых очень мало, кроме того, легко избежать применения таких групп. Поэтому этот алгоритм не представляет практической угрозы для криптографических систем на эллиптических кривых. Следовательно, для решения задачи дискретного логарифмирования на эллиптических кривых известны только алгоритмы экспоненциальной сложности. Именно это свойство делает их столь привлекательными для криптографических применений, в частности, позволяет использовать ключи небольшого размера.

Таким образом, основные преимущества криптосистем на эллиптических кривых заключаются в том, что неизвестны субэкспоненциальные алгоритмы вскрытия этих систем, если в них не используются суперсингулярные кривые, а также кривые, порядки которых делятся на большое простое число.