Хеш-функция Стрибог. Особенности аппаратной реализации на System Verilog

О чем статья

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

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

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

Рисунок 1. Структурная схема хеш-функции Стрибог

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

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

G функция

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

m – это входной массив данных, для которого считается хеш-функция, разбитый по 512 бит. Если последний кусочек меньше 512 бит, то оно сразу дополняется нулями с единичкой в первом дополнительном разряде до полных 512 бит. Если длина сообщения кратна 512 битам, то дополнительно вычисляется g функция для m = 512`h00...01 (единица в младшем разряде), при этом суммирование в кольце для количества бит не ведется (n=0), а суммирование в кольце для сообщения производится для m = 512`h00...01 (единица в младшем разряде) ;

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

n – результат функции сложения в кольце для количества бит в 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.

Рисунок 2. Структурная схема G функции

LPSX-функция

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

Рисунок 3. Структурные схемы LPSX функций

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

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

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

Рисунок 4. Структурная схема распараллеливания вычислений LPSX функций внутри G функции

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

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

LPSX-функция

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

Рисунок 5. Интерфейс LPSX-функции

Рисунок 6. Временная диаграмма LPSX-функции

G функция

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

Рисунок 7. Интерфейс G-функции

Рисунок 8. Временная диаграмма G-функции

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

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

Рисунок 9. Интерфейс функции сложения в кольце

Рисунок 10. Временная диаграмма функции сложения в кольце

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

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

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

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

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

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

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

  

  Рисунок 11. Интерфейс модуля верхнего уровня хеш-функции Стрибог

  

  Рисунок 12. Временная диаграмма модуля верхнего уровня хеш-функции Стрибог

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

Исходные файлы хеш-функции Стрибог на языке 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