Проблема аутентификации данных и блочные шифры

Алгоритм S выработки цифровой подписи для бита t (t {0,1}) заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи:

s=S(t)=K_t.

Алгоритм V проверки подписи состоит в проверке уравнения E_Kt(X_t)=C_t, которое, очевидно, должно выполняться для нашего t. Получателю известны все используемые величины:

K_t=s - цифровая подпись бита,

C_t - соответствующая половина ключа проверки,

X_t - несекретный параметр алгоритма.

Таким образом, функция проверки подписи будет следующей:

.

Не правда ли, все три алгоритма этой схемы изумительно простоты в сравнении со схемами RSA и эль-Гамаля?! Покажем, что данная схема работоспособна, для чего проверим выполнение необходимых свойств схемы цифровой подписи:

Невозможность подписать бит t, если неизвестен ключ подписи.

Действительно, для выполнения этого злоумышленнику потребовалось бы решить уравнение E_s(X_t)=C_t относительно s, эта задача эквивалентна определению ключа для известных блока шифротекста и соответствующего ему открытого текста, что вычислительно невозможно в силу использования стойкого шифра.

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

E_s(X₀)=C₀,

E_s(X₁)=C₁.

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

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

размер ключа подписи:

n_S=n_H2n_K=2n_Hn_K.

размер ключа проверки подписи:

n_С=n_H2n=2n_Hn.

размер подписи:

n_Sg=n_Hn_K=n_Hn_K.

Если, например, в качестве основы в данной схеме будет использован шифр ГОСТ 28147-89 с размером блока n=64 бита и размером ключа n_K=256 бит, и для выработки хэш-блоков будет использован тот же самый шифр в режиме выработки MDC, что даст размер хэш-блока n_H=64 то размеры рабочих блоков будут следующими:

размер ключа подписи:

n_S=n_H2n_K=2n_Hn_K=264256=2¹⁵ бит = 4096 байт.

размер ключа проверки подписи:

n_С=n_H2n=2n_Hn=26464=2¹³ бит = 1024 байта.

размер подписи:

n_Sg=n_Hn_K=n_Hn_K=64256=2¹⁴ бит = 2048 байт.

Согласитесь, довольно тяжелые ключики.

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

В силу указанных двух недостатков предложенная схемы до сравнительно недавнего времени рассматривалась лишь как курьезная теоретическая возможность, никто всерьез не рассматривал возможность ее практического использования. Однако несколько лет назад в работе [7] была предложена модификация схемы Диффи-Хеллмана, фактически устраняющая ее недостатки. В настоящей работе данная схема не рассматривается во всех деталях, здесь изложены только основные принципы подхода к модификации исходной схемы Диффи-Хеллмана и описания работающих алгоритмов.

3.3 Модификация схемы Диффи-Хеллмана для подписи битовых групп

В данном разделе изложены идеи авторов [7], позволившие перейти от подписи отдельных битов в исходной схемы Диффи-Хеллмана к подписи битовых групп. Центральным в этом подходе является алгоритм «односторонней криптографической прокрутки», который в некотором роде может служить аналогом операции возведения в степень. Как обычно, предположим, что в нашем распоряжении имеется криптографический алгоритм E_K с размером блока данных и ключа соответственно n и n_K битов, причем размер блока данных не превышает размера ключа: nn_K. Пусть в нашем распоряжении также имеется некоторая функция «расширения» n-битовых блоков данных в n_K-битовые Y=P_nnK(X), |X|=n, |Y|=n_K. Определим функцию R_k «односторонней прокрутки» блока данных T размером n бит k раз (k0) с помощью следующей рекурсивной формулы:

где X - произвольный несекретный n-битовый блок данных, являющийся параметром процедуры прокрутки. По своей идее функция односторонней прокрутки чрезвычайно проста, надо всего лишь нужное количество раз (k) выполнить следующие действия: расширить n-битовый блок данных T до размера ключа использованного криптоалгоритма (n_K), на полученном расширенном блоке как на ключе зашифровать блок данных X, результат зашифрования занести на место исходного блока данных (T). В силу определения операция R_k(T) обладает двумя крайне важными для нас свойствами:

Аддитивность по числу прокручиваний:

R_k+k'(T)=R_k'(R_k(T)).

Односторонность или необратимость прокрутки: если известно только некоторое значение функции R_k(T), то вычислительно невозможно найти значение R_k'(T) для любого k'<k - если бы это было возможно, в нашем распоряжении был бы способ определить ключ шифрования по известному входному и выходному блоку криптоалгоритма E_K. что противоречит предположению о стойкости шифра.

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

секретный ключ подписи K_S выбирается как произвольная пара блоков K₀, K₁, имеющих размер блока данных используемого блочного шифра:

K_S=(K₀,K₁);

