Проблема аутентификации данных и блочные шифры

       

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


Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре.  Предположим, в нашем распоряжении есть алгоритм зашифрования  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=nnK=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=nnK=nHnK=64×256=214

                  бит = 2048 байт.

                  Согласитесь, довольно тяжелые ключики.

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

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


                  Содержание раздела