Jump to content

    
Sign in to follow this  
Lixlex

Хеш-функция ГОСТ 34.11-2012 (Стрибог) оптимизация по утилизации

Recommended Posts

Если пойти тривиальным путём получается следующая картина:

  • S-функция. На один байт входного вектора расходуется одна ячейка BRAM. Двухпортовой памяти соответственно требуется в два раза меньше.
  • P-функция для FPGA бесплатно
  • L-функция - 2000 lut.

В процессорных реализациях используют таблицы предвычислений L и S функций:

https://github.com/drobotun/stribog_precalc/blob/master/gost_3411_2012_const.h

Но для финального вычисления требуется аж 64 обращения к таблицам, так что для FPGA этот метод выглядит бесполезным.

Есть ли другие пути оптимизации этого алгоритма или вся оптимизация возможна только за счет потери пропускной способности?

Share this post


Link to post
Share on other sites
1 hour ago, negiin said:

Какая требуется пропускная способность?

Какая ПЛИС используется?

А с какой целью интересуетесь?

Четких требований пока нет, я хотел бы выяснить, есть ли еще возможность для оптимизации на уровне lps-функций.

Пробовал имплементацию под 325й кинтекс - целиком влезла одна E-функция. 

Share this post


Link to post
Share on other sites
On 6/28/2019 at 10:05 AM, Lixlex said:

Но для финального вычисления требуется аж 64 обращения к таблицам, так что для FPGA этот метод выглядит бесполезным.

Почему? Современные FPGA имеют много быстрой памяти внутри.

Share this post


Link to post
Share on other sites
On 7/18/2019 at 4:22 PM, Koluchiy said:

Возможностей для оптимизации масса, всё зависит от того, что хотите получить.

Подскажите "массу", поскольку реализация стрибога "в лоб" гигантское число ресурсов, это притом, что Sboxes на BRAM (утилизация BRAM свыше 3000 шт).

Результат готов каждый такт (на вход тоже можно подавать каждый такт).

Критерий - максимизация T/A (Throughput/Area)

Share this post


Link to post
Share on other sites
On 7/19/2019 at 3:32 PM, count_enable said:

Почему? Современные FPGA имеют много быстрой памяти внутри. 

В этом случае мы лишь в 2 раза(и то не факт) выигрываем по утилизации, но в 64 раза проигрываем в пропускной способности.

Share this post


Link to post
Share on other sites
On 7/19/2019 at 7:44 PM, Doka said:

Подскажите "массу", поскольку реализация стрибога "в лоб" гигантское число ресурсов, это притом, что Sboxes на BRAM (утилизация BRAM свыше 3000 шт).

Результат готов каждый такт (на вход тоже можно подавать каждый такт).

Критерий - максимизация T/A (Throughput/Area)

Вы хотите каждый такт иметь что? Хэш-сумму для всего файла? А зачем? Файл может быть большой и подать его целиком на логику может быть физически невозможно. Более того, бессмысленно желать вычислять Стрибога быстрее, чем загружаете этот самый файл.

Так что, начинать надо с определения, какая "средняя" скорость поступления данных, и из нее уже решать, каким образом оптимизировать расчет.

Естественно, всё это только в случае, если требования скорости расчета реально заданы, а не просто желание кинуть в логику известный пример на Си вообще без переделки под FPGA.

 

Share this post


Link to post
Share on other sites
1 minute ago, Koluchiy said:

Вы хотите каждый такт иметь что? Хэш-сумму для всего файла? А зачем? Файл может быть большой и подать его целиком на логику может быть физически невозможно.

ок.   условия:

  • у меня есть набор данных каждый длиной 512бит
  • от каждого набора надо считать хеш (наборы независимы)
  • темп поступления набора - раз в такт
  • темп снятия результата - раз в такт

 

вопрос тот же:

какую "массу возможностей для оптимизации" вы могли бы рекомендовать.

важен критерий - максимизация T/A (Throughput/Area)

Share this post


Link to post
Share on other sites

Даже страшно подумать, чего Вы там обсчитываете, если на каждые 512 бит надо посчитать хэш в 512 бит, и всё это за 1 такт.

Для такой ширины шины 200Мгц - это уже 100Г.

Какая частота тактов?

Share this post


Link to post
Share on other sites
7 minutes ago, Koluchiy said:

Какая частота тактов?

As high as possible

Данные формируются внутри FPGA, так что ограничений нет никаких.

PS: Что за сфера применения догадаться не так сложно

Share this post


Link to post
Share on other sites

Не, я недогадливый. Расскажите, если не секретно. Если секретно - тогда не рассказывайте :).

Quote

As high as possible

Ой как я не люблю такие постановки задач... Гораздо лучше, когда люди знают, что они хотят.

 

Ладно, пара мыслей.

 

1. Стрибог - итерационный байт-ориентированный алгоритм, скармливать ему целиком строку и требовать сразу ответа - на мой взгляд, затея безнадежная.

 

2. Я бы пошел по пути распараллеливания с соответствующим увеличением латентности. Далее зависит от того, какая латентность устраивает.

 

1) Если латентность совсем не важна, наплодить ядер с последовательным расчетом (1 байт/такт, итерации последовательно). Каждое такое ядро занимает довольно небольшой объем, в большую микросхему их можно запихнуть много. Есть опыт реализации подобного ядра, если интересно - пишите в личку, поинтересуюсь у начальства по поводу возможности модернизации под Ваши нужды.

 

2) Если латентность не совсем не важна, хотя бы сделать расчет 1 итерации за 1 такт входных данных. Не знаю, во что это выльется, не пробовал.

 

3) Если с латентностью совсем никак, тогда только задирать рабочую частоту относительно частоты данных, и пытаться из этого как-то разбить расчет на итерации.

Share this post


Link to post
Share on other sites

у меня уже написанный и работающий стрибог, и конечно я, как и ТС после фразы о "массе возможностей для оптимизации" ожидали откровений именно для стрибог (и даже конкретно - для L-проеобразования), а не "Есть опыт реализации подобного ядра... поинтересуюсь у начальства..." :whistle3:

 

33 minutes ago, Koluchiy said:

Ой как я не люблю такие постановки задач... Гораздо лучше, когда люди знают, что они хотят.

а вам не кажется, что в случае ПЛИС этот кейс хорошо бьётся с намерением максимизации Т/А?

36 minutes ago, Koluchiy said:

1. Стрибог - итерационный байт-ориентированный алгоритм, скармливать ему целиком строку и требовать сразу ответа - на мой взгляд, затея безнадежная.

практика - критерий истины

36 minutes ago, Koluchiy said:

2. Я бы пошел по пути распараллеливания с соответствующим увеличением латентности.

как это вообще повлияет на Т/А? (никак)

37 minutes ago, Koluchiy said:

1) Если латентность совсем не важна, наплодить ядер с последовательным расчетом (1 байт/такт, итерации последовательно).

возьмите произвольный алгоритм хеширования/криптования - конвейеризованная реализация всегда раз выигрывает у итеративной/свёрнутой реализации, особенно это заметно у алгоритмов, параметры которых меняются от раунда к раунду (величина циклического сдвига, схема перемешивания, раундовые константы).

 

ЗЫЖ всёравно спасибо что не остались безучастным к проблеме.

Share this post


Link to post
Share on other sites
Quote

и конечно я, как и ТС 

Вы и ТС - одно лицо? Или откуда знаете, чего он хотел? :)

Quote

ожидали откровений именно для стрибог (и даже конкретно - для L-проеобразования)

Очень жаль, что я Вас разочаровал... :( В следующий раз подробнее пишите, чего Вам надо - а то выспрашивать приходиццо :).

В случае с ПЛИС довольно часто основная масса возможностей по оптимизации лежит в плоскости применения алгоритма к ПЛИС, а не доработке алгоритма. По крайней мере, я бы начал именно с этого, и скорее всего этого бы хватило для большинства задач. Когда читаешь от ТС про Е-функцию в 325 Кинтекс, первые мысли всегда о том, что дело не в доработке L-преобразования.

Quote

а вам не кажется, что в случае ПЛИС этот кейс хорошо бьётся с намерением максимизации Т/А?

Отсутствие задания реалистичных требований всегда плохо бьется со всем. В случае с ПЛИС, например, отсутствие задания частоты входных данных не позволяет понять, в сколько раз можно ускорить обработку за счет увеличения тактовой.

 

Quote

возьмите произвольный алгоритм хеширования/криптования - конвейеризованная реализация всегда раз выигрывает у итеративной/свёрнутой реализации

Это зависит от стоящих требований. В моем случае нужно было минимизировать объем при относительно небольшой скорости поступления данных. Конвейер был бы избыточен.

 

 

 

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this