На заседании технического комитета по стандартизации "Криптографическая защита информации" (ТК 26) утвержден проект документа "Методические рекомендации по заданию параметров эллиптических кривых в соответствии с ГОСТ Р 34.10-2012", созданного специалистами нашей компании. В настоящей заметке рассказывается о цели этого документа и о принципах выбора кривых, которыми мы руководствовались.

Первого января 2013 года на территории России введен новый стандарт процессов формирования и проверки электронной подписи ГОСТ Р 34.10-2012 [1], призванный заменить предыдущий стандарт ГОСТ Р 34.10-2001. Новый стандарт позволяет работать как с ключами электронной подписи длины 256 бит (длина открытого ключа – 512 бит), так и с ключами длины 512 бит (длина открытого ключа – 1024 бита) и должен использоваться исключительно совместно с алгоритмом хэширования ГОСТ Р 34.11-2012 [2]. Если бы не последнее ограничение, можно было бы сказать, что новый стандарт является лишь расширением старого для работы с ключами 512 бит – дело в том, что в части процессов формирования и проверки подписи, созданной с помощью ключа длины 256 бит, новый и старый стандарты идентичны.

Российский стандарт электронной подписи ГОСТ Р 34.10-2012, как и его предшественник ГОСТ Р 34.10-2001, основан на вычислениях в группе точек эллиптических кривых и имеет структуру, близкую к схеме ECDSA. В определенном смысле ГОСТ Р 34.10-2001 и ГОСТ Р 34.10-2012 являются аналогами ГОСТ Р 34.10-94 при замене класса используемых циклических групп с мультипликативных групп простых полей на группы точек эллиптических кривых – точно так же, как ECDSA является аналогом DSA при аналогичных изменениях. Схемы ГОСТ Р 34.10-94 и DSA по структуре преобразований, в свою очередь, близки к классической схеме подписи Эль-Гамаля (1984 год), в частности, основываются на том же классе теоретико-сложностных предположений о трудности задачи нахождения дискретного полулогарифма. Строгое обоснование стойкости ГОСТ Р 34.10-2001 (переносимое без каких-либо изменений на ГОСТ Р 34.10-2012) в условиях принятых в мировой криптографической практике предположений, можно найти, например, в работе [3]. 

Итак, стойкость стандарта ГОСТ Р 34.10-2012 базируется на трудности решения задачи нахождения дискретного полулогарифма в группе точек эллиптической кривой. Напомним, что группа точек эллиптической кривой над конечным полем вычетов по модулю N – это множество решений уравнения y²=x³+ax+b mod N, где a и b являются определяющими кривую параметрами (приводится описание в часто используемой форме Вейерштрасса). Таким образом, для задания кривой достаточно зафиксировать параметры N, a и b, а для использования со стандартом ГОСТ Р 34.10-2012 также зафиксировать некоторую ее циклическую подгруппу и точку (x₀, y₀), являющуюся порождающим элементом этой подгруппы.

Особенностью стандарта ГОСТ Р 34.10-2012 является то, что в документе не зафиксированы какие-либо кривые, рекомендуемые для использования, присутствует только набор требований к ним. Для конкретных примеров кривых, приведенных в стандарте, явно оговорено, что они должны использоваться сугубо в тестовых целях. В этом наш стандарт существенно отличается, например, от документа, определяющего схему ECDSA: в FIPS PUB 186-4 [4] приведены рекомендованные (даже с пометкой "для использования в государственных учреждениях") кривые. С одной стороны, данный подход позволяет сохранять стандарт неизменным даже при появлении новых результатов о "слабых" классах эллиптических кривых: достаточно будет проверить новые ограничения для используемых на практике кривых и при необходимости быстро провести их замену – но не менять государственный стандарт. С другой стороны, отсутствие рекомендуемых для использования параметров требует дополнительных действий от криптографического сообщества по выбору и обоснованию конкретных параметров, а также согласованию их с регулирующими органами и созданию методических рекомендаций.

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

Для кривых с модулем 512 бит было решено строить кривые исходя из следующих принципов:

• Минимизация требований к модификации существующих программных и аппаратных реализаций ГОСТ Р 34.10-2001  (для кривых с модулем 256 бит) для работы с новыми кривыми (с модулем 512 бит).
• Обеспечение наименьшей трудоемкости операций на новых кривых.
• Доказуемая псевдослучайность новых кривых.

