Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
METHOD AND DEVICE FOR CALCULATING A HASH FUNCTION
Document Type and Number:
WIPO Patent Application WO/2019/117758
Kind Code:
A1
Abstract:
The group of inventions relates to computer technology and can be used for calculating a hash function. The technical result is an increase in the rapidity of calculations and an extension for the possibility of selecting the configuration of a device. The device comprises a preliminary preparation unit having M inputs having a size of k bits, wherein M>1; M pipeline computation units operating in parallel, each of which comprises a memory module, a module for disconnecting a feedback link, a register, a pipeline multiplier having L cascades, a feedback link unit and a storage unit; and a connection unit.

Inventors:
KALISTRU, Ilia Ivanovich (house 29, fl. 141 60-th Army stree, Voronezh 7, 394077, RU)
Application Number:
RU2018/050130
Publication Date:
June 20, 2019
Filing Date:
October 23, 2018
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
JOINT STOCK COMPANY "INFOTECS" (1/23, Building 1 Stariy Petrovsko-Razumovskiy proez, Moscow 7, 127287, RU)
International Classes:
H04L9/06; G06F17/10
Foreign References:
US7970130B22011-06-28
US20100115017A12010-05-06
US20090080646A12009-03-26
US20070081668A12007-04-12
Attorney, Agent or Firm:
LAW FIRM "GORODISSKY & PARTNERS" LTD. (25 bldg.3, B. Spasskaya Str.Moscow, 129090, RU)
Download PDF:
Claims:
Формула изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сумматор,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

вычисляют значения степеней полинома H , вычисленные в поле GF ( 2 к ) ; записывают вычисленные значения степеней полинома H в модули памяти всех блоков конвейерного вычисления, причем в ячейку памяти с номером i записы- вается H 1 + причем 0 < i < L *М, а в ячейку с номером L х записывается Н LM записывают L блоков данных, содержащих нули во всех битах, в блоки обратной связи всех блоков конвейерного вычисления;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

записывают вычисленные значения степеней полинома H для следу- ющего кадра данных, в дополнительный модуль памяти блока кон- вейерного вычисления, причем в ячейку памяти с номером i записы- вается H l + l, причем 0 < i < Z* , а в ячейку с номером х записы- т т LM

вается Н ;

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

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

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

записывают вычисленные значения степеней полинома H для следу- ющего кадра данных, в модуль памяти блока конвейерного вычисле- ния, причем в ячейку памяти с номером i записывается H l + l, причем

0 < i < Zx , а в ячейку с номером LxM записывается Н LM .

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

Description:
СПОСОБ И УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ХЭШ-ФУНКЦИИ

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

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

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

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

Данная функция определяется как

GHASH (S', Н ) = X t ,

где S - данные кадра данных,

H - полином хэш-функции, являющийся ключом данной хэш-функции,

I - количество блоков данных в S,

Г 0 , при i = О

X . =

( X Q S ( ) Н , при i < I

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

Так, известны способ и устройство вычисления хэш-функции для режима Galois Counter Mode (GCM; патент США N° 7970130, приоритет от 21.09.2007 г.), причем в спо- собе для входных данных, включающих ассоциированные данные А, шифротекст С, по- лином Н, вычисляют сначала промежуточное значение

затем промежуточное значение а также значения Н n +l , после чего вычисляется величина

Х А Н п +х ® Х с

являющаяся искомым значением функции GHASH.

У стройство, осуществляющее вычисления, состоит из первого, второго и третьего вычислительных модулей, вычисляющих значения И Н п + соответственно, а также четвертого вычислительного модуля, вычисляющего значение X A H h +i Q X с . Это устройство позволяет вычислить значение GHASH(A, С, Н ) за max ( , п) + \ циклов, где т - количество блоков данных в А, а п - количество блоков данных в С, при этом I = т + п + 1 - это количество блоков, подаваемых на вход функции GHASH.

Известные способ и устройство приняты за прототипы.

Недостатками известных устройства и способа являются невысокое быстродей- ствие и отсутствие возможности выбора конфигурации устройства перед его изготовле- нием. Так, наилучшего быстродействия в известном устройстве и способе удается до- биться, если т = п. В этом случае удается получить ускорение в 2 раза по сравнению с последовательным вычислением.

Раскрытие изобретения

Техническим результатом является

1) повышение быстродействия вычислений,

2) расширение возможности выбора конфигурации устройства.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• сумматор,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• вычисляют значения степеней полинома H, вычисленные в поле GF ( 2 к ) ;

