Базовая идея Диффи и Хеллмана

Базовая идея Диффи и Хеллмана. Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре.

Предположим, в нашем распоряжении есть алгоритм зашифрования 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 nH2nK 2nHnK. размер ключа проверки подписи nС nH2n 2nHn. размер подписи nSg nHnK nHnK. Если, например, в качестве основы в данной схеме будет использован шифр ГОСТ28147-89 с размером блока n 64 бита и размером ключа nK 256 бит, и для выработки хэш-блоков будет использован тот же самый шифр в режиме выработки MDC, что даст размер хэш-блока nH 64 то размеры рабочих блоков будут следующими размер ключа подписи nS nH2nK 2nHnK 264256 215 бит 4096 байт. размер ключа проверки подписи nС nH2n 2nHn 26464 213 бит 1024 байта. размер подписи nSg nHnK nHnK 64256 214 бит 2048 байт. Согласитесь, довольно тяжелые ключики.

Второй недостаток данной схемы, быть может, менее заметен, но зато гораздо более серьезен.

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

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

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

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