О чем статья

На просторах интернета есть несколько статей об алгоритме получения хеш-функции Стрибог (ГОСТ 34.11-2012), в том числе и на Хабре. Однако везде в качестве примера приводится реализация на языках программирования C, C#, Python и других. То есть идет последовательное выполнение операций алгоритма. В данной статье я хочу затронуть аппаратную реализацию на языке System Verilog, уделить внимание распараллеливанию вычислений и описанию интерфейсов модулей. Для начала кратко рассмотрим теорию.

Краткая теория

Основу алгоритма составляют последовательное исполнение так называемой g функции и функции сложения в кольце. Структурную схему можно увидеть на рисунке 1. Подробную теорию и математическое описание можно почитать в ГОСТ 34.11—2012 или в этой статье. Мы же рассмотрим, что подается на вход и получается на выходе. А далее рассмотрим практическую реализацию.

Сложение в кольце

На рисунке обозначено sc(a,b). В данной функции 512-разрядный вход а складывается с 512-разрядным входом b, результат пишется в 512 разрядный выход s. Если есть переполнение, то оно отбрасывается.

G функция

На рисунке обозначено g(m,h,n).

m – это входной массив данных, для которого считается хеш-функция, разбитый по 512 бит. Если последний кусочек меньше 512 бит, то оно сразу дополняется нулями с единичкой в первом дополнительном разряде до полных 512 бит;

h – это выход функции от предыдущей итерации, если итерация первая, то подается инициализационное значение V₀ = `{64{8`h00}} или V₀ = `{64{8`h01}} ;

n – количество бит исходного сообщения в 512 битном кусочке. Для целого кусочка значения будет 512 бит;

Если исходный массив больше 512 бит, то вычисления состоят из трех этапов :

• Инициализация

• Рекурсия

• Дополнение

Если исходный массив меньше или равен 512 бит, то вычисления состоят из двух этапов :

• Инициализация

• Дополнение

Хеш-функция «Стрибог» может иметь две реализации с результирующим значением длиной 256 или 512 бит. Для реализации 512 бит на этапе инициализации V₀ = `{64{8`h00}}, для реализации 256 бит на этапе инициализации V₀ = `{64{8`h01}}, а c выхода последней g функции берутся старшие 256 бит.

Рассмотрим внутреннее устройство g функции. Структурная схема представлена на рисунке 2. Данная функция состоит из LPSX функций и операций исключающего “ИЛИ”. Кроме того, используется массив итерационных констант, который используется для входного аргумента b функции LPSX на итерациях с 1 по 12. Значения констант из массива приведено в ГОСТ 34.11-2012.

LPSX-функция

Структурная схема представлена на рисунке 3. Функция LPSX представляет из себя алгоритм преобразования и перестановки байт, который можно реализовать последовательно через функции X,S,P,L про которые можно подробно почитать здесь или здесь. Преобразования S и L можно выполнить заранее и сформировать восемь массивов по 256 восьмибайтовых чисел, в которых будут содержаться все возможные значения этих двух преобразований. Помимо этого, при вычислении хеш‑суммы с использованием заранее рассчитанных значений можно сразу сделать и нужные перестановки в соответствии с преобразованием P. Таким образом последовательные преобразования LPSX можно заменить одним преобразованием PRECALC с массивом заранее расчитанных значений.

Аппаратная реализация

Распараллеливание вычислений

В отличие от программной реализации, аппаратная реализация в ПЛИС или ASIC позволяет распараллеливать вычисления. Так, на верхнем уровне параллельно и независимо друг от друга в каждой итерации производятся вычисления в двух функциях суммирования по модулю 2 и вычисление g функции. Если посмотреть на структурную схему реализации g функции, то можно заметить, что вычисление LPSX функций от входа n и массива констант C идет независимо от вычисления LPSX функций от входа m (см. рисунок 2). Следовательно, при вычислении g функции можно создать два экземпляра LPSX функций, которые будут работать параллельно, производя по 12 итераций до получения выходного значения g функции. Схематично такая реализация представлена на рисунке 4.

Описание интерфейсов

Для каждой функции приведу интерфейс для реализации на языке описания аппаратуры Verilog или VHDL, а также диаграмму сигналов.

LPSX-функция

Представляет из себя регистровый конвейер вычислений. На вход подаются данные и сигнал валидности. На выходе преобразованные данные и сигнал валидности.

G функция

Представляет из себя регистровый конвейер вычислений. На вход подаются данные и сигнал валидности. На выходе преобразованные данные и сигнал валидности.

Функция сложения в кольце

Представляет из себя регистровый конвейер вычислений. На вход подаются данные и сигнал валидности. Поскольку идет суммирование входного числа с результатом предыдущего вычисления, то удобнее оставить один вход данных и добавить сигнал очистки модуля clear_i.

Модуль верхнего уровня

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

• системные – частота и сброс

• настройки – выбор длины хеша

• входные данные – данные с рукопожатием valid/ready, а также флаг последнего сообщения и количество значимых бит в последнем сообщении

• управление – запрос на старт работы автоматов модуля и подтверждение выставляемое после получения хеша

• выходные данные — данные с рукопожатием valid/ready

  

  

Заключение. Описание исходников

Исходные файлы хеш-функции Стрибог на языке System Verilog находятся в моем репозитории git. Также там представлен тестбенч с примерами из ГОСТа. Для запуска симуляции в программе QuestaSim необходимо выполнить:

в консольном режиме для реализации без предвычислений,

make run_questa_console

в консольном режиме для реализации c предвычислениями,

make precalc=1 run_questa_console

в графическом режиме для реализации без предвычислений,

make run_questa_gui

в графическом режиме для реализации c предвычислениями.

make precalc=1 run_questa_gui