Проблема аутентификации данных и блочные шифры (стр. 8 из 9)
Дополнительные контрольные комбинации, которые передаются вместе с подписью и используются при ее проверке, вырабатываются при формировании ключа проверки по ключу подписи и могут храниться в системе и использоваться в момент формирования подписи, либо вычисляться заново в этот момент. Первый подход предполагает затраты дисковой памяти, так как необходимо хранить 2L+1–2 хэш-комбинаций всех уровней, а второй требует большого объема вычислений в момент формирования подписи. Можно использовать и компромиссный подход – хранить все хэш-комбинации начиная с некоторого уровня l*, а комбинации меньшего уровня вычислять при формировании подписи. В рассмотренной выше схеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций, используемых при проверки (всего их 15, но самая верхняя не используется), тогда при проверке подписи их не надо будет вычислять заново. Можно хранить 6 комбинаций начиная с уровня 1 (C0(1), C1(1), C2(1), C3(1), C0(2), C1(2)), тогда при проверке подписи сообщения №5 необходимо будет заново вычислить комбинацию C4(0), а остальные (C0(2),C3(1)) взять из «хранилища», и т.д.. Указанный подход позволяет достичь компромисса между быстродействием и требованиям к занимаемому количеству дискового пространства. Надо отметить, что отказ от хранения комбинаций одного уровня приводит к экономии памяти и росту вычислительных затрат примерно вдвое, то есть зависимость носит экспоненциальный характер.
3.4.Схема цифровой подписи на основе блочного шифра.
Ниже приведены числовые параметры и используемые вспомогательные алгоритмы рассматриваемой схемы цифровой подписи:
· EK – алгоритм зашифрования с размером блока данных и ключа n и nKбитов соответственно;
· Гm(s,K) – алгоритм выработки mбитов криптостойкой гаммы с использованием n-битового вектора начальных параметров (синхропосылки) s и nK–битового ключа K, представляет собой рекуррентный алгоритм выработки n-битовых блоков данных и их последующего зашифрования по алгоритму EK;
· Pm®nK – набор функций расширения m-битовых блоков данных до nK-битовых для различных m (типично – для кратных n, меньших nK);
· L – фактор количества подписей (система рассчитана на N=2L подписей);
· nT – число битов в подписываемых битовых группах, тогда число групп равно
.Ниже изложены алгоритмы схемы подписи:
1.Алгоритм формирования ключей подписи и проверки подписи.
a)Формирования ключа подписи.
Ключ подписи формируется как nK-битовый блок данных с помощью аппаратного генератора случайных кодов или криптостойкого программного генератора псевдослучайных кодов KS=GnT(...). Биты ключа должны быть независимы и с равной вероятностью принимать оба возможных значения – 0 и 1.
b)Формирования ключа проверки подписи. Схема алгоритма формирования ключа проверки подписи изображена на рисунке 4.
Øàã0.Исходные данные алгоритма – nK–битовый массив данных KS – ключ подписи.
Øàã1.Вычисляем nG – количество nT-битовых групп в подписываемых блоках.
Следующие шаги 2–9 выполняются столько раз, на сколько подписей рассчитана схема, т.е. для каждого номера подписи системы.
Øàã2.
Выработать блок гаммы размером 2nnG бит с помощью генератора криптостойкой гаммы на ключе KSс начальным заполнением i(номером подписи) и поместить его в 2nnG–битовый массив X.Øàã3.2nnG–битовый массив X интерпретируется как массив из 2nGn-битовых элементов Xj, X=(X1,X2,...,X2nG), |Xj|=n,
затем для каждого элемента этого массива вычисляется результат его «односторонней прокрутки» 2nT–1 раз.
Øàã4.Для массива X вычисляется и записывается в блок данных Sего хэш-код, который является индивидуальной проверочной комбинацией для подписи номер i.
Следующие шаги 5,6 выполняются количество раз, равное фактору количества подписей L.
Øàã5.Если lмладших бит номера подписи – единицы, переход к шагу 6, иначе – выполнение цикла прекращается и управление передается на шаг 7.
Øàã6.Текущая хэш-комбинация S объединяется c текущей хэш-комбинацией Dl уровня l, и для полученного массива вычисляется хэш–значение, которое становится новой текущей хэш–комбинацией.
Øàã7.Текущая хэш-комбинация S заменяет хэш-комбинацию Dl уровня l.
Øàã8.Последняя вычисленная при выполнении алгоритма текущая хэш-комбинация S и будет являться результатом работы алгоритма – ключом проверки подписи. Кроме того, в ходе выполнения алгоритма будут последовательно выработаны хэш-комбинации всех уровней от 0 до L
, 0£l£L, 0£i<2L–l, которые могут храниться в системе и использоваться при формировании подписи.2.Алгоритм подписи хэш-блока массива данных.
Схема алгоритма подписи хэш-блока массива данных изображена на рисунке 5.
Øàã0.Исходные данные алгоритма:
· T– подписываемый – n-битовый хэш-блок массива данных;
· KS – ключ подписи – nK-битовый массив данных;
· i – порядковый номер подписи.
Øàã1.Вычисляем nG – число nT-битовых групп в подписываемом n-битном хэш-блоке.
Øàã2.Выработать блок гаммы размером 2nnG бит с помощью генератора криптостойкой гаммы на ключе KSс начальным заполнением i(номером подписи) и поместить его в 2nnG-битовый массив X.
Øàã3.2nnG-битовый массив X интерпретируется как массив из nGпар n-битовых элементов X=((X1,X2),...,(X2nG–1,X2nG)), |Xj|=n,
затем для каждой составляющей каждого элемента этого массива, соответствующего определенной битовой группе хэш-блока, нужное число раз выполняется процедура «односторонней прокрутки».
Øàã4.
К индивидуальной проверочной комбинации последовательно добавляется попарные хэш-комбинации, по одной комбинации с каждого уровня от 0 до L–1, которые необходимы при вычислении проверочной комбинации самого верхнего уровня (L), общей для всех сообщений. Номер добавляемой комбинации каждого уровня определяется отбрасыванием количества последних бит в номере подписи, равного номеру уровня, и в инвертировании младшего бита полученного числа.Øàã5.В результате получаем цифровую подпись хэш-блока сообщения S=(X,D), состоящую из массива подписей битовых групп блока X=(X1,X2,...,X2nG) и из массива дополнительных проверочных комбинаций D=(D0,D1,...,DL–1), необходимых для выполнения процедуры проверки подписи и используемых при вычислении попарных проверочных комбинаций.
3.Алгоритм проверки подписи хэш-блока массива данных.
Схема алгоритма проверки подписи хэш-блока массива данных изображена на рисунке 6.
Øàã0.
Исходные данные алгоритма:· T– подписанный – n-битовый хэш-блок массива данных;
· s – подпись хэш–блока, состоит из массива X, содержащего 2nGn-битовых элементов подписи битовых групп, и массива D, содержащего Ln-битовых хэш–комбинаций;
· i – порядковый номер подписи.
Øàã1.Вычисляем nG – число nT–битовых групп в подписываемом хэш–блоке, имеющем размер nбит.
Øàã2.В соответствии с правилами проверки подписи производится «односторонняя прокрутка» элементов подписи битовых групп, содержащихся в массиве X, по два элемента на каждую группу.
Øàã3.Для массива X вычисляется и записывается в Sего хэш-код, который должен быть равен индивидуальной проверочной комбинацией для i-той подписи.
Следующие шаги 4–6 выполняются количество раз, равное фактору количества подписей L.
Øàã4.Производится выбор по значению l-того бита (нумерация с 0 со стороны младшего бита) номера подписи.
Øàã5.Если значение бита равно 0, то к коду справа добавляется очередная хэш-комбинация, содержащаяся в подписи, для полученного блока вычисляется хэш-функция, которая замещает предыдущее содержимое S.
Øàã6.Если значение бита равно 1, то выполняется то же самое, только хэш-комбинация добавляется к коду слева.
Øàã7.В конце выполнения алгоритма в S содержится код, который должен быть сравнен с ключом проверки подписи, если коды одинаковы, подпись считается верной, иначе – неверной.