А.В. ГЕРАСИМЧУК, К.А. ЕСЕНЬКОВ, М.С. КОБЗАРЬ,
Г.Ю. ЖИХАРЕВ
Научный руководитель – И.И. ШАГУРИН, д.т.н., профессор
Национальный исследовательский ядерный университет «МИФИ»
ОРГАНИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОГО КАНАЛА
ДЛЯ РАСЧЁТА ХЕШ-СУММ В КРИПТОБЛОКАХ,
РЕАЛИЗУЕМЫХ В СОСТАВЕ « СИСТЕМ НА КРИСТАЛЛЕ»
В докладе описывается предлагаемая структура вычислительного канала для использования в криптоблоках, выполняющих высокопроизводительные конвейерные вычисления хеш-функций в соответствии с алгоритмами MD4, MD5, SHA-1 и SHA-256.
При разработке криптоблоков, реализующих алгоритмы хеширования, обычно используются либо итеративная архитектура, либо архитектура развёртки цикла для организации вычислений [1, 2]. При этом представленные криптоблоки, как правило, реализуют только один криптографический алгоритм. В данной работе предлагается специализированная конвейерная архитектура, поддерживающая обработку сообщений в нескольких режимах (согласно алгоритмам MD4, MD5, SHA-1, SHA-256).
Вычислительный канал состоит из блока расширения входных сообщений, системного коммутатора и вычислительных конвейеров. Со входного интерфейса сообщения поступают на блок расширения в виде 32-битных слов. Блок расширения формирует из поступивших данных 512-битные блоки и направляет их в системный коммутатор. Блок расширения может выдавать данные как по одному слову расширенного сообщения за такт, так и одновременно несколько слов данных сообщения. Если длина сообщения больше или равна 448 бит, то происходит формирование нескольких блоков расширенного сообщения.
В алгоритмах MD5 и SHA-256 вычисления производятся за 4 раунда, в каждом из которых 16 итераций; в MD4 - 3 раунда по 16 итераций; в SHA-1 4 раунда по 20 итераций, но для реализации вместе с другими алгоритмами в работе он представляется как 5 псевдо-раундов по 16 итераций. В связи с этим вычислительные конвейеры состоят из 16 стадий. Все стадии независимы и на каждой в данный момент времени может происходить обработка одного из принятых сообщений.
Для наихудшего случая, когда новые сообщения приходят с максимальным темпом, вычислительный канал, включающий 4 конвейера, гарантирует обработку данных без блокировки внешнего интерфейса для алгоритмов MD4, MD5 и SHA-256. Для исключения блокировок при работе в режиме SHA-1, данные от системного коммутатора на вычислительные конвейеры поступает через буферы типа FIFO на 16 позиций, которые хранят данные во время обработки 5 раунда.
В предлагаемой архитектуре на стадиях происходит сложение до пяти операндов за такт. Это даёт большую задержку в вычислениях. Чтобы уменьшить её используются сумматоры с сохранением переносом (CSA) [3]. В данной работе CSA представлен как последовательное соединение компрессора и полного сумматора и используются (5:2)-компрессор и (4:2)-компрессор, состоящие из нескольких (3:2)-компрессоров соединённых последовательно. Компрессор (3:2) представляет собой логическую схему, которая преобразовывает три слагаемых в два. Важную роль имеет подключение слагаемых: слагаемые, которые известны заранее, надо подавать на первый компрессор, а те, что вычисляются на том же такте, на котором производится сложение, подаются на остальные. При подаче слагаемого, требующего вычисления на последний компрессор, происходит параллельное вычисление этого слагаемого и суммы остальных на предыдущих компрессорах, что приводит к уменьшению критического пути.
В связи со спецификой приёма данных с входного интерфейса нет возможности загружать конвейеры новыми сообщениями каждый такт. Это приводит к ограничению на максимальный темп выдачи результата: каждые два такта. В свою очередь, ограничение на темп поступления входных данных позволяет разделить каждую стадию на две ступени, т.е. данные на каждой стадии будут обрабатываться за два такта, что приводит к увеличению тактовой частоты. Для алгоритма SHA-256 используется подход, когда часть значений необходимых на текущей стадии, рассчитываются на предыдущей стадии. Например, на нулевой стадии рассчитывается первая часть вычислений, на первой стадии рассчитывается вторая часть и параллельно первая часть для новых данных и т.д.
Использование предлагаемой архитектуры позволяет при полной загруженности конвейера и при тактовой частоте 200 МГц (Virtex-7) получать хеш-сумм в секунду.
Список литературы
-
Ducloyer S. Hardware implementation of a multi-mode hash architecture for MD5, SHA-1 and SHA-2 / S. Ducloyer, R. Vaslin, G. Gogniat, E. Wanderley/ LESTER CNRS FRE 2734. Lorient, France, 2007.
-
Lien R. A 1 Gbit/s partially unrolled architecture of hash functions SHA-1 and SHA-512 / R. Lien, T. Grembowski, K. Gaj // CT-RSA. – 2004. – C. 324-338.
-
Prof. Loh. Carry-Save Addition // CS322- Processor Design. – 2005.
|