Решением Технического комитета по стандартизации "Криптографическая защита информации" (ТК 26) утвержден проект документа "Рекомендации по стандартизации. Задание параметров скрученных эллиптических кривых Эдвардса в соответствии с ГОСТ Р 34.10-2012", подготовленного специалистами нашей компании. О том, что такое скрученные кривые Эдвардса, кому они нужны и какую пользу рекомендуемые ТК 26 кривые могут принести, мы расскажем в настоящей заметке.
В ГОСТ-е нет ни слова ни про какого Эдвардса, тем более скрученного, откуда он взялся?
В стандарте действительно идет речь о кривых в форме Вейерштрасса, то есть кривых, задаваемых уравнением y2=x3+ax+b. Однако в общем случае эллиптическая кривая может задаваться и другим уравнением, а кривые Вейерштрасса выбраны для описания благодаря следующему замечательному свойству – уравнение любой эллиптической кривой с помощью подходящей замены координат может быть приведено к уравнению кривой Вейерштрасса (речь идет об эллиптических кривых над большими простыми полями). Таким образом, форма Вейерштрасса для эллиптических кривых – это некий "универсальный язык". В соответствии с ГОСТ 34.10-2012, в форме Вейерштрасса следует представлять только результаты вычислений, производимых на кривых. Никаких ограничений на форму, используемую для выполнения промежуточных вычислений, в том числе, на то, с помощью каких представлений они производятся, стандарт не накладывает.
Зачем же нужны другие формы представления эллиптических кривых? Вспомним, что эллиптические кривые используются в криптографии вследствие того, что множество точек этих кривых образует аддитивную группу. Закон сложения в этой группе устроен достаточно нетривиальным образом. Замена координат приводит к изменению не только задающего кривую уравнения, но и формул, определяющих групповую операцию, что в свою очередь влияет на скорость вычислений. Этот путь открывает обширные возможности по выбору кривых, допускающих возможность построения эффективных реализаций.
Исследованиям свойств кривых, допускающих различные представления, посвящено множество работ (например, см. работы [1] и [2], содержащие обширный список литературы). Спектр исследуемых форм представлений эллиптических кривых весьма широк: форма Гессе, форма пересечений Якоби, форма Монтгомери, форма Эдвардса и т.д. (обширный список разных форм представления кривых с перечислением их свойств приведен здесь).
И чем же так хорош этот скрученный Эдвардс?
Двумя основными плюсами скрученных кривых Эдвардса (уравнение eu2+v2=1+du2v2) по сравнению с кривыми Вейерштрасса являются следующие:
- возможность построения более эффективных реализаций;
- однородность закона сложения.
Расскажем о каждом из этих преимуществ.
Результаты ряда исследований (см. работы [3] и [4]), проведенных, в том числе, специалистами нашей компании, показали, что закон сложения точек на скрученных кривых в форме Эдвардса допускает построение реализаций ГОСТ Р 34.10-2012, которые позволяют ощутимо увеличить скорость вычислений. Причем это ускорение наблюдается не только для модельных реализаций, но и для полноценно функционирующего СКЗИ, в котором учитываются все требования по защищенности. Среднее по трем основным операциям (формирование подписи, проверка подписи и выработка ключа VKO) ускорение для кривых с модулем размера 256 бит составило 20%, для кривых с модулем размера 512 битов – 25%.
Вторым из обозначенных выше преимуществ скрученных кривых Эдвардса является однородность закона сложения. Для кривых Вейерштрасса сложение двух разных точек и сложение двух одинаковых точек (то есть удвоение) производятся по разным формулам. При этом отличается также и скорость выполнения этих операций. Влияние этой разницы на скорость проведения высокоуровневых криптографических операций может привести к атакам по побочным каналам. Закон сложения на скрученных кривых Эдвардса не имеет этой неприятной особенности.
Отметим дополнительно, что построенные ранее и рекомендованные к использованию в соответствии с ГОСТ 34.10-2012 эллиптические кривые невозможно представить в форме скрученных кривых Эдвардса. Это объясняется тем, что для существования такого представления необходимо, чтобы порядок кривой делился на 4, а порядки упомянутых кривых являются простыми числами. Поэтому для использования всех преимуществ скрученных кривых Эдвардса такие кривые необходимо было сначала построить.
Как мы их делали
Основные принципы, которыми руководствовались специалисты нашей компании при создании скрученных кривых Эдвардса, во многом совпадают с теми, которые были определяющими при создании обычных кривых Вейерштрасса. А именно, кривые должны удовлетворять следующим условиям:
- Малая трудоемкость выполнения операций на кривых;
- Доказуемая псевдослучайность кривых;
- Отсутствие у кривых известных уязвимостей (см. [7]).
Для того, чтобы удовлетворить первому из перечисленных условий, характеристики используемых конечных полей выбирались близкими к степени двойки, а параметр e из уравнения, задающего кривую, выбирался равным 1. Еще более эффективные реализации удается построить для кривых с параметром e=-1, но такие кривые не удовлетворяют двум требованиям по защищенности: кофакторы основной и двойственной кривых должны быть равны 4.
Мы не будем останавливаться подробно на свойстве доказуемой псевдослучайности, т.к. оно было достаточно подробно рассмотрено в заметке о генерации кривых Вейерштрасса.
Два из множества требований, относящихся к отсутствию у кривых Эдвардса известных уязвимостей, мы уже упоминали – они связаны с кофакторами основной и двойственной кривых.
Построенные кривые удовлетворяют самым сильным требованиям по стойкости к MOV-атаке (см. [6], [8]): методу, основанному на сведении задачи дискретного логарифмирования на кривой к логарифмированию в мультипликативной группе некоторого конечного поля. Неприменимость этого метода обеспечивается отсутствием возможности вложить группу точек кривой в мультипликативную группу поля достаточно малой мощности. Для этого достаточно, чтобы минимальное натуральное t, для которого выполнено условие pt=1 mod |E|, было достаточно велико (здесь p – характеристика поля, а |E| – порядок кривой). Для обоих кривых Эдвардса этот параметр равен |E|-1, то есть является максимально возможным.
Еще одно требование, которому удовлетворяют построенные кривые – существенная негладкость порядка скрученной кривой, то есть среди его делителей должно присутствовать очень большое простое число (сравнимое по порядку с |E|). Если порядок скрученной кривой раскладывается в произведение малых простых чисел, это может быть использовано для определения секретного ключа путем подмены точки с используемой кривой на точку со скрученной кривой. Особенность операций на кривых в том, что если абонент не проверяет принадлежность точки кривой, то результат проделанных им вычислений будет кратной точкой на навязанной кривой. Наличие в группе точек скрученной кривой циклических подгрупп малого порядка позволяет противнику использовать китайскую теорему об остатках для определения секретного ключа. Несмотря на то, что указанный метод применим лишь в том случае, если абонент не проверяет принадлежность точки используемой кривой, его необходимо брать в расчет. Ни для одной из построенных кривых этот метод не применим (разложения порядков скрученных кривых имеет вид 4·r, где r – простое число, а порядок скрученной кривой примерно равен порядку самой кривой).
Что получилось в результате
Были построены две скрученные эллиптические кривые в форме Эдвардса: одна для 256-битного модуля, вторая – для 512-битного модуля. Эти кривые получили одобрение для использования со схемой подписи ГОСТ Р 34.10-2012; Техническим комитетом по стандартизации "Криптографическая защита информации" приняты соответствующие методические рекомендации, кривым присвоены объектные идентификаторы. В КриптоПро CSP 4.0 данные эллиптические кривые используются для полного спектра операций, использующих ключи алгоритма ГОСТ Р 34.10-2012 длины 256 и 512 бит. И, разумеется, все положительные свойства этих эллиптических кривых, что были заложены нами на этапе разработки рекомендаций, используются в КриптоПро CSP 4.0 в полном объеме.
Литература
[1] Василенко О.Н. “О вычислении кратных точек на эллиптических кривых над конечными полями с использованием нескольких оснований систем счисления и новых видов координат”. Матем. вопр. криптогр., 2:1 (2011), 5-28.
[2] Василенко О.Н. “Новые методы вычисления кратной точки на эллиптической кривой над конечным полем”. Тр. по дискр. матем., 11, № 2, Физматлит, М., 2008, 5-30.
[3] Гребнев С.В., Дыгин Д.M. “Современные алгоритмы вычисления кратной точки и суммы кратных точек эллиптической кривой над конечным простым полем и их приложение к реализации схемы электронной цифровой подписи ГОСТ Р 34.10”. Материалы XIV международной конференции "РусКрипто'2012".
[4] Алексеев Е.К., Ошкин И.Б., Попов В.О., Смышляев С.В., Сонина Л.А. “О перспективах использования скрученных эллиптических кривых Эдвардса со стандартом ГОСТ Р 34.10-2012 и алгоритмом ключевого обмена на его основе”. Материалы XVI международной конференции "РусКрипто'2014".
[5] http://www.hyperelliptic.org/EFD/index.html
[6] Menezes A.J., Okamoto T., Vanstone S.A. “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field”. IEEE Transactions On Information Theory, Vol. 39, No. 5, September 1993.
[7] http://safecurves.cr.yp.to/
[8] Семаев И.А. “О вычислении логарифмов на эллиптических кривых”. Дискрет. матем., 8:1 (1996), 65–71.
Смышляев С.В., к.ф.-м.н.,
начальник отдела защиты информации
ООО "КРИПТО-ПРО"
Ошкин И.Б., к.ф.-м.н.,
заместитель начальника отдела защиты информации
ООО "КРИПТО-ПРО"
Алексеев Е.К., к.ф.-м.н.,
инженер-аналитик 1 категории
ООО "КРИПТО-ПРО"
Сонина Л.А.,
инженер-аналитик 2 категории
ООО "КРИПТО-ПРО"