Анимация
JavaScript


Главная  Библионтека 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [ 17 ] 18 19 20 21 22 23 24

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

ЕХо) - Со, EsiXi) = Сь

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

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

размер ключа подписи: Пк = 2пв-пк.

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

размер подписи: «s «н «к-

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

размер ключа подписи: 2«н«к = 2-64-256 бит= 4096 байт;

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

размер подписи: «к 64-256 бит = 2048 байт.

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

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

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

и-битовых блоков данных в Ик-битовые Y = Р„„Х), \Х\ = п, IГI = «к- Определим рекурсивную функцию Rk «односторонней прокрутки» блока данных Т размером п бит к раз (к > 0) при помощи следующей формулы:

Т, к = 0,

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

Rk(T) =



результат зашифрования занести на место исходного блока данных (J). По определению операция Rk{T) обладает двумя важными для нас свойствами:

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

2. Односторонность или необратимость прокрутки: если известно только некоторое значение функции Rk{T), то вычислительно невозможно найти значение Rk{T) для любого к<к - если бы это было возможно, в нашем распоряжении был бы способ определить ключ шифрования по известному входному и выходному блоку алгоритма Ey. что противоречит предположению о стойкости шифра Теперь покажем, как указанную операцию можно использовать для подписи блока Т, состояш,его из «г битов.

Секретный ключ подписи A:s выбирается как произвольная пара блоков Аго, к\, имеюш,их размер блока данных используемого блочного шифра, т.е. размер ключа выработки подписи равен удвоенному размеру блока данных использованного блочного шифра: A:s = 2п;

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

кс = (Co,Ci) = (i?2«-l(0), P2«-l(l)).

в этих вычислениях также используются несекретные блоки данных Хо и Xl, являюш,иеся параметрами функции «односторонней прокрутки», они обязательно должны быть различными. Таким образом, размер ключа проверки подписи также равен удвоенному размеру блока данных использованного блочного шифра: \кс\ = 2п.

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

Алгоритм Sign-j выработки цифровой подписи для пт-битового блока Т заключается в выполнении «односторонней прокрутки» обеих половин ключа подписи Г и 2"-\-Трга соответственно:

Ver(T,s,kc) =

Алгоритм Ver„ проверьси подписи состоит в проверке истинности соотношений R„j.(sq) = Cq,Rj-(si) = Ci, которые,

очевидно, должны выполняться для подлинного блока данных Т:

i?2«T-i-r(5o) = i?2«T-i-r(Pr(o)) = i?2«T-i-r+r(o) = Ri-iiko) = Co, Rrisi) = Rr{R2»--i-r{ki)) = i?r+2«-i-r(A:i) = i?2«-i(A:i) = Ci. Таким образом, функция проверки подписи будет следуюш,ей: \ RnT i T(0) = Со (1) = Cl, О, V-l-г(o)Col%(l)Q• Пoкaжeм, что для данной схемы выполняются необходимые условия работоспособности схемы подписи:

Предположим, что в распоряжении злоумышленника есть «т-битовый блок Т, его подпись s = {sq,S\), и ключ проверки kc (Co,Ci). Пользуясь этой информацией, злоумышленник пытается найти правильную подпись s = {sq,s\) для другого «т-битового блока Т. Для этого ему надо решить следуюш,ие уравнения относительно «о и s\.

i?2«T-l-r(5o) = Со,

Rt{s{) = Cl.

в распоряжении злоумышленника есть блок данных Т с подписью S = {so,S\), что позволяет ему вычислить одно из значений So,s{, даже не владея ключом подписи:

(a) если Т < Г, то So = Rriko) = i?r-r(Pr(o)) = Rr-riso),

(b) если Т>Т, то Sl= i?2«M-r(A:i) = i?r-r(P2«M-r(A:i)) = Rr-risi).

Однако для нахождения второй половины подписи {s{ и so в случаях (а) и (Ь) соответственно) ему необходимо выполнить прокрутку в обратную сторону, т.е. найти RiX), располагая только значением для большего к, что является вычислительно невозможным. Таким образом, злоумышленник не может под-



делать подпись под сообщением, если не располагает секретным ключом подписи.

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

S = SniX) = (so,Si) = (Rriko), i?2«-i-r(A:i)),

s = Sn,{T) = {sl>,s{) - (Rriko), i?2«-i-r(A:i)),

HO ss, следовательно:

Кт{ко) = Rriko) и i?2«-i-r(A:i) = i?2«-i-r(A:i).

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

i?r-r(o) = kl Яг-т{к\) = к\, где = Mko), kl = i?2«T-i-r(A:i)

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

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

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

жим также, что если последняя группа содержит меньшее число битов, обрабатывается она все равно как полная «т-битовая группа. Тогда размеры ключей подписи/проверки и самой подписи совпадают и равны следующей величине:

I Ks 1=1 к с 1=1 S 1= 2иГ-1 = 2- бит,

где \х \ обозначает округление числа х до ближайшего целого в сторону возрастания. Число операций шифрования Е-{Х), требуемое для реализации процедур схемы, определяются нижеследующими соотношениями:

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

Wic=2-{2"t - \)\--\

Пт Пт

при выработке и проверке подписи оно вдвое меньше:

Ws=Wc={2" -1)Г-Ъ

«7-

2"тп nj

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

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

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

Таким образом, проблема размера ключей и подписи решена, однако, второй недостаток схемы - одноразовость ключей - не



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [ 17 ] 18 19 20 21 22 23 24