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

Общеизвестно, что так называемая «современная», она же двухключевая криптография возникла и стала быстро развиваться в последние десятилетия именно потому, что ряд новых криптографических протоколов типа протокола цифровой подписи не удалось эффективно реализовать на базе традиционных криптографических алгоритмов, широко известных и хорошо изученных к тому времени. Тем не менее, это возможно. И первыми, кто обратил на это внимание, были родоначальники криптографии с открытым ключом У. Диффи и М. Хсллман, опубликовавшие описание подхода, позволяющего выполнять процедуру цифровой подписи одного бита с помощью блочного шифра. Прежде чем изложить эту идею, примем во внимание ряд замечаний о сути и реализациях цифровой подписи.

Стойкость какой-либо схемы подписи доказывается обычно установлением равносильности соответствующей задачи вскрытия схемы какойлибо другой, о которой известно, что она вычислительно неразрешима.

Практически все современные алгоритмы ЭЦП основаны на так называемых «сложных математических задачах» типа факторизации больших чисел или логарифмирования в дискретных полях. Однако, доказательство невозможности эффективного вычислительного решения этих задач отсутствует, и нет никаких гарантий, что они не будут решены в ближайшем будущем, а соответствующие схемы взломаны — как это произошло с «ранцевой» схемой цифровой подписи. Более того, с бурным прогрессом средств вычислительной техники «границы надежности» методов отодвигаются в область все больших размеров блока. Всего пару десятилетий назад, на заре криптографии, с открытым ключом считалось, что для реализации схемы подписи RSA достаточно даже 128-битовых чисел.

Сейчас эта граница отодвинута до 1024-битовых чисел и это далеко еще не предел. Все это приводит к необходимости переписывать реализующие схему программы, и зачастую перепроектировать аппаратуру. Ничего подобного не наблюдается в области классических блочных шифров, если не считать изначально ущербного и непонятного решения комитета по стандартам США ограничить размер ключа алгоритма DBS 56-ю битами, тогда как еще во время обсуждения алгоритма предлагалось использовать ключ большего размера. Схемы подписи, основанные на классических блочных шифрах, свободны от указанных недостатков:

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

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

Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре. Предположим, что есть алгоритм зашифрования Ек, оперирующий блоками данных X размера п и использующий ключ размером пк: X = п, К = nk. Структура ключевой информации в схеме следующая: секретный ключ подписи ks выбирается как произвольная (случайная) пара ключей kO, к1 используемого блочного шифра: к s = (кО, kl). Таким образом, размер ключа подписи равен удвоенному размеру ключа использованного блочного шифра: k s = 2 К. = 2пК.

Ключ проверки представляет собой результат шифрования двух блоков текста ХО и XI с ключами кО и kl соответственно:

где являющиеся параметром схемы блоки данных несекретны и известны проверяющей подпись стороне. Таким образом, размер ключа проверки подписи равен удвоенному размеру блока использованного блочного шифра: k s = 2 К = 2пК .

Алгоритм Sig выработки цифровой подписи для бита t заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи: s = S (t) = kt.

Алгоритм Vcr проверки подписи состоит в проверке уравнения Ekt (Xf) = Q, которое, очевидно, должно выполняться для нашего t. Получателю известны все используемые при этом величины.

Таким образом, функция проверки подписи будет следующей:

Q), Es (X t) Ф Ct.

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

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

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

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

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

Центральным в этом подходе является алгоритм «односторонней криптографической прокрутки», который в некотором роде может служить аналогом операции возведения в степень. По своей идее функция односто;

ронней прокрутки чрезвычайно проста, надо всего лишь нужное количество раз (К) выполнить следующие действия: расширить n-битовый блок данных Т до размера ключа использованного алгоритма шифрования (лк), на полученном расширенном блоке как на ключе зашифровать блок данных X, результат зашифрования занести на место исходного блока данных (Т). По определению операция Rk (T) обладает двумя важными свойствами.

1. Аддитивность и коммутативность по числу прокручиваний:

2. Односторонность или необратимость прокрутки: если известно только некоторое значение функции Rk (T), то вычислительно невозможно найти значение Rk'(T), для любого к' < к — если бы это было возможно, то был бы способ определить ключ шифрования по известному входному и выходному блоку алгоритма Ек, что противоречит предположению о стойкости шифра.

При реализации данного алгоритма размер ключа проверки подписи равен удвоенному размеру блока данных использованного блочного шифра: k S = 2п.

Таким образом, рассмотренная модификация схемы ДиффиХеллмана делает возможным подпись не одного бита, а целой битовой группы. Это позволяет в несколько раз уменьшить размер подписи и ключей подписи/проверки данной схемы. Однако надо понимать, что увеличение размера подписываемых битовых групп приводит к экспоненциальному росту объема необходимых вычислений и, начиная с некоторого значения, делает работу схемы также неэффективной. Граница «разумного размера» подписываемой группы находится где-то около десяти бит, и блоки большего размера все равно необходимо подписывать «по частям».

Размер ключа подписи и проверки подписи можно дополнительно уменьшить следующими приемами:

• 1. Нет необходимости хранить ключи подписи отдельных битовых групп, их можно динамически вырабатывать в нужный момент времени с помощью генератора криптостойкой гаммы. Ключом подписи в этом случае будет являться обычный ключ использованного в схеме подписи блочного шифра. Например, если схема подписи будет построена на алгоритме ГОСТ 28 147–89, то размер ключа подписи будет равен 256 битам.
• 2. Аналогично, нет необходимости хранить массив ключей проверки подписи отдельных битовых групп блока, достаточно хранить его значение хеш-функции этого массива. При этом алгоритм выработки ключа подписи и алгоритм проверки подписи будут дополнены еще одним шагом — вычислением хеш-функции массива проверочных комбинаций отдельных битовых групп.