Базовая идея Диффи и Хеллмана.
Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре. Предположим, в нашем распоряжении есть алгоритм зашифрования EK, оперирующий блоками данных X размера n и использующий ключ размером nK: |X|=n, |K|=nK. Структура ключевой информации в схеме следующая:
- секретный ключ подписи KS выбирается как произвольная пара ключей K0, K1 используемого блочного шифра:
- ключ проверки вычисляется как пара блоков криптоалгоритма по следующим уравнениям:
- размер ключа подписи:
- размер ключа проверки подписи:
- размер подписи:
- размер ключа подписи:
- размер ключа проверки подписи:
- размер подписи:
KS=(K0,K1);
Таким образом, размер ключа подписи равен удвоенному размеру ключа использованного блочного шифра:
|KS|=2|K|=2nK
KC=(C0,C1), где:
C0=EK0(X0), C1=EK1(X1),
где являющиеся параметром схемы блоки данных X0 и X1 несекретны и известны проверяющей подпись стороне.
Таким образом, размер ключа проверки подписи равен удвоенному размеру блока использованного блочного шифра:
|KC|=2|X|=2n.
Алгоритмы схемы цифровой подписи Диффи и Хеллмана следующие:
1. Алгоритм G выработки ключевой пары:
Берем случайный блок данных размера 2nK, это и будет секретный ключ подписи:
KS=(K0,K1)=R.
Ключ проверки подписи вычисляем как результат двух циклов зашифрования по алгоритму EK:
KC=(C0,C1)=(EK0(X0),EK1(X1)).
2. Алгоритм S выработки цифровой подписи для бита t (t Î{0,1}) заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи:
s=S(t)=Kt.
3. Алгоритм V проверки подписи состоит в проверке уравнения EKt(Xt)=Ct, которое, очевидно, должно выполняться для нашего t. Получателю известны все используемые величины:
Kt=s – цифровая подпись бита,
Ct
– соответствующая половина ключа проверки,
Xt
– несекретный параметр алгоритма.
Таким образом, функция проверки подписи будет следующей:
Не правда ли, все три алгоритма этой схемы изумительно простоты в сравнении со схемами RSA и эль-Гамаля?! Покажем, что данная схема работоспособна, для чего проверим выполнение необходимых свойств схемы цифровой подписи:
1. Невозможность подписать бит t, если неизвестен ключ подписи.
Действительно, для выполнения этого злоумышленнику потребовалось бы решить уравнение Es(Xt)=Ct относительно s, эта задача эквивалентна определению ключа для известных блока шифротекста и соответствующего ему открытого текста, что вычислительно невозможно в силу использования стойкого шифра.
2. Невозможность подобрать другое значение бита t, которое подходило бы под заданную подпись очевидна, потому что число возможных значений бита всего два и вероятность выполнения двух следующих условий одновременно пренебрежимо мала в просто в силу использования криптостойкого алгоритма:
Es(X0)=C0,
Es(X1)=C1.
Таким образом, предложенная Диффи и Хеллманом схема цифровой подписи на основе классического блочного шифра криптостойка настолько, насколько стоек использованный шифр, и при этом весьма проста. Теперь самое время рассказать, почему же эта замечательная схема не нашла сколько-нибудь значительного практического применения. Все дело в том, что у нее есть два недостатка. Всего два, но каких!
Первый недостаток сразу бросается в глаза – он заключается в том, что данная схема позволяет подписать лишь один бит информации. В блоке большего размера придется отдельно подписывать каждый бит, поэтому даже с учетом хеширования сообщения все компоненты подписи – секретный ключ, проверочная комбинация и собственно подпись получаются довольно большими по размеру и более чем на два порядка превосходят размер подписываемого блока. Предположим, что в схеме используется криптографический алгоритм EK с размером блока и ключа, выраженными в битах, соответственно n и nK. Предположим также что размер хэш–блока в схеме равен nH. Тогда размеры основных рабочих блоков будут следующими:
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] была предложена модификация схемы Диффи–Хеллмана, фактически устраняющая ее недостатки. В настоящей работе данная схема не рассматривается во всех деталях, здесь изложены только основные принципы подхода к модификации исходной схемы Диффи–Хеллмана и описания работающих алгоритмов.