Таким образом, размер ключа подписи равен удвоенному размеру блока данных использованного блочного шифра:

|K_S|=2n;

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

K_C=(C₀,C₁), где:

C₀=R_2nT-1(K₀), C₁=R_2nT-1(K₁).

В этих вычислениях также используются несекретные блоки данных X₀ и X₁, являющиеся параметрами функции «односторонней прокрутки», они обязательно должны быть различными.

Таким образом, размер ключа проверки подписи равен удвоенному размеру блока данных использованного блочного шифра:

|K_C|=2n.

Алгоритмы модифицированной авторами [7] схемы цифровой подписи Диффи и Хеллмана следующие:

1. Алгоритм G выработки ключевой пары:

Берем случайный блок данных подходящего размера 2n, это и будет секретный ключ подписи:

K_S=(K₀,K₁)=R.

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

K_C=(C₀,C₁)=(R_2nT-1(K₀), R_2nT-1(K₁)).

2. Алгоритм S_nT выработки цифровой подписи для n_T-битового блока T, ограниченного, по своему значению, условием 0T2^nT-1, заключается в выполнении «односторонней прокрутки» обеих половин ключа подписи T и 2^nT-1-T раз соответственно:

s=S_nT(T)=(s₀,s₁)=(R_T(K₀), R_2nT-1-T(K₁)).

3. Алгоритм V_nT проверки подписи состоит в проверке истинности соотношений:

R_2nT-_1-T(s₀)=C₀, R_T(s₁)=C₁, которые, очевидно, должны выполняться для подлинного блока данных T:

R_2nT-1-T(s₀)=R_2nT-1-T(R_T(K₀))=R_2nT-1-T+T(K₀)=R_2nT-1(K₀)=C₀,

R_T(s₁)=R_T(R_2nT-1-T(K₁))=R_T+2nT-1-T(K₁)=R_2nT-1(K₁)=C₁.

Таким образом, функция проверки подписи будет следующей:

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

Предположим, что в распоряжении злоумышленника есть n_T-битовый блок T, его подпись s=(s₀,s₁), и ключ проверки K_C=(C₀,C₁). Пользуясь этой информацией, злоумышленник пытается найти правильную подпись s'=(s'₀,s'₁) для другого n_T-битового блока T'. Для этого ему надо решить следующие уравнения относительно s'₀ и s'₁:

R_2nT-1-T'(s'₀)=C₀,

R_T'(s'₁)=C₁.

В распоряжении злоумышленника есть блок данных T с подписью s=(s₀,s₁), и это позволяет ему вычислить одно из значений s'₀,s'₁, даже не владея ключом подписи:

если T<T', то s'₀=R_T'(K₀)=R_T'-_T(R_T(K₀))=R_T'-_T(s₀),

если T>T', то s'₁=R_2nT-1-T'(K₁)=R_T-_T'(R_2nT-1-T(K₁))=R_T-_T'(s₁).

Однако для нахождения второй половины подписи (s'₁ в случае (a) и s'₀ в случае (b)) ему необходимо выполнить прокрутку в обратную сторону, т.е. найти R_k(X), располагая только значением для большего k: R_k'(X), k'>k, что является вычислительно невозможным. Таким образом, злоумышленник не может подделать подпись под сообщением, если не располагает секретным ключом подписи.

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

s=S_nT(T)=(s₀,s₁)=(R_T(K₀), R_2nT-1-T(K₁)),

s'=S_nT(T')=(s'₀,s'₁)=(R_T'(K₀), R_2nT-1-T'(K₁)),

s=s', следовательно:

R_T(K₀)=R_T'(K₀) & R_2nT-1-T(K₁)=R_2nT-1-T'(K₁).

Положим для определенности TT', тогда справедливо следующее:

R_T'-T(K₀^*)=K₀^*,R_T'-T(K₁^*)=K₁^*,где K₀^*=R_T(K₀), K₁^*=R_2nT-_1-T'(K₁)

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

Таким образом рассмотренная модификация схемы Диффи-Хеллмана делает возможным подпись не одного бита, а целой битовой группы. Это позволяет в несколько раз уменьшить размер подписи и ключей подписи/проверки данной схемы. Однако надо понимать, что увеличение размера подписываемых битовых групп приводит к экспоненциальному росту объема необходимых вычислений и начиная с некоторого значения делает работу схемы недопустимо неэффективной. Граница «разумного размера» подписываемой группы находится где-то рядом с восемью битами, и блоки большего размера все равно необходимо подписывать «по частям».

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

бит,

где x обозначает округление числа x до ближайшего целого в сторону возрастания. Число операций шифрования E_K(X), требуемое для реализации процедур схемы, определяются нижеследующими соотношениями:

при выработке ключевой информации оно равно:

,

при подписи и проверке подписи оно вдвое меньше:

.

