Защита информации цифровая подпись (стр. 4 из 6)

размер ключа подписи: n_kS=2n_HЧn_K.

размер ключа проверки подписи: n_С=2n_Hn.

размер подписи: n_S=n_HЧn_K.

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

размер ключа подписи: n_kS=2n_HЧn_K =2Ч64Ч256бит=4096 байт;

размер ключа проверки подписи: n_С=2n_Hn = 2Ч64Ч64 бит = 1024 байта.

размер подписи: n_S=n_HЧn_K = 64Ч256 бит = 2048 байт.

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

Однако, несколько лет назад Березин и Дорошкевич предложили модификацию схемы Диффи–Хеллмана, фактически устраняющую ее недостатки.

Центральным в этом подходе является алгоритм «односторонней криптографической прокрутки», который в некотором роде может служить аналогом операции возведения в степень. Как обычно, предположим, что в нашем распоряжении имеется криптографический алгоритм E_K с размером блока данных и ключа соответственно n и n_K бит, причем nЈn_K.

Пусть в нашем распоряжении также имеется некоторая функция отображения n–битовых блоков данных в n_K–битовые Y=P_n®nK(X), |X|=n, |Y|=n_K. Определим рекурсивную функцию R_k «односторонней прокрутки» блока данных T размером n бит k раз (kі0) при помощи следующей формулы:

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

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

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

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

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

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

Секретный ключ подписи k_S выбирается как произвольная пара блоков k₀, k₁, имеющих размер блока данных используемого блочного шифра, т.е. размер ключа выработки подписи равен удвоенному размеру блока данных использованного блочного шифра: |k_S|=2n;

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

k_C=(C₀,C₁) = (R_2nT–1(K₀), R_2nT–1(K₁)).

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

Вычисление и проверка ЭЦП будут выглядеть следующим образом:

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

s=Sig_nT(T)=(s₀,s₁)=

.

Алгоритм Ver_nT проверки подписи состоит в проверке истинности соотношений

, которые, очевидно, должны выполняться для подлинного блока данных 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'₁, даже не владея ключом подписи:

(a) если T<T', то s'₀=R_T'(k₀)=R_T'–T(R_T(k₀))=R_T'–T(s₀),

(b) если T>T', то s'₁=R_2nT–1–T'(k₁)=R_T–T'(R_2nT–1–T(k₁))=R_T–T'(s₁).

Однако для нахождения второй половины подписи (s'₁ и s'₀ в случаях (a) и (b) соответственно) ему необходимо выполнить прокрутку в обратную сторону, т.е. найти R_k(X), располагая только значением для большего 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₁).

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

R_T'–T(k₀^*)=k₀^*,R_T'–T(k₁^*)=k₁^*,где k₀^*=R_T(k₀), k₁^*=R_2nT–1–T'(k₁)

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

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