Первый принцип позволяет упростить разработчикам криптографических средств реализацию новых алгоритмов. Удобнее всего было бы просто увеличить в два раза используемые блоки данных и обобщить существующие алгоритмические схемы для работы с обеими длинами. Это накладывает ограничения на класс возможных кривых; в рамках этого класса желательно выбрать кривые с минимальными трудоемкостями операций (второй принцип). Соблюдение третьего принципа дает гарантию, что у полученных кривых отсутствуют слабости, заложенные авторами, но неизвестные другим членам сообщества.

В соответствии с этими принципами была создана методика выработки кривых, построенная вокруг следующих ключевых моментов:

• Для повышения эффективности операций в базовых полях вычетов определяющие поля простые числа выбираются близкими к степеням двойки (в нашем случае, к 2⁵¹¹ и 2⁵¹²).
• Кривые выбираются в короткой форме Вейерштрасса, как и существующие кривые для длины модуля 256 бит.
• Выбираются эллиптические кривые с группой точек, имеющей порядок, равный простому числу.
• Рассматриваются только кривые с коэффициентом a в форме Вейерштрасса равном минус трем.
• Учитывается требование возможности определенной верификации "случайности" кривой.

Выбор параметров эллиптической кривой производится в соответствии с принципом «проверяемой случайности», заключающимся в выработке параметров с помощью односторонней функции, или, на практике, с помощью некоторого «трудно» обратимого преобразования (в нашем случае – на основе криптографической хэш-функции ГОСТ Р 34.11-2012). На вход данного преобразования подаются случайные строки. В силу свойств односторонней функции, даже специальный подбор входных строк не позволяет осуществлять выбор окончательных параметров для принадлежности некоторому классу заведомо "слабых" (хотя заметим, что требования к кривым, предъявляемые в тексте стандарта, уже гарантируют отсутствие принадлежности кривых известным классам "слабых" кривых). В качестве параметра, значение которого полагалось равным выходу хэш-функции, выбран параметр r =  a³/b²  mod N (см. [6]), задающий два класса эквивалентных кривых. 

После порождения r, фиксации a=-3 и выбора одной из двух возможных кривых фиксацией b, необходимо проверить весь набор требуемых в методике свойств. Большая часть из них проверяется по параметрам a и b тривиальным образом (проверками некоторых соотношений на a и b), некоторые же требуют применения весьма мощных и трудоемких алгоритмов (например, для проверки того факта, что порядок группы точек кривой является простым числом, используется алгоритм Шуфа-Элкиса-Аткина (1985, 1988, 1991), которому может потребоваться несколько минут машинного времени для проверки одной кривой). После получения кривой, удовлетворяющей всем проверявшимся свойствам, остается только выбрать ее циклическую подгруппу и ее порождающий элемент – но так как порядок группы точек является простым числом, то данный шаг тривиален: вся группа является циклической, а любой ее ненулевой элемент является порождающим. Для дополнительного ускорения вычислений при работе на данной кривой в качестве порождающего элемента выбирается точка кривой (x₀,y₀) с малым значением x₀.

Полученные две эллиптические кривые получили одобрение для использования с ГОСТ Р 34.10-2012; техническим комитетом по стандартизации "Криптографическая защита информации" приняты соответствующие методические рекомендации, кривым присвоены объектные идентификаторы. В КриптоПро CSP 4.0 данные эллиптические кривые используются для полного спектра операций, использующих ключи алгоритма ГОСТ Р 34.10-2012 длины 512 бит. И разумеется, все положительные свойства этих эллиптических кривых, что были заложены нами на этапе разработки рекомендаций, используются в КриптоПро CSP 4.0 в полном объеме.

Литература

1. ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

2. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования.

3. Варновский Н.П. Стойкость схем электронной подписи в модели с защищенным модулем. Дискретная математика, 2008, т. 20, вып. 3, с. 147-159.

4. FIPS PUB 186-4. FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION. Digital Signature Standard (DSS).

5. V.Popov, I. Kurepkin, S. Leontiev. RFC 4357. Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms.

6. ISO/IEC 15946-5:2009. Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 5: Elliptic curve generation.

Скачать проект документа "Методические рекомендации по заданию параметров эллиптических кривых в соответствии с ГОСТ Р 34.10-2012".

Скачать скрипт с верификацией утвержденных наборов параметров.

Смышляев С.В., к.ф.-м.н.