Эллиптические кривые для нового стандарта электронной подписи

Пример эллиптической кривой На заседании технического комитета по стандартизации "Криптографическая защита информации" (ТК 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 – это множество решений уравнения y2=x3+ax+b mod N, где a и b являются определяющими кривую параметрами (приводится описание в часто используемой форме Вейерштрасса). Таким образом, для задания кривой достаточно зафиксировать параметры N, a и b, а для использования со стандартом ГОСТ Р 34.10-2012 также зафиксировать некоторую ее циклическую подгруппу и точку (x0, y0), являющуюся порождающим элементом этой подгруппы.

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

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

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

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

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

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

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

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

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

Полученные две эллиптические кривые получили одобрение для использования с ГОСТ Р 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".

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


 

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


Купить

Вход

Подписка на обновления