Основы современной криптографии


Цифровые подписи, основанные на симметричных криптосистемах - часть 6


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

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

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




- Начало -  - Назад -  - Вперед -