Хеш-функция Стрибог. Особенности аппаратной реализации на System Verilog
О чем статья
На просторах интернета есть несколько статей об алгоритме получения хеш-функции Стрибог (ГОСТ 34.11–2012), в том числе и на Хабре. Однако везде в качестве примера приводится реализация на языках программирования C, C#, Python и других. То есть идет последовательное выполнение операций алгоритма. В данной статье я хочу затронуть аппаратную реализацию на языке System Verilog, уделить внимание распараллеливанию вычислений и описанию интерфейсов модулей. Для начала кратко рассмотрим теорию.
Краткая теория
Основу алгоритма составляют последовательное исполнение так называемой g функции и функции суммирования по модулю 2. Структурную схему можно увидеть на рисунке 1. Подробную теорию и математическое описание можно почитать в ГОСТ 34.11—2012 или в этой статье. Мы же рассмотрим, что подается на вход и получается на выходе. А далее рассмотрим практическую реализацию.
Рисунок 1. Структурная схема хеш-функции Стрибог
Суммирование по модулю два
На рисунке обозначено smod2(a, b). В данной функции 512-разрядный вход, а складывается с 512-разрядным входом b, результат пишется в 512 разрядный выход s. Если есть переполнение, то оно отбрасывается.
G функция
На рисунке обозначено g (m, h, n).
m — это входной массив данных, для которого считается хеш-функция, разбитый по 512 бит. Если последний кусочек меньше 512 бит, то оно сразу дополняется нулями с единичкой в первом дополнительном разряде до полных 512 бит;
h — это выход функции от предыдущей итерации, если итерация первая, то подается инициализационное значение V0 = `{64{8`h00}} или V0 = `{64{8`h01}} ;
n — количество бит исходного сообщения в 512 битном кусочке. Для целого кусочка значения будет 512 бит;
Если исходный массив больше 512 бит, то вычисления состоят из трех этапов :
Если исходный массив меньше или равен 512 бит, то вычисления состоят из двух этапов :
Хеш-функция «Стрибог» может иметь две реализации с результирующим значением длиной 256 или 512 бит. Для реализации 512 бит на этапе инициализации V0 = `{64{8`h00}}, для реализации 256 бит на этапе инициализации V0 = `{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 позволяет распараллеливать вычисления. Так, на верхнем уровне параллельно и независимо друг от друга в каждой итерации производятся вычисления в двух функциях суммирования по модулю 2 и вычисление 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-функции
Суммирование по модулю 2
Представляет из себя регистровый конвейер вычислений. На вход подаются данные и сигнал валидности. Поскольку идет суммирование входного числа с результатом предыдущего вычисления, то удобнее оставить один вход данных и добавить сигнал очистки модуля clear_i.
Рисунок 9. Интерфейс функции суммирования по модулю 2
Рисунок 10. Временная диаграмма функции суммирования по модулю 2
Модуль верхнего уровня
Представляет из себя регистровый конвейер вычислений. На модуль приходят 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