Электронно-цифровая подпись как инструмент для придания юридической силы электронным документам

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

Функции DSA ограничены только цифровой подписью, система принципиально  не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи.

Вместе с проектом DSS опубликован  проект стандарта SHS (Secure Hash Standard), описывающий  однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования вместе с DSA. Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе.

 

 

11. Стандарт на процедуры ЭЦП  ГОСТ Р 34.10-94

 

Отечественным стандартом на процедуры выработки и проверки ЭЦП является ГОСТ  Р 34.10-94. Схема ЭЦП, предложенная в данном стандарте, во многом напоминает подпись в DSA.

 

Цифровая подпись представляет собой два больших целых простых  числа. Общедоступные параметры  схемы ЭЦП  (p,q,a) должны удовлетворять следующим условиям:

 

p: 2^501<p<2^512  или 2^1020<p<2^1020

q: простой делитель числа (p-1), который удовлетворяет

    условию 2^254<q<2^256

 

a: 1<a<p-1, a^q(mod p) =1

 

Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете.

 

Открытый ключ вычисляется:  y=a^x mod p.

 

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

 

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

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

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

Всего пару десятилетий  назад, на заре криптографии с открытым ключом считалось, что для реализации схемы подписи RSA достаточно даже 128-битовых  чисел. Сейчас эта граница отодвинута до 1024-битовых чисел – практически  на порядок, – и это далеко еще не предел. Это приводит к необходимости переписывать реализующие схему программы, и зачастую перепроектировать аппаратуру.

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

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

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

Итак, вернемся к схеме  Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре. Предположим, в нашем распоряжении есть алгоритм зашифрования EK, оперирующий блоками данных X размера n и использующий ключ размером nK: |X|=n, |K|=nK. Структура ключевой информации в схеме следующая: секретный ключ подписи kS выбирается как произвольная (случайная) пара ключей k0, k1 используемого блочного шифра:

kS=(k0,k1);

Таким образом, размер ключа  подписи равен удвоенному размеру  ключа использованного блочного шифра:

|KS|=2|K|=2nK.

Ключ проверки представляет собой результат шифрования двух блоков текста X0 и X1 с ключами k0 и k1 соответственно:

kV=(C0, C1) =

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

|kV|=2|X|=2n.

Алгоритм Sig выработки  цифровой подписи для бита t (t О{0,1}) заключается просто в выборе соответствующей  половины из пары, составляющей секретный  ключ подписи:

s = S(t) = kt.

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

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

.

Покажем, что данная схема  работоспособна, для чего проверим выполнение необходимых свойств  схемы цифровой подписи:

Невозможность подписать  бит t, если неизвестен ключ подписи. Действительно, для выполнения этого злоумышленнику потребовалось бы решить уравнение Es(Xt)=Ct относительно s, что эквивалентно определению ключа для известных блоков шифрованного и соответствующего ему открытого текста, что вычислительно невозможно в силу использования стойкого шифра.

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

Es(X0)=C0, 
Es(X1)=C1.

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

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

размер ключа подписи: nkS=2nHЧnK.

размер ключа проверки подписи: nС=2nHn.

размер подписи: nS =nHЧnK.

Если, например, в качестве основы в данной схеме будет использован шифр ГОСТ 28147–89 с размером блока n=64  бита и размером ключа nK=256 бит, и для выработки хэш–блоков будет использован тот же самый шифр в режиме выработки имитовставки, что даст размер хэш–блока nH=64 то размеры рабочих блоков будут следующими:

размер ключа подписи: nkS=2nHЧnK =2Ч64Ч256бит=4096 байт;

размер ключа проверки подписи: nС=2nHn = 2Ч64Ч64 бит = 1024 байта.

размер подписи: nS =nHЧnK = 64Ч256 бит = 2048 байт.

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

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

Центральным в этом подходе  является алгоритм «односторонней криптографической прокрутки», который в некотором роде может служить аналогом операции возведения в степень. Как обычно, предположим, что в нашем распоряжении имеется криптографический алгоритм EK с размером блока данных и ключа соответственно n и nK бит, причем nЈnK. 

Пусть в нашем распоряжении также имеется некоторая функция  отображения n–битовых блоков данных в nK–битовые Y=Pn®nK(X),  |X|=n,  |Y|=nK. Определим  рекурсивную функцию Rk «односторонней прокрутки» блока данных T размером n бит k раз (k і 0) при помощи следующей формулы:

 

 

 

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

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

 

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

Rk+k'(T)=Rk'(Rk(T)) = Rk(Rk'(T)).

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

Теперь покажем, как  указанную операцию можно использовать для подписи блока T, состоящего из nT битов.

Секретный ключ подписи kS выбирается как произвольная пара блоков k0, k1, имеющих размер блока  данных используемого блочного шифра, т.е. размер ключа выработки подписи равен удвоенному размеру блока данных использованного блочного шифра: |kS|=2n;

Ключ проверки подписи  вычисляется как пара блоков, имеющих  размер блоков данных использованного  алгоритма по следующим формулам:

kC=(C0,C1) = (R2nT–1(K0), R2nT–1(K1)).

В этих вычислениях также  используются несекретные блоки  данных X0 и X1, являющиеся параметрами  функции «односторонней прокрутки», они обязательно должны быть различными. Таким образом, размер ключа проверки подписи также равен удвоенному размеру блока данных использованного блочного шифра: |kC|=2n.

Вычисление и проверка ЭЦП будут выглядеть следующим  образом:

Алгоритм SignT выработки  цифровой подписи для  nT-битового блока T заключается в выполнении «односторонней прокрутки» обеих половин ключа подписи T и 2nT–1–T раз соответственно:

 

s=SignT(T)=(s0,s1)=.

 

Алгоритм VernT  проверки подписи состоит в проверке истинности соотношений , которые, очевидно, должны выполняться для подлинного блока данных  T:

R2nT–1–T(s0)=R2nT–1–T(RT(k0))=R2nT–1–T+T(k0)=R2nT–1(k0)=C0, 
RT(s1)=RT(R2nT–1–T(k1))=RT+2nT–1–T(k1)=R2nT–1(k1)=C1.

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

 

 

 

Покажем, что для данной схемы выполняются необходимые  условия работоспособности схемы  подписи:

Предположим, что в распоряжении злоумышленника есть nT-битовый блок T, его подпись s=(s0,s1), и ключ проверки  kC=(C0,C1). Пользуясь этой информацией, злоумышленник пытается найти правильную подпись s'=(s'0,s'1)  для другого nT-битового блока T'. Для этого ему надо решить следующие уравнения относительно s'0 и s'1:

R2nT–1–T'(s'0)=C0, 
RT'(s'1)=C1.

В распоряжении злоумышленника есть блок данных T с подписью s=(s0,s1), что позволяет ему вычислить  одно из значений s'0,s'1, даже не владея ключом подписи: