Область техники, к которой относится изобретение

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

Уровень техники

В современных цифровых устройствах для обеспечения аутентичности информации используются различные ключевые хэш-функции. Одной из таких хэш-функций является функция GHASH, описанная в стандарте ISO/IEC 19772:2009 А.8.

Формула изобретения

1. Устройство для вычисления хэш-функции для кадра цифровых данных, причем кадр данных состоит из блоков данных длиной k бит, включающее

блок предварительной подготовки, имеющий М входов размерностью k бит, при этом М>1;

М блоков конвейерного вычисления, входы которых являются соответствующими выходами блока предварительной подготовки, и которые используют конвейерные перемножители, содержащие L каскадов;

блока объединения, имеющего М входов, причем каждый вход подключен к соответствующему выходу блока конвейерного вычисления, а выход блока объединения является выходом устройства в целом;

при этом блок предварительной подготовки также имеет М буферных регистров FIFO и выполнен с возможностью

записывать поступающие одновременно на М входов блоки данных в концы соответствующих буферных регистров FIFO;

определять количество блоков данных, записанных в буферные регистры FIFO блока предварительной подготовки;

определять наличие в буферных регистрах FIFO блока предварительной подготовки последнего блока данных кадра данных;

считывать из соответствующих буферных регистров FIFO блоки данных во все М выходов блока предварительной подготовки при условии наличия в буферных регистрах FIFO блока предварительной подготовки L×M блоков данных или наличия в буферных регистрах FIFO блока предварительной подготовки последнего блока данных кадра данных;

помечать выходы блока, как не имеющие данных, при условии отсутствия в буферных регистрах FIFO блока предварительной подготовки L×M блоков данных и отсутствия в буферных регистрах FIFO блока предварительной подготовки последнего блока данных кадра данных;

нумеровать считываемые из буферных регистров FIFO блока предварительной подготовки блоки данных, причем

при наличии последнего блока данных в буферных регистрах FIFO блока предварительной подготовки, нумерация блоков данных осуществляется, начиная с конца кадра данных, и производится, начиная с нуля,

при отсутствии последнего блока данных в буферных регистрах FIFO блока предварительной подготовки, каждому считываемому блоку присваивается номер L×М;

каждый из М блоков конвейерного вычисления, работающих параллельно, содержит

модуль памяти,

модуль отключения обратной связи,

сумматор,

конвейерный перемножитель, имеющий L каскадов,

блок обратной связи,

блок накопления;

при этом модуль памяти выполнен с возможностью

хранить записанные в него данные;

выдавать на выход модуля памяти данные, хранящиеся в тех ячейках модуля памяти, номер которых равен номерам блоков данных, поступающих на вход модуля памяти;

сумматор содержит 1-й и 2-й входы и один выход и выполнен с возможностью суммировать в поле GF(2^k) приходящие на 1-й и 2-й входы блоки данных и передавать результат на выход сумматора;

модуль отключения обратной связи содержит 1-й и 2-й входы, счетчик и выход и выполнен с возможностью

увеличивать значение счетчика, при поступлении блока данных на 2-й вход;

передавать на выход блок данных с 1-го входа, если значение счетчика больше или равно М;

передавать на выход блок данных, содержащий нули во всех битах, если значение счетчика меньше М;

обнулять значение счетчика, если номер блока данных, поступившего на 2-й вход, меньше М;

конвейерный перемножитель содержит

1-й и 2-й входы,

L каскадов конвейера перемножения, подключенные друг за другом, работающие одновременно, и каждый из которых выполняет свою часть вычислений произведения двух блоков, при этом входы первого каскада конвейера перемножения подключены к входам конвейерного перемножителя,

один выход, который является выходом последнего каскада конвейера перемножения;

при этом конвейерный перемножитель выполнен с возможностью нумеровать выходные блоки так, что выходному блоку данных присваивается номер соответствующего блока данных, взятого с 1-го входа;

блок обратной связи содержит

1-й и 2-й входы и один выход,

буферный регистр FIFO, в который записываются блоки данных, поступающие на 1-й вход блока обратной связи;

при этом блок обратной связи выполнен с возможностью считывать блоки данных из буферного регистра FIFO на выход лишь при поступлении блоков данных на 2-й вход;

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

получать на вход блоки данных и их номера;

сравнивать номер входящего блока данных со значением L×М;

если номер входящего блока данных больше или равен L×М, то обнулять ячейку памяти накопления;

если номер входящего блока данных меньше L×М, то суммировать входящий блок данных в поле GF (2^k) со значением, содержащемся в ячейке памяти накопления, и записывать результат обратно в ячейку памяти накопления;

при этом вход каждого блока конвейерного вычисления, подключен к 1-му входу сумматора, к входу модуля памяти, 2-му входу модуля отключения обратной связи и 2-му входу блока обратной связи;

при этом 1-й вход конвейерного перемножителя подключен к выходу модуля памяти, а 2-й вход конвейерного перемножителя подключен к выходу сумматора;

при этом выход конвейерного перемножителя подключен ко входу блока накопления и к 1-му входу блока обратной связи, а выход блока обратной связи подключен к 1-му входу модуля отключения обратной связи;

выход модуля отключения обратной связи подключен ко 2-му входу сумматора;

выход блока накопления является выходом блока конвейерного вычисления;

блок объединения содержит М входов и выполнен с возможностью производить сложение блоков данных в поле GF (2^k) от всех М входов и выдавать результат этого сложения на свой выход.

2. Устройство, по п. 1, на вход которого подаются блоки данных, дополнительно содержащие флаг K, причем для блоков данных, принадлежащих первому обрабатываемому кадру данных, флаг K имеет нулевое значение, а для блоков данных всех последующих кадров данных флаг K установлен по следующему правилу:

если хэш-функция для следующего кадра данных должна быть рассчитана на том же значении полинома Н, что и хэш-функция для предыдущего кадра данных, то значение флага K для всех блоков данных следующего кадра данных установлено в то же значение, что и значение флага K для блоков данных предыдущего кадра данных;

иначе, значение флага K для всех блоков данных следующего кадра данных установлено в значение, противоположное значению флага K для блоков данных предыдущего кадра данных;

при этом в устройстве

имеется дополнительный независимый модуль памяти в каждом блоке конвейерного вычисления, подключенный параллельно имеющемуся модулю памяти;

в каждом блоке конвейерного вычисления блоки данных поступают в модуль памяти, если флаг K равен нулю, или в дополнительный модуль памяти, если флаг K равен единице.

3. Устройство по п. 1 или 2, в котором выход блока конвейерного перемножителя имеет возможность подключаться напрямую к 1-му входу модуля отключения обратной связи, минуя блок обратной связи.

4. Способ вычисления хэш-функции для кадра цифровых данных, причем кадр данных состоит из блока данных длиной k бит, заключающийся в том, что

определяют полином Н хэш-функции;

обнуляют содержимое всех буферных регистров FIFO блока предварительной подготовки;

обнуляют ячейку памяти блоков накопления всех блоков конвейерного вычисления;

вычисляют значения степеней полинома Н, вычисленные в поле GF (2^k);

записывают вычисленные значения степеней полинома Н в модули памяти всех блоков конвейерного вычисления, причем в ячейку памяти с номером i записывается Hⁱ⁺¹, причем 0≤i<L×М, а в ячейку с номером L×М записывается Н^LM;

записывают L блоков данных, содержащих нули во всех битах, в блоки обратной связи всех блоков конвейерного вычисления;

обнуляют значение счетчиков в модулях отключения обратной связи всех блоков конвейерного вычисления;

подают одновременно на М входов блока предварительной подготовки очередные М блоков данных кадра данных;

если есть входящие блоки данных, записывают очередные блоки данных в соответствующие М буферные регистры FIFO в блоке предварительной подготовки;

если в каком либо из буферных регистров FIFO есть последний блок данных кадра данных, то

считывают очередные блоки данных из каждого буферного регистра FIFO;

передают их на выход блока предварительной подготовки;

присваивают каждому блоку данных порядковый номер, начиная с нуля и считая с последнего блока данных кадра, находящегося в буферных регистрах FIFO;

иначе, если очереди имеют длину L и не содержат последнего блока данных кадра данных, то

считывают очередные блоки данных из каждого буферного регистра FIFO;

передают их на выход блока предварительной подготовки;

присваивают каждому блоку данных номер L×М;

передают блоки данных с выходов блока предварительной подготовки на входы соответствующих блоков конвейерного вычисления;

передают входящие блоки данных на вход модуля памяти, на 1-й вход сумматора, на 2-й вход модуля отключения обратной связи, на 2-й вход блока обратной связи в каждом блоке конвейерного вычисления;

используют номер входящего блока данных как адрес модуля памяти в модуле памяти, извлекают заранее записанную в память модуля памяти значение степени Н в поле GF (2^k);

подают извлеченное значение на выход модуля памяти;

выполняют в сумматоре следующие действия

суммируют в поле GF(2^k) входящие с 1-го и 2-го входа блоки данных;

присваивают результату сложения номер блока данных со 1-го входа;

передают этот результат на выход сумматора;

передают с выхода модуля памяти блок данных на 1-й вход конвейерного перемножителя;

передают с выхода сумматора очередной блок данных на 2-й вход конвейерного перемножителя;

вычисляют произведение блоков данных в поле GF (2^k) в конвейерном перемножителе, передают его на выход конвейерного перемножителя, при этом присваивают результирующему блоку номер, равный номеру соответствующего входящего блока данных, взятого со 2-го входа конвейерного перемножителя;

передают блок данных с выхода конвейерного перемножителя на вход блока накопления и на 1-й вход блока обратной связи;

если имеется входящий блок данных на 1-м входе блока обратной связи, то записывают его в буферные регистры FIFO блока обратной связи;

если имеется входящий блок данных на 2-м входе блока обратной связи, то

считывают из буферного регистра FIFO блока обратной связи очередной блок данных;

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

передают блок данных с выхода блока обратной связи на 1-й вход модуля отключения обратной связи;

выполняют в модуле отключения обратной связи следующие действия

если на 2-й вход поступает блок данных, увеличивают значение счетчика;

если значение счетчика больше или равно М, передают на выход блок данных с 1-го входа;

если значение счетчика меньше М, передают на выход блок данных, содержащий нули во всех битах;

если номер блока данных, поступившего на 2-й вход меньше М, обнуляют значение счетчика;

передают блоки данных с выхода модуля отключения обратной связи на 2-й вход сумматора;

проверяют наличие данных на входе блока накопления,

если на входе имеется блок данных, то

если его номер меньше L×М, но больше или равен М, то

производят суммирование в поле GF (2^k) входящего блока данных и содержимого ячейки памяти блока накопления;

записывают результат обратно в ячейку памяти накопления;

иначе, если номер входящего блока данных меньше М, то

производят суммирование в поле GF (2^k) входящего блока данных и содержимого ячейки памяти блока накопления;

записывают результат в выход блока накопления;

обнуляют содержимое ячейки памяти блока накопления;

если на входе блока накопления отсутствует блок данных или если имеется блок данных, но его номер равен L×M, то не передают данные на выход блока накопления;

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

передают блоки данных с выхода блоков конвейерного вычисления на входы блока объединения;

проверяют наличие входящих блоков данных в блоке объединения

если на входе отсутствуют блоки данных, то помечают выход блока объединения, как не имеющий данных;

иначе, если на входе имеются блоки данных, то

суммируют в поле GF (2^k) блоки данных со всех входов;

передают результат суммирования, являющийся значением хэш-функции, на выход блока объединения.

5. Способ по п. 4 в котором, при наличии дополнительных модулей памяти в каждом блоке конвейерного вычисления, на этапе передачи входящих блоков данных на вход модуля памяти выполняют следующие действия:

если входящий блок данных помечен флагом K, равным нулю, то

передают входящий блок данных на вход модуля памяти;

вычисляют значения степеней следующего полинома Н в поле GF (2^k) для следующего кадра данных;

записывают вычисленные значения степеней полинома Н для следующего кадра данных, в дополнительный модуль памяти блока конвейерного вычисления, причем в ячейку памяти с номером i записывается Нⁱ⁺¹, причем 0≤i<L×М, а в ячейку с номером L×М записывается Н^LM;

если входящий блок данных помечен флагом K, равным единице, то

передают входящий блок данных на вход дополнительного модуля памяти;

вычисляют значения степеней следующего полинома Н в поле GF (2^k) для следующего кадра данных;

записывают вычисленные значения степеней полинома Н для следующего кадра данных, в модуль памяти блока конвейерного вычисления, причем в ячейку памяти с номером i записывается Нⁱ⁺¹, причем 0≤i<L×М, а в ячейку с номером L×М записывается H^LM.

6. Способ по п. 4 или п. 5, в котором передают блок данных с выхода конвейерного перемножителя на вход блока накопления и на 1-й вход модуля отключения обратной связи вместо 1-го входа блока обратной связи.