Проблема аутентификации данных и блочные шифры (стр. 5 из 9)

1. Алгоритм GKвыработки пары ключей – подписи KSи проверки подписи KCс использованием вектора случайных параметров R: (KS,KC)=GK(R), здесь:

KS – ключ подписи, он должен быть известен только подписывающему;

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

2. Алгоритм Sподписи сообщения T с использованием секретного ключа подписи KS:

s=S(T,KS),

где s – цифровая подпись сообщения;

3. Алгоритм V проверки подписи с использованием ключа проверки подписи KC, выдающий в качестве результата булево значение – подтверждается или не подтверждается авторство сообщения:

V(T,s,KC)Î{0,1}.

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

· вычисляют контрольную комбинацию по некоторому алгоритму C с использованием подписанного сообщения и цифровой подписи:

c=C(T,s);

· сравнивают контрольную комбинацию c и ключ проверки подписи KC, если они совпадают, то подпись признается верной, а данные – подлинными, в противном случае данные считаются ложными.

Собственно говоря, указанных трех алгоритмов достаточно для реализации схемы цифровой подписи, однако на практике в схемы добавляют еще один алгоритм – функцию выработки хэш–блока для подписываемого массива данных T. Большинство криптографических алгоритмов оперируют блоками данных фиксированного размера, а массивы большего размера обрабатывают по частям, что необходимо для обеспечения эффективности и надежности этих схем. Если такой же подход использовался при выработке цифровой подписи, блоки массивов информации подписывались бы отдельно друг от друга, и размер подписи оказался бы сравнимым с размером подписываемого массива данных, что по вполне понятным причинам не удобно. Поэтому в практических схемах ЭЦП подписывается не само сообщение, а его хэш–код, то есть результат вычисления функции необратимого сжатия для этого массива, который имеет фиксированный размер. Таким образом, в схему ЭЦП добавляется четвертый алгоритм:

4. Алгоритм H вычисления необратимой хэш–функции для подписываемых массивов:

h=H(T).

Алгоритм вычисления хэш–функции и прочие алгоритмы схемы не зависят друг от друга и согласуются только по размеру блоков, которыми они оперируют. Это позволяет при необходимости менять в схеме подписи способ вычисления хэш–значений.

Для работоспособной схемы электронно-цифровой подписи необходимо выполнение следующих условий:

· никто, кроме лица, обладающего секретным ключом подписи KS, не может корректно подписать заданное сообщениеT;

Поскольку сторона, проверяющая подпись, обладает открытым ключом KC проверки подписи, из указанного свойства следует, что не должно существовать вычислительно эффективного алгоритма вычисления секретного ключа KS по открытому KC.

· никто, включая лицо, обладающее ключом подписи, не в состоянии построить сообщениеT', подходящее под наперед заданную подписьs.

При предложении какой-либо схемы подписи оба эти свойства необходимо доказывать, что делается обычно доказательством равносильности соответствующей задачи вскрытия схемы какой-либо другой, о которой известно, что она вычислительно неразрешима. Практически все современные алгоритмы цифровой подписи и прочие схемы «современной криптографии» основаны на так называемых «сложных математических задачах» типа факторизации больших чисел или логарифмирования в дискретных полях. Однако доказательство невозможности эффективного вычислительного решения этих задач отсутствует, и нет никаких гарантий, что они не будут решены в ближайшем будущем, а соответствующие схемы взломаны – как это произошло с «ранцевой» схемой цифровой подписи [9]. Более того, с бурным прогрессом средств вычислительных техники «границы надежности» методов отодвигаются в область все больших размеров блока. Всего пару десятилетий назад, на заре криптографии с открытым ключом считалось, что для реализации схемы подписи RSA достаточно 128- или даже битовых чисел. Сейчас эта граница отодвинута до 1024-битовых чисел – практически на порядок, – и это далеко еще не предел. Надо ли объяснять, что с каждой такой «подвижкой» приходится перепроектировать аппаратуру и переписывать программы, реализующие схему. Ничего подобного нет в области классических блочных шифров, если не считать изначально ущербного и непонятного решения комитета по стандартам США ограничить размер ключа алгоритма DES 56-ю битами, тогда как еще во время обсуждения алгоритма предлагалось использовать ключ большего размера [5]. Схемы подписи, основанные на классических блочных шифрах, свободны от указанных недостатков:

· во-первых, их стойкость к попыткам взлома вытекает из стойкости использованного блочного шифра;

Надо ли говорить, что классические методы шифрования изучены гораздо больше, а их надежность обоснована неизмеримо лучше, чем надежность методов «современной криптографии».

· во-вторых, даже если стойкость использованного в схеме подписи шифра окажется недостаточной в свете прогресса вычислительной техники, его легко можно будет заменить на другой, более устойчивый, с тем же размером блока данных и ключа, без необходимости менять основные характеристики всей схемы – это потребует только минимальной модификации программного обеспечения;

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

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