• записывают вычисленные значения степеней полинома H в модули памяти всех блоков конвейерного вычисления, причем в ячейку памяти с номером i записы- вается H 1 + причем 0 < i < L х , а в ячейку с номером L х записывается Н LM

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• если на входе блока накопления отсутствует блок данных или если имеется блок данных, но его номер равен LxM, то не передают данные на выход блока накоп- ления;

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

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

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

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

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

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

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

Следует обратить внимание на то, что выражение для GHASH ( S, Н) = X 1 можно переписать в следующем виде

Учитывая линейность производимых операций, можно раскрыть скобки и собрать М групп членов, сгруппировав по j все члены содержащие S iM + j , причем 0 <j < M. При этом М может быть любым положительным натуральным числом. Применив правило Г орнера к каждой из групп отдельно, получим x l = m-) H M ® S t - 2M ) H M ® S t - M ) H M ® S t ) H l

Если правильным образом сгруппировать входящие данные, то можно вычислять М слагаемых (частичных сумм) данного выражения независимо друг от друга, при этом умножать нужно не на Я, а на Н м , а последний раз в каждом выражении нужно умно- жать на значения различных степеней Н в зависимости от номера блока данных, который был прибавлен перед умножением - после прибавления последнего блока данных нужно умножать на Н , после прибавления предпоследнего блока данных - Н и т.д.

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

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

Использование М блоков конвейерной обработки, работающих параллельно, поз- воляет повысить быстродействие предлагаемого устройства в М раз.

Еше одним методом повышения быстродействия предлагаемого устройства явля- ется повышение тактовой частоты работы устройства в L раз за счет применения конвей- ерного перемножителя, содержащего L каскадов перемножения.

Поскольку сложение в поле Г алуа является простейшим побитовым исключающим “или”, требует немного ресурсов и быстро выполняется, то основным ограничением на повышение тактовой частоты является перемножитель. Таким образом, если разбить вы- числение произведения на несколько каскадов конвейера, тем самым уменьшив длину критических путей распространения сигнала, то можно значительно повысить рабочую тактовую частоту устройства.

Разбиение процедуры перемножения на несколько частей не представляет большой сложности - при перемножении“в столбик” можно разбить суммирование результатов по- разрядного перемножения на несколько частей, а при перемножении рекурсивным мето- дом Карацубы, можно, например, завершать очередной каскад конвейера после выполне- ния сложений алгоритма для более мелких блоков алгоритма и перед началом сложения более крупных. Можно применять и другие разбиения и алгоритмы.

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

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

тактов (округление вверх до ближайшего целого значения), каждый из который в L раз короче.

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

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

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

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

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

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

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

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

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

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

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

о передают входящий блок данных на на вход модуля памяти, о вычисляют значения степеней следующего полинома H в поле GF ( 2 к ) для следующего кадра данных о записывают вычисленные значения степеней полинома H для следую- щего кадра данных, в дополнительный модуль памяти блока конвейер- ного вычисления, причем в ячейку памяти с номером i записывается H 1 + причем 0 < i < L*M, а в ячейку с номером L*M записывается Н LM ;

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

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

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

о записывают вычисленные значения степеней полинома H для следую- щего кадра данных, в модуль памяти блока конвейерного вычисления, причем в ячейку памяти с номером i записывают Н 1 +1 , причем 0 < i <

L*M, а в ячейку с номером L*M записывают Н LM .

Описанный частный случай выполнения способа позволяет повысить быстродей- ствие устройства в случае, когда от устройства требуется обработка кадров данных с ис- пользованием различных полиномов хэш-функции H. Блоки данных кадров данных, по- ступают на вход устройства и содержат флаг К, заранее установленный в соответствии с учетом того, для какого полинома хэш-функции H требуется обработать данный кадр. В то время, когда кадры данных обрабатываются с одним полиномом хэш-функции H , ис- пользуется один из модулей памяти, а в другой модуль памяти загружают значения степе- ней полинома H для следующего кадра данных. Это позволяет не останавливать устрой- ство для смены полинома хэш-функции H.

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

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

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

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

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

Краткое описание чертежей

На фиг. 1 показана блок-схема устройства.

На фиг. 2 показана блок-схема блока конвейерного вычисления.

Осуществление изобретения

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

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

Количество каскадов в конвейерных перемножителях L выбирают достаточным для того, что бы максимальная частота работы конвейерного перемножителя достигла макси- мальной тактовой частоты F mSX для других компонентов схемы.

