Анимация
JavaScript
|
Главная Библионтека 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 |