Схема цифровой подписи на основе блочного шифра

Ниже приведены числовые параметры и используемые вспомогательные алгоритмы рассматриваемой схемы цифровой подписи:

EK — алгоритм зашифрования с размером блока данных и ключа n и nK битов соответственно;

Гm (s, K) — алгоритм выработки m битов криптостойкой гаммы с использованием n-битового вектора начальных параметров (синхропосылки) s и nK-битового ключа K, представляет собой рекуррентный алгоритм выработки n-битовых блоков данных и их последующего зашифрования по алгоритму EK;

PmnK — набор функций расширения m-битовых блоков данных до nK-битовых для различных m (типично — для кратных n, меньших nK);

L — фактор количества подписей (система рассчитана на N=2L подписей);

nT — число битов в подписываемых битовых группах, тогда число групп равно.

Ниже изложены алгоритмы схемы подписи:

Алгоритм формирования ключей подписи и проверки подписи.

Формирования ключа подписи.

Ключ подписи формируется как nK-битовый блок данных с помощью аппаратного генератора случайных кодов или криптостойкого программного генератора псевдослучайных кодов KS=GnT (…). Биты ключа должны быть независимы и с равной вероятностью принимать оба возможных значения — 0 и 1.

Формирования ключа проверки подписи. Схема алгоритма формирования ключа проверки подписи изображена на рисунке 4.

Исходные данные алгоритма — nK-битовый массив данных KS — ключ подписи.

Вычисляем nG — количество nT-битовых групп в подписываемых блоках.

Следующие шаги 2−9 выполняются столько раз, на сколько подписей рассчитана схема, т. е. для каждого номера подписи системы.

Рис. 4. Алгоритм выработки ключа проверки подписи

Выработать блок гаммы размером 2nnG бит с помощью генератора криптостойкой гаммы на ключе KS с начальным заполнением i (номером подписи) и поместить его в 2nnG-битовый массив X.

2nnG-битовый массив X интерпретируется как массив из 2nG n-битовых элементов Xj, X=(X1,X2,…, X2nG), |Xj|=n,.

затем для каждого элемента этого массива вычисляется результат его «односторонней прокрутки» 2nT-1 раз.

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

Следующие шаги 5,6 выполняются количество раз, равное фактору количества подписей L.

Если l младших бит номера подписи — единицы, переход к шагу 6, иначе — выполнение цикла прекращается и управление передается на шаг 7.

Текущая хэш-комбинация S объединяется c текущей хэш-комбинацией Dl уровня l, и для полученного массива вычисляется хэш-значение, которое становится новой текущей хэш-комбинацией.

Текущая хэш-комбинация S заменяет хэш-комбинацию Dl уровня l.

Последняя вычисленная при выполнении алгоритма текущая хэш-комбинация S и будет являться результатом работы алгоритма — ключом проверки подписи. Кроме того, в ходе выполнения алгоритма будут последовательно выработаны хэш-комбинации всех уровней от 0 до L, 0lL, 0i<2L-l, которые могут храниться в системе и использоваться при формировании подписи.

Алгоритм подписи хэш-блока массива данных.

Схема алгоритма подписи хэш-блока массива данных изображена на рисунке 5.

Исходные данные алгоритма:

T — подписываемый — n-битовый хэш-блок массива данных;

KS — ключ подписи — nK-битовый массив данных;

i — порядковый номер подписи.

Вычисляем nG — число nT-битовых групп в подписываемом n-битном хэш-блоке.

Выработать блок гаммы размером 2nnG бит с помощью генератора криптостойкой гаммы на ключе KS с начальным заполнением i (номером подписи) и поместить его в 2nnG-битовый массив X.

2nnG-битовый массив X интерпретируется как массив из nG пар n-битовых элементов X=((X1,X2),…,(X2nG-1,X2nG)), |Xj|=n,.

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

Рис. 5. Алгоритм подписи хэш-кода сообщения

К индивидуальной проверочной комбинации последовательно добавляется попарные хэш-комбинации, по одной комбинации с каждого уровня от 0 до L-1, которые необходимы при вычислении проверочной комбинации самого верхнего уровня (L), общей для всех сообщений. Номер добавляемой комбинации каждого уровня определяется отбрасыванием количества последних бит в номере подписи, равного номеру уровня, и в инвертировании младшего бита полученного числа.

В результате получаем цифровую подпись хэш-блока сообщения S=(X, D), состоящую из массива подписей битовых групп блока X=(X1,X2,…, X2nG) и из массива дополнительных проверочных комбинаций D=(D0,D1,…, DL-1), необходимых для выполнения процедуры проверки подписи и используемых при вычислении попарных проверочных комбинаций.

Алгоритм проверки подписи хэш-блока массива данных.

Схема алгоритма проверки подписи хэш-блока массива данных изображена на рисунке 6.

Рис. 6. Алгоритм проверки подписи

Исходные данные алгоритма:

T — подписанный — n-битовый хэш-блок массива данных;

s — подпись хэш-блока, состоит из массива X, содержащего 2nG n-битовых элементов подписи битовых групп, и массива D, содержащего L n-битовых хэш-комбинаций;

i — порядковый номер подписи.

Вычисляем nG — число nT-битовых групп в подписываемом хэш-блоке, имеющем размер n бит.

В соответствии с правилами проверки подписи производится «односторонняя прокрутка» элементов подписи битовых групп, содержащихся в массиве X, по два элемента на каждую группу.

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

Следующие шаги 4−6 выполняются количество раз, равное фактору количества подписей L.

Производится выбор по значению l-того бита (нумерация с 0 со стороны младшего бита) номера подписи.

Если значение бита равно 0, то к коду справа добавляется очередная хэш-комбинация, содержащаяся в подписи, для полученного блока вычисляется хэш-функция, которая замещает предыдущее содержимое S.

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

В конце выполнения алгоритма в S содержится код, который должен быть сравнен с ключом проверки подписи, если коды одинаковы, подпись считается верной, иначе — неверной.