Количество блоков конвейерного вычисления М выбирают достаточным, для до- стижения требуемого быстродействия, исходя из следующей формулы

Р = ^ nax М , бит/с

Если М - 1 блоков конвейерного вычисления недостаточно для достижения требуе- мого быстродействия, а М блоков конвейерного вычисления обеспечивают быстродей- ствие, превышающее требуемое, то для снижения энергопотребления выбирают частоту работу устройства по формуле

F = Р/ ( к -М )

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

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

Реализовать предложенное устройство в виде блока интегральной схемы или в виде блока устройства для обеспечения аутентичности данных, выполненного на базе програм- мируемой логической интегральной схемы (ПЛИС) или базового матричного кристалла может специалист в области проектирования цифровых интегральных схем.

Для реализации предложенного способа изготавливают устройство согласно опи- санию. Затем определяют битовое представление значения полинома H, являющегося ключом хэш-функции и значение которого должно храниться в секрете. Например, 128 бит битового представления значения полинома H может быть получено из генератора случайных чисел. В зависимости, от применяемого алгоритма, значение H может опреде- ляться и другими способами.

После этого обнуляют содержимое всех буферных регистров FIFO блока предвари- тельной подготовки, вычисляют в поле GF ( 2 к ) значения степеней полинома H вплоть до Н и n1 , записывают их битовые представления в модули памяти всех блоков конвейер- ного вычисления, причем в ячейку памяти с номером i записывается H 1 + причем 0 < ί <

LxM, а в ячейку с номером L*M записывают Н LM , записывают L блоков данных, содер- жащих нули во всех битах, в блоки обратной связи всех блоков конвейерного вычисления, обнуляют значение счетчиков в модулях отключения обратной связи всех блоков конвей- ерного вычисления.

После этого приступают к обработке кадров данных. Для этого разделяют кадры данных на блоки по к бит, причем последний блок снабжен метаинформацией о том, что это последний блок кадра данных. Подают одновременно по М очередных блоков данных на M входов блока предварительной подготовки. В блоке предварительной подготовки ну- меруют блоки данных (снабжают метаинформацией). Затем передают блоки данных с вы- ходов блока предварительной подготовки на входы соответствующих М блоков конвейер- ного вычисления. В каждом блоке конвейерного вычисления, используя хранящиеся в мо- дулях памяти значения степеней H , вычисляют L частичных сумм и суммируют их в блоке накопления блока конвейерного вычисления.

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

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

Наличие двух модулей памяти в каждом блоке конвейерного вычисления позволяет загружать значения степеней H для нового ключа в один из модулей памяти, без остановки работы устройства, пока происходит обработка данных с использованием степеней H для старого ключа, хранящихся в другом модуле памяти. При этом на вход устройства пода- ются блоки данных, дополнительно содержащие флаг К, причем для блоков данных, при- надлежащих первому обрабатываемому кадру данных, флаг К имеет нулевое значение, а для блоков данных всех последующих кадров данных флаг К установлен по следующему правилу:

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

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

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

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

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

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

о записывают вычисленные значения степеней полинома H для следующего кадра данных, в дополнительный модуль памяти блока конвейерного вычис- ления, причем в ячейку памяти с номером i записывается H l + l , причем 0 < i

< Zx , а в ячейку с номером LxM записывается Н LM ;

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

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

о записывают вычисленные значения степеней полинома H для следующего кадра данных, в модуль памяти блока конвейерного вычисления, причем в ячейку памяти с номером i записывается Н 1 + причем 0 < i < L х а в ячейку с номером JxM записывается Н LM ;

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

Данный частный случай возможно осуществить, например, с использованием элек- тронных ключей, отключающих выход конвейерного перемножителя от блока обратной связи и подключающих к 1-му входу модуля отключения обратной связи. При этом возни- кает возможность для экономии электроэнергии отключить питание блока обратной связи, когда выход конвейерного перемножителя подключен напрямую к 1 -му входу модуля от- ключения обратной связи. Если же заранее известно, что блоки данных кадра данных подаются на вход устройства на каждый такт без промежутков до конца каждого кадра, то возможно осу- ществление данного частного случая реализации устройства вообще без изготовления блока обратной связи. В этом случае выход конвейерного перемножителя подключают напрямую к Ему входу модуля отключения обратной связи. Такое исполнение позволяет экономить электроэнергию и аппаратные ресурсы, например, место на кристалле микро- схемы, на которой реализовано устройство.

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