В следующей ниже таблице 2 приведены рассчитанные значения размеров ключей и подписи, и числа требуемых операций шифрования в зависимости от размера подписываемых битовых групп при условии использования блочного криптоалгоритма с размером блока n=64 бита:

Таблица 2. Числовые показатели схемы подписи в зависимости от размера битовых групп.

nT	Число бит.	Размер подписи и ключей, байт	Число операций шифрования
	групп	|KS|=|KC|=|s|	WK	WS=WC
	64	1024	128	64
	32	512	192	96
	22	352	308	154
	16	256	480	240
	13	208	806	403
	11	176	1386	693
	10	160	2540	1270
	8	128	4080	2040
	8	128	8176	4088
	7	112	14322	7161
	6	96	24564	12282
	6	96	49140	24570
	5	80	81910	40955
	5	80	163830	81915
	5	80	327670	163835
	4	64	524280	262140

Размер ключа подписи и проверки подписи можно дополнительно уменьшить следующими приемами:

Нет необходимости хранить ключи подписи отдельных битовых групп, их можно динамически вырабатывать в нужный момент времени с помощью генератора криптостойкой гаммы. Ключом подписи в этом случае будет являться обычный ключ использованного в схеме подписи блочного шифра. Для ГОСТа 28147-89 этот размер равен 256 битам, поэтому если схема подписи будет построена на ГОСТе, размер ключа подписи будет равен тем же 256 битам.

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

Таким образом, проблема размера ключей и подписи полностью решена, однако, главный недостаток схемы - одноразовость ключей - не преодолен, поскольку это невозможно в рамках подхода Диффи-Хеллмана. Для практического использования такой схемы, рассчитанной на подпись N сообщений, отправителю необходимо хранить N ключей подписи, а получателю - N ключей проверки, что достаточно неудобно. Однако эта проблема может быть решена в точности так же, как была решена проблема ключей для множественных битовых групп - генерацией ключей подписи для всех N сообщений из одного мастер-ключа и свертывание всех проверочных комбинаций в одну контрольную комбинацию с помощью алгоритма выработки хэш-кода. Такой подход решил бы проблему размера хранимых ключей, однако привел бы к необходимости вместе подписью каждого сообщения высылать недостающие N-1 проверочных комбинаций, необходимых для вычисления хэш-кода от массива всех контрольных комбинаций отдельных сообщений. Ясно, что такой вариант не обладает преимуществами по сравнению с исходным. Однако в [7] был предложен механизм, позволяющий значительно снизить остроту проблемы. Его основная идея - вычислять контрольную комбинацию (ключ проверки подписи) не как хэш от линейного массива проверочных комбинаций всех сообщений, а попарно - с помощью бинарного дерева. На каждом уровне проверочная комбинация вычисляется как хэш от двух проверочных комбинаций младшего уровня. Чем выше уровень комбинации, тем больше отдельных ключей проверки в ней «учтено». Предположим, что наша схема рассчитана на 2^L сообщений. Обозначим через C_i^(l) i-тую комбинацию l-того уровня. Если нумерацию комбинаций и уровней начинать с нуля, то справедливо следующее условие: 0i<2^L-^l, а i-тая проверочная комбинация l-того уровня рассчитана на 2^l сообщений с номерами от i2^l до (i+1)2^l-1 включительно. Число комбинаций нижнего, нулевого уровня равно 2^L, а самого верхнего, L-того уровня - одна, она и является контрольной комбинацией всех 2^L сообщений, на которые рассчитана схема. На каждом уровне, начиная с первого, проверочные комбинации рассчитываются по следующей формуле:

C_i^(l+1)=H(C₂⁽_i^l)||C₂⁽_i^l)₊₁),

где через A||B обозначен результат конкатенации двух блоков данных - A и B, а через H(X) - процедура вычисления хэш-кода блока данных X.

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

Схема попарного хеширова-ния проверочных комбинаций при выработке общего ключа проверки подписи на восемь сообщений при-ведена на рисунке 3. Так, в схеме на 8 сообщений при передаче сообще-ния №5 (контрольная комбинация выделена рамкой) вместе с его под-писью должны быть переданы кон-трольная комбинация сообщения №4 (C₄⁽⁰⁾), общая для сообщений №№6-7 (C₃⁽¹⁾) и общая для сообще-ний №№0-3 (C₀⁽²⁾), все они выделе-ны на рисунке другим фоном. При проверке подписи значение C₅⁽⁰⁾ будет вычислено из сообщения и его подписи, а итоговая контрольная комбинация, подлежащая сравнению с эталонной, по следующей формуле:

C=C₀⁽³⁾=H(C₀⁽²⁾||H(H(C₄⁽⁰⁾||C₅⁽⁰⁾)||C₃⁽¹⁾)).

