Ключ проверки представляет собой результат шифрования двух блоков текста X0 и X1 с ключами k0 и k1 соответственно: kV=(C0, C1) =
где являющиеся параметром схемы блоки данных несекретны и известны проверяющей подпись стороне. Таким образом, размер ключа проверки подписи равен удвоенному размеру блока использованного блочного шифра: |kV|=2|X|=2n.
Алгоритм Sig выработки цифровой подписи для бита t (t ОО{0, 1}) заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи: s = S(t) = kt.
Алгоритм Ver проверки подписи состоит в проверке уравнения Ekt(Xt)=Ct, которое, очевидно, должно выполняться для нашего t. Получателю известны все используемые при этом величины. Таким образом, функция проверки подписи будет следующей: .
Покажем, что данная схема работоспособна, для чего проверим выполнение необходимых свойств схемы цифровой подписи: Невозможность подписать бит t, если неизвестен ключ подписи. Действительно, для выполнения этого злоумышленнику потребовалось бы решить уравнение Es(Xt)=Ct относительно s, что эквивалентно определению ключа для известных блоков шифрованного и соответствующего ему открытого текста, что вычислительно невозможно в силу использования стойкого шифра. Невозможность подобрать другое значение бита t, которое подходило бы под заданную подпись, очевидна: число возможных значений бита всего два и вероятность выполнения двух следующих условий одновременно пренебрежимо мала в просто в силу использования криптостойкого алгоритма: Es(X0)=C0, Es(X1)=C1.
Таким образом, предложенная Диффи и Хеллманом схема цифровой подписи на основе классического блочного шифра обладает такой же стойкостью, что и лежащий в ее основе блочный шифр, и при этом весьма проста. Однако, у нее есть два существенных недостатка. Первый недостаток заключается в том, что данная схема позволяет подписать лишь один бит информации. В блоке большего размера придется отдельно подписывать каждый бит, поэтому даже с учетом хэширования сообщения все компоненты подписи – секретный ключ, проверочная комбинация и собственно подпись получаются довольно большими по размеру и более чем на два порядка превосходят размер подписываемого блока. Предположим, что в схеме используется криптографический алгоритм EK с размером блока и ключа, соответственно n и nK. Предположим также, что используется функция хэширования с размером выходного блока nH. Тогда размеры основных рабочих блоков будут следующими: размер ключа подписи: nkS=2nHЧЧnK. размер ключа проверки подписи: nС=2nHn. размер подписи: nS =nHЧЧnK.
Если, например, в качестве основы в данной схеме будет использован шифр ГОСТ 28147–89 с размером блока n=64 бита и размером ключа nK=256 бит, и для выработки хэш–блоков будет использован тот же самый шифр в режиме выработки имитовставки, что даст размер хэш–блока nH=64 то размеры рабочих блоков будут следующими: размер ключа подписи: nkS=2nHЧЧnK =2ЧЧ64ЧЧ256бит=4096 байт; размер ключа проверки подписи: nС=2nHn = 2ЧЧ64ЧЧ64 бит = 1024 байта. размер подписи: nS =nHЧЧnK = 64ЧЧ256 бит = 2048 байт.
Второй недостаток данной схемы, быть может, менее заметен, но столь же серьезен. Дело в том, что пара ключей выработки подписи и проверки подписи могут быть использованы только один раз. Действительно, выполнение процедуры подписи бита сообщения приводит к раскрытию половины секретного ключа, после чего он уже не является полностью секретным и не может быть использован повторно. Поэтому для каждого подписываемого сообщения необходим свой комплект ключей подписи и проверки. Это практически исключает возможность использования рассмотренной схемы Диффи–Хеллмана в первоначально предложенном варианте в реальных системах ЭЦП. Однако, несколько лет назад Березин и Дорошкевич предложили модификацию схемы Диффи–Хеллмана, фактически устраняющую ее недостатки. Центральным в этом подходе является алгоритм “односторонней криптографической прокрутки”, который в некотором роде может служить аналогом операции возведения в степень. Как обычно, предположим, что в нашем распоряжении имеется криптографический алгоритм EK с размером блока данных и ключа соответственно n и nK бит, причем nЈЈnK. Пусть в нашем распоряжении также имеется некоторая функция отображения n–битовых блоков данных в nK–битовые Y=Pn®®nK(X), |X|=n, |Y|=nK. Определим рекурсивную функцию Rk “односторонней прокрутки” блока данных T размером n бит k раз (k іі 0) при помощи следующей формулы:
где X – произвольный несекретный n-битовый блок данных, являющийся параметром процедуры прокрутки. По своей идее функция односторонней прокрутки чрезвычайно проста, надо всего лишь нужное количество раз (k) выполнить следующие действия: расширить n-битовый блок данных T до размера ключа использованного алгоритма шифрования (nK), на полученном расширенном блоке как на ключе зашифровать блок данных X, результат зашифрования занести на место исходного блока данных (T). По определению операция Rk(T) обладает двумя важными для нас свойствами: Аддитивность и коммутативность по числу прокручиваний: Rk+k'(T)=Rk'(Rk(T)) = Rk(Rk'(T)).
Односторонность или необратимость прокрутки: если известно только некоторое значение функции Rk(T), то вычислительно невозможно найти значение Rk'(T) для любого k'
В этих вычислениях также используются несекретные блоки данных X0 и X1, являющиеся параметрами функции “односторонней прокрутки”, они обязательно должны быть различными. Таким образом, размер ключа проверки подписи также равен удвоенному размеру блока данных использованного блочного шифра: |kC|=2n. Вычисление и проверка ЭЦП будут выглядеть следующим образом: Алгоритм SignT выработки цифровой подписи для nT-битового блока T заключается в выполнении “односторонней прокрутки” обеих половин ключа подписи T и 2nT–1–T раз соответственно: s=SignT(T)=(s0, s1)=.
Алгоритм VernT проверки подписи состоит в проверке истинности соотношений , которые, очевидно, должны выполняться для подлинного блока данных T: R2nT–1–T(s0)=R2nT–1–T(RT(k0))=R2nT–1–T+T(k0)=R2nT–1(k0)=C0, RT(s1)=RT(R2nT–1–T(k1))=RT+2nT–1–T(k1)=R2nT–1(k1)=C1. Таким образом, функция проверки подписи будет следующей:
Покажем, что для данной схемы выполняются необходимые условия работоспособности схемы подписи: Предположим, что в распоряжении злоумышленника есть nT-битовый блок T, его подпись s=(s0, s1), и ключ проверки kC=(C0, C1). Пользуясь этой информацией, злоумышленник пытается найти правильную подпись s'=(s'0, s'1) для другого nT-битового блока T'. Для этого ему надо решить следующие уравнения относительно s'0 и s'1: R2nT–1–T'(s'0)=C0, RT'(s'1)=C1.
В распоряжении злоумышленника есть блок данных T с подписью s=(s0, s1), что позволяет ему вычислить одно из значений s'0, s'1, даже не владея ключом подписи: если T
если T>T', то s'1=R2nT–1–T'(k1)=RT–T'(R2nT–1–T(k1))=RT–T'(s1). Однако для нахождения второй половины подписи (s'1 и s'0 в случаях (a) и (b) соответственно) ему необходимо выполнить прокрутку в обратную сторону, т. е. найти Rk(X), располагая только значением для большего k, что является вычислительно невозможным. Таким образом, злоумышленник не может подделать подпись под сообщением, если не располагает секретным ключом подписи. Второе требование также выполняется: вероятность подобрать блок данных T', отличный от блока T, но обладающий такой же цифровой подписью, чрезвычайно мала и может не приниматься во внимание. Действительно, пусть цифровая подпись блоков T и T' совпадает. Тогда подписи обоих блоков будут равны соответственно: s=SnT(T)=(s0, s1)=(RT(k0), R2nT–1–T(k1)), s'=SnT(T')=(s'0, s'1)=(RT'(k0), R2nT–1–T'(k1)), но s=s', следовательно: RT(k0)=RT'(k0) и R2nT–1–T(k1)=R2nT–1–T'(k1).
Положим для определенности TЈЈT', тогда справедливо следующее: RT'–T(k0*)=k0*, RT'–T(k1*)=k1*, где k0*=RT(k0), k1*=R2nT–1–T'(k1) Последнее условие означает, что прокручивание двух различных блоков данных одно и то же число раз оставляет их значения неизменными. Вероятность такого события чрезвычайно мала и может не приниматься во внимание. Таким образом рассмотренная модификация схемы Диффи–Хеллмана делает возможным подпись не одного бита, а целой битовой группы. Это позволяет в несколько раз уменьшить размер подписи и ключей подписи/проверки данной схемы. Однако надо понимать, что увеличение размера подписываемых битовых групп приводит к экспоненциальному росту объема необходимых вычислений и начиная с некоторого значения делает работу схемы также неэффективной. Граница “разумного размера” подписываемой группы находится где-то около десяти бит, и блоки большего размера все равно необходимо подписывать “по частям”. Теперь найдем размеры ключей и подписи, а также объем необходимых для реализации схемы вычислений. Пусть размер хэш–блока и блока используемого шифра одинаковы и равны n, а размер подписываемых битовых групп равен nT. Предположим также, что если последняя группа содержит меньшее число битов, обрабатывается она все равно как полная nT-битовая группа. Тогда размеры ключей подписи/проверки и самой подписи совпадают и равны следующей величине: бит,
где ййxщщ обозначает округление числа x до ближайшего целого в сторону возрастания. Число операций шифрования EK(X), требуемое для реализации процедур схемы, определяются нижеследующими соотношениями: при выработке ключевой информации оно равно: , при выработке и проверке подписи оно вдвое меньше: .
Размер ключа подписи и проверки подписи можно дополнительно уменьшить следующими приемами: Нет необходимости хранить ключи подписи отдельных битовых групп, их можно динамически вырабатывать в нужный момент времени с помощью генератора криптостойкой гаммы. Ключом подписи в этом случае будет являться обычный ключ использованного в схеме подписи блочного шифра. Например, если схема подписи будет построена на алгоритме ГОСТ 28147-89, то размер ключа подписи будет равен 256 битам. Аналогично, нет необходимости хранить массив ключей проверки подписи отдельных битовых групп блока, достаточно хранить его значение хэш-функции этого массива. При этом алгоритм выработки ключа подписи и алгоритм проверки подписи будут дополнены еще одним шагом – вычислением хэш-функции массива проверочных комбинаций отдельных битовых групп. Таким образом, проблема размера ключей и подписи решена, однако, второй недостаток схемы – одноразовость ключей – не преодолен, поскольку это невозможно в рамках подхода Диффи–Хеллмана. Для практического использования такой схемы, рассчитанной на подпись N сообщений, отправителю необходимо хранить N ключей подписи, а получателю – N ключей проверки, что достаточно неудобно. Эта проблема может быть решена в точности так же, как была решена проблема ключей для множественных битовых групп – генерацией ключей подписи для всех N сообщений из одного мастер-ключа и свертывание всех проверочных комбинаций в одну контрольную комбинацию с помощью алгоритма вычисления хэш-функции. Такой подход решил бы проблему размера хранимых ключей, но привел бы к необходимости вместе подписью каждого сообщения высылать недостающие N–1 проверочных комбинаций, необходимых для вычисления хэш-функции массива всех контрольных комбинаций отдельных сообщений. Ясно, что такой вариант не обладает преимуществами по сравнению с исходным. Упомянутыми выше авторами был предложен механизм, позволяющий значительно снизить остроту проблемы. Его основная идея – вычислять контрольную комбинацию (ключ проверки подписи) не как хэш-функцию от линейного массива проверочных комбинаций всех сообщений, а попарно – с помощью бинарного дерева. На каждом уровне проверочная комбинация вычисляется как хэш-функция от конкатенации двух проверочных комбинаций младшего уровня. Чем выше уровень комбинации, тем больше отдельных ключей проверки "учитывается" в ней. Предположим, что наша схема рассчитана на 2L сообщений. Обозначим через i-тую комбинацию l-того уровня. Если нумерацию комбинаций и уровней начинать с нуля, то справедливо следующее условие: 0 ЈЈ i < 2L–l, а i-ая проверочная комбинация l-того уровня рассчитана на 2l сообщений с номерами от iЧЧ2l до (i+1)ЧЧ2l–1 включительно. Число комбинаций нижнего, нулевого уровня равно 2L, а самого верхнего, L-того уровня – одна, она и является контрольной комбинацией всех 2L сообщений, на которые рассчитана схема. На каждом уровне, начиная с первого, проверочные комбинации рассчитываются по следующей формуле: ,
Страницы: 1, 2, 3, 4
