Реализация постквантовой электронной подписи SPHINCS+ на основе алгоритма ГОСТ 34.11-2012/18

Квантовые вычисления стремительно развиваются, одновременно всё больше угрожая традиционной криптографии. В современном мире пока не существует стандартов постквантовой криптографии и настоящая работа призвана внести вклад в развитие этой области. SPHINCS⁺ имеет три стандартные реализации, на базе: SHAKE256, SHA-256 и Haraka [1, с. 12]. Настоящая работа предлагает реализацию на базе ГОСТ 34.11-2012/18 («Стрибог») [2].

Для начала необходимо ознакомиться с предложенными алгоритмами. ГОСТ 34.11-2012/18 – это российский стандарт криптографической хэш-функции, более известный как «Стрибог». Он работает в двух режимах: выходной хэш полной длины (512 бит) и половины длины (256 бит). Алгоритм можно разделить на три стадии (рис. 1) [3, с. 3].

Рис. 1. Стадии алгоритма «Стрибог»

SPHINCS⁺ – это алгоритм-участник конкурса стандартизации постквантовой криптографии от NIST. Является электронной подписью на основе хэш-функции.

Основным компонентом SPHINCS⁺ является гипердерево [1, с. 7]. Это так называемое дерево деревьев, соединённое между собой одноразовой схемой подписи (OTS) WOTS⁺ [1, с. 7]. Листовые узлы выбираются случайно, и чтобы разрешить компромисс между размером дерева и вероятностью выбора одинакового конечного узла, в нижней части гипердерева используется малократная подпись (FTS) FORS [1, с. 7] Корневой узел дерева является публичным ключом, его необходимо знать при верификации. Однако, чтобы не хранить всё дерево, подписи содержат в себе аутентификационные пути, позволяющие восстановить путь к корню. Алгоритм способен гибко настраивать размер подписи и скорость её создания благодаря своим параметрам. Пример конструкции гипердерева представлен на рисунке 2.

Рис. 2. Пример конструкции гипердерева

Все значения вычисляются при помощи семейства криптографических хэш-функций [1, с. 6]. Рассмотрим каждого представителя семейства и действия, необходимые для интеграции «Стрибога» в них.

1. Th_l (F, H)

Настраиваемая хэш-функция (tweakable hash function) в дополнение к сообщению  (l – количество блоков; n – длина одного блока) получает на вход публичный параметр  и настройку (tweak) . Настройка является адресом в гипердереве.

Имеет частные случаи, когда длина входное сообщения равна длине одного блока (F) или двух блоков (H):

Th_l (F, H) не предполагает каких-либо изменений для хэш-функции, а лишь определяет данные на входе;

2. PRF

Псевдослучайная функция генерации секретного ключа. На вход функция принимает: seed-значение секретного ключа  и его адрес в гипердереве  . Результатом функции будет псевдослучайный секретный ключ.

PRF не предполагает каких-либо изменений для хэш-функции, а лишь определяет данные на входе;

3. PRF_msg

Псевдослучайная функция генерации случайности для сжатия сообщения. На вход функция принимает: секретный ключ , опциональное случайное значение  и сообщение . Результатом функции будет “случайность”, используемая для сжатия исходного сообщения.

Для использования «Стрибога» в PRF_msg на его основе реализован HMAC:

4. H_msg

Функция сжатия подписываемого сообщения. На вход функция принимает: “случайность” (PRF_msg)  , публичный ключ  и сообщение . Результатом функции будет подпись FORS и значения адресов дерева и листа. H_msg предполагает значение на выходе, длина которого фиксирована и зависит от исходных параметров SPHINCS⁺. Таким образом хэш-функция должна иметь возможность устанавливать произвольную длину хэш-кода. Так как «Стрибог» не обладает такой возможностью, будет использована функция генерации маски (MGF1) [4, с. 28], позволяющая получить выходное значение произвольной длины с сохранением криптографических свойств хэш-функции

Полученное семейство на основе алгоритма «Стрибог» может быть использовано в рамках SPHINCS⁺.

Таким образом в работе была получена постквантовая электронная подпись SPHINCS⁺ на базе российского стандарта ГОСТ 34.11-2012/18.

1. Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, Peter Schwabe. The SPHINCS+ Signature Framework. [Электронный ресурс]. – Режим доступа: https://sphincs.org/data/sphincs+-paper.pdf
2. ГОСТ Р 34.11-2018. Криптографическая защита информации. Функция хэширования. Введён в действие 1 июня 2019.
3. Oleksandr Kazymyrov, Valentyna Kazymyrova. Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012. [Электронный ресурс]. – Режим доступа: https://eprint.iacr.org/2013/556.pdf
4. RFC2437. RSA Cryptography Specification Version 2.0. [Электронный ресурс]. – Режим доступа: https://www.ietf.org/rfc/rfc2437.txt