Номера контрольных комбинаций каждого уровня, которые должны быть переданы вместе с подписью сообщения с номером i (0i<2^L), вычисляются по следующей формуле: C ⁽_i^l_/⁾_2l1, l=0,...,L-1, где x1 означает число, получающееся в результате инвертирования младшего бита в числе x.

Необходимость отправлять вместе с подписью сообщения дополнительную информацию, нужную для проверки подписи, на самом деле не очень обременительна. Действительно, в системе на 1024=2¹⁰ подписей вместе с сообщением и его подписью необходимо дополнительно передавать 10 контрольных комбинаций, а в системе на 1048576=2²⁰ подписей - всего 20 комбинаций. Однако при большом числе подписей, на которые рассчитана система, возникает другая проблема - хранение дополнительных комбинаций, если они рассчитаны предварительно, или их выработка в момент формирования подписи.

Дополнительные контрольные комбинации, которые передаются вместе с подписью и используются при ее проверке, вырабатываются при формировании ключа проверки по ключу подписи и могут храниться в системе и использоваться в момент формирования подписи, либо вычисляться заново в этот момент. Первый подход предполагает затраты дисковой памяти, так как необходимо хранить 2^L+1-2 хэш-комбинаций всех уровней, а второй требует большого объема вычислений в момент формирования подписи. Можно использовать и компромиссный подход - хранить все хэш-комбинации начиная с некоторого уровня l^*, а комбинации меньшего уровня вычислять при формировании подписи. В рассмотренной выше схеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций, используемых при проверки (всего их 15, но самая верхняя не используется), тогда при проверке подписи их не надо будет вычислять заново. Можно хранить 6 комбинаций начиная с уровня 1 (C₀⁽¹⁾, C₁⁽¹⁾, C₂⁽¹⁾, C₃⁽¹⁾, C₀⁽²⁾, C₁⁽²⁾), тогда при проверке подписи сообщения №5 необходимо будет заново вычислить комбинацию C₄⁽⁰⁾, а остальные (C₀⁽²⁾,C₃⁽¹⁾) взять из «хранилища», и т.д.. Указанный подход позволяет достичь компромисса между быстродействием и требованиям к занимаемому количеству дискового пространства. Надо отметить, что отказ от хранения комбинаций одного уровня приводит к экономии памяти и росту вычислительных затрат примерно вдвое, то есть зависимость носит экспоненциальный характер.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2nn_G-битовый массив X интерпретируется как массив из 2n_G n-битовых элементов X_j, X=(X₁,X₂,...,X_2nG), |X_j|=n,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2nn_G-битовый массив X интерпретируется как массив из n_G пар n-битовых элементов X=((X₁,X₂),...,(X_2nG-₁,X_2nG)), |X_j|=n,

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

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

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

В результате получаем цифровую подпись хэш-блока сообщения S=(X,D), состоящую из массива подписей битовых групп блока X=(X₁,X₂,...,X₂n_G) и из массива дополнительных проверочных комбинаций D=(D₀,D₁,...,D_L-₁), необходимых для выполнения процедуры проверки подписи и используемых при вычислении попарных проверочных комбинаций.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

В качестве приложения к настоящей статье приведены исходные тексты на языке ассемблера для процессоров клона Intel 8086 функции вычисления MDC для блоков данных и функции, реализующие алгоритмы описанной схемы цифровой подписи. Функция выработки хэш-кода (MDC) написана таким образом, что позволяет обрабатывать блоки данных по частям, то есть за несколько вызовов. Все функции используют в качестве основы алгоритм зашифрования по ГОСТ 28147-89. Также прилагаются тексты тестовых программ на языке Си для проверки неизменности файлов на основе MDC и цифровой подписи.

Литература

А.Ю. Винокуров. ГОСТ не прост..., а очень прост, М., Монитор.-1995.-N1.

А.Ю. Винокуров. Еще раз про ГОСТ., М., Монитор.-1995.-N5.

А.Ю.Винокуров. Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86., Рукопись, 1997.

А.Ю. Винокуров. Как устроен блочный шифр?, Рукопись, 1995.

М.Э. Смид, Д.К. Бранстед. Стандарт шифрования данных: прошлое и будущее. /пер. с англ./ М., Мир, ТИИЭР.-1988.-т.76.-N5.

Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89, М., Госстандарт, 1989.

Б.В. Березин, П.В. Дорошкевич. Цифровая подпись на основе традиционной криптографии//Защита информации, вып.2.,М.: МП "Ирбис-II",1992.

W. Diffie, M.E. Hellman. New Directions in cryptography// IEEE Trans. Inform. Theory, IT-22, vol 6 (Nov. 1976), pp. 644-654.

У. Диффи. Первые десять лет криптографии с открытым ключом. /пер. с англ./ М., Мир, ТИИЭР.-1988.-т.76.-N5.

Размещено на Allbest.ru