Проблема аутентификации данных и блочные шифры (стр. 6 из 9)
· размер ключа подписи:
nS=nH×2nK=2nHnK.
· размер ключа проверки подписи:
nС=nH×2n=2nHn.
· размер подписи:
nSg=nH×nK=nHnK.
Если, например, в качестве основы в данной схеме будет использован шифр ГОСТ 28147–89 с размером блока n=64 бита и размером ключа nK=256 бит, и для выработки хэш–блоков будет использован тот же самый шифр в режиме выработки MDC, что даст размер хэш–блока nH=64 то размеры рабочих блоков будут следующими:
· размер ключа подписи:
nS=nH×2nK=2nHnK=2×64×256=215бит = 4096 байт.
· размер ключа проверки подписи:
nС=nH×2n=2nHn=2×64×64=213бит = 1024 байта.
· размер подписи:
nSg=nH×nK=nHnK=64×256=214 бит = 2048 байт.
Согласитесь, довольно тяжелые ключики.
Второй недостаток данной схемы, быть может, менее заметен, но зато гораздо более серьезен. Дело в том, что пара ключей подписи и проверки в ней одноразовая! Действительно, выполнение процедуры подписи бита сообщения приводит к раскрытию половины секретного ключа, после чего он уже не является полностью секретным и не может быть использован повторно. Поэтому для каждого подписываемого сообщения необходим свой комплект ключей подписи и проверки. Это исключает возможность практического использования рассмотренной схемы Диффи–Хеллмана в первоначально предложенном варианте в реальных системах ЭЦП.
В силу указанных двух недостатков предложенная схемы до сравнительно недавнего времени рассматривалась лишь как курьезная теоретическая возможность, никто всерьез не рассматривал возможность ее практического использования. Однако несколько лет назад в работе [7] была предложена модификация схемы Диффи–Хеллмана, фактически устраняющая ее недостатки. В настоящей работе данная схема не рассматривается во всех деталях, здесь изложены только основные принципы подхода к модификации исходной схемы Диффи–Хеллмана и описания работающих алгоритмов.
3.3.Модификация схемы Диффи–Хеллмана для подписи битовых групп.
В данном разделе изложены идеи авторов [7], позволившие перейти от подписи отдельных битов в исходной схемы Диффи–Хеллмана к подписи битовых групп. Центральным в этом подходе является алгоритм «односторонней криптографической прокрутки», который в некотором роде может служить аналогом операции возведения в степень. Как обычно, предположим, что в нашем распоряжении имеется криптографический алгоритм 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) обладает двумя крайне важными для нас свойствами:
1. Аддитивность по числу прокручиваний:
Rk+k'(T)=Rk'(Rk(T)).
2. Односторонность или необратимость прокрутки: если известно только некоторое значение функции Rk(T), то вычислительно невозможно найти значение Rk'(T) для любого k'<k – если бы это было возможно, в нашем распоряжении был бы способ определить ключ шифрования по известному входному и выходному блоку криптоалгоритма EK. что противоречит предположению о стойкости шифра.
Теперь покажем, как указанную операцию можно использовать для подписи группы битов: изложим описание схемы подписи блока T, состоящего из nT битов, по точно такой же схеме, по которой в предыдущем разделе описывается схема подписи одного бита.
· секретный ключ подписи KS выбирается как произвольная пара блоков K0, K1, имеющих размер блока данных используемого блочного шифра:
KS=(K0,K1);
Таким образом, размер ключа подписи равен удвоенному размеру блока данных использованного блочного шифра:
|KS|=2n;
· ключ проверки вычисляется как пара блоков, имеющих размер блоков данных использованного криптоалгоритма по следующим формулам:
KC=(C0,C1), где:
C0=R2nT–1(K0), C1=R2nT–1(K1).
В этих вычислениях также используются несекретные блоки данных X0 и X1, являющиеся параметрами функции «односторонней прокрутки», они обязательно должны быть различными.
Таким образом, размер ключа проверки подписи равен удвоенному размеру блока данных использованного блочного шифра:
|KC|=2n.
Алгоритмы модифицированной авторами [7] схемы цифровой подписи Диффи и Хеллмана следующие:
1. Алгоритм G выработки ключевой пары:
Берем случайный блок данных подходящего размера 2n, это и будет секретный ключ подписи:
KS=(K0,K1)=R.
Ключ проверки подписи вычисляем как результат «односторонней прокрутки» двух соответствующих половин секретного ключа подписи на число, равное максимальному возможному числовому значению nT-битового блока данных, то есть на 2nT–1.
KC=(C0,C1)=(R2nT–1(K0), R2nT–1(K1)).
2. Алгоритм SnT выработки цифровой подписи для nT-битового блока T, ограниченного, по своему значению, условием 0£T£2nT–1, заключается в выполнении «односторонней прокрутки» обеих половин ключа подписи T и 2nT–1–Tраз соответственно:
s=SnT(T)=(s0,s1)=(RT(K0), R2nT–1–T(K1)).
3. Алгоритм VnTпроверки подписи состоит в проверке истинности соотношений:
R2nT–1–T(s0)=C0, RT(s1)=C1, которые, очевидно, должны выполняться для подлинного блока данных 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.
Таким образом, функция проверки подписи будет следующей:
Покажем, что для данной схемы выполняются необходимые условия работоспособности схемы подписи:
1. Предположим, что в распоряжении злоумышленника есть 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, даже не владея ключом подписи:
a)если T<T', то s'0=RT'(K0)=RT'–T(RT(K0))=RT'–T(s0),
b)если T>T', то s'1=R2nT–1–T'(K1)=RT–T'(R2nT–1–T(K1))=RT–T'(s1).
Однако для нахождения второй половины подписи (s'1 в случае (a) и s'0 в случае (b)) ему необходимо выполнить прокрутку в обратную сторону, т.е. найти Rk(X), располагая только значением для большего k: Rk'(X), k'>k, что является вычислительно невозможным. Таким образом, злоумышленник не может подделать подпись под сообщением, если не располагает секретным ключом подписи.