Цифровая подпись. Общие положения. Цифровые подписи на основе шифросистемы с открытыми ключами стандартов ГОСТ Р и DSS

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

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

2) электронный документ — документ, в котором информация представлена в электронно-цифровой форме и удостоверена посредством электронной цифровой подписи;

3) владелец регистрационного свидетельства — физическое или юридическое лицо, на имя которого выдано регистрационное свидетельство, правомерно владеющее закрытым ключом, соответствующим открытому ключу, указанному в регистрационном свидетельстве;

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

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

6) подписывающее лицо — физическое или юридическое лицо, правомерно владеющее закрытым ключом электронной цифровой подписи и обладающее правом на ее использование на электронном документе;

7) регистрационное свидетельство — документ на бумажном носителе или электронный документ, выдаваемый удостоверяющим центром для подтверждения соответствия электронной цифровой подписи требованиям, установленным настоящим Законом;

8) система электронного документооборота — система обмена электронными документами, отношения между участниками которой регулируется настоящим Законом и иными нормативными правовыми актами Республики Казахстан;

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

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

Общие положения

1. Цифровая (электронная) подпись предназначена для обеспечения подтверждения подлинности и авторства документов, обрабатываемых в электронной форме с помощью вычислительной техники.

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

 2. Процедура электронной подписи включает в себя два алгоритма: формирования цифровой подписи и проверки подлинности подписи.

 Формирование подписи состоит в вычислении по документу, представленному в электронной форме, и секретному параметру(ключу подписывания), имеющемуся лишь у автора подписи, длинной цифровой последовательности, называемой цифровой подписью данного лица под данным документом.

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

Образец подписи - длинная цифровая последовательность(не являющаяся секретной),однозначно связанная с секретным ключом подписывания.

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

Надежность схемы цифровой подписи определяется сложностью следующих трех задач:

— подделки подписи, то есть нахождения значения подпи-си под заданным документом лицом, не являющимся вла-дельцем секретного ключа;

— создания подписанного сообщения, то есть нахождения хотя бы одного сообщения с правильным значением подписи;

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

Цифровые подписи на основе

шифрсистем с открытыми ключами

Идея использования систем шифрования с открытыми ключами для построения систем цифровой подписи как бы заложена в постановке задачи. Действительно, пусть имеется пара преобразований (Е, D), первое из которых зависит от открытого ключа, а второе — от секретного. Для того чтобы вычислить цифровую подпись S для сообщения, владелец секретного ключа может применить к сообщению Μ второе преобразование D: S = D(M). В таком случае вычислить подпись может только владелец секретного ключа, в то время как проверить равенство E(S) = Μ может каждый. Основ­ными требованиями к преобразованиям Ε и D являются:

— выполнение равенства Μ = E(D(M)) для всех сооб­щений М;

—  невозможность вычисления значения D(M) для задан­ного сообщения Μ без знания секретного ключа.

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

Стандарт ЭЦП DSS

В 1991 г. NIST (National Institute of Standards and Technology) предложил для обсуждения проект стандарта ЭЦП DSS (Digital Signature Standard), использую­щий алгоритм DSA (Digital Signature Algorithm). Стойкость данного алгоритма основана на сложности решения задачи дискретного логарифмирования в муль­типликативной группе простого поля F(/p) (см. главу 3).

Формирование подписи.

1.   Отправитель А сообщения Μ предоставляет широкому кругу абонентов (получателей его сообщений) доступ к следующим параметрам:

p — простое число, 2(\⁵¹²⁾ < р< 2(\¹⁰²⁴⁾, битовая длинам кратна 64;

q — простое число, 2(\¹⁵⁹⁾ <р< 2(\¹⁶⁰⁾, и делитель р-1

g=h(\((p-1)/q))(mod p) где h — такое целое число, что 0 < h < p и h(\((p-1)/q)) (mod p) > 1;

у — открытый ключ, сформированный по правилу у = a(\x)(mod p). Здесь x — секретный ключ, известный только А, причем 0 < x < q;

Η (Μ) — хэш-функция, которая по исходному сообщению Μ формирует це­лое число в диапазоне от 1 до q

2.  Пользователь А генерирует случайное число к такое, что 0 < к < q, дер­жит его в секрете и уничтожает сразу после получения подписи.

3.  А находит два числа r и s по следующему правилу:

r=(g(\k)(mod p))(mod q)

s=k(\-1)(xr+H(M))(mod q)

Подписью к сообщению Μ является пара (r, s).

Проверка подписи. Пользователь В получает от А сообщение M’ и подпись (r’,s’) к нему. B должен убедиться, что Μ совпадает с M’. Для этого:

1)  если хотя бы одно из условий 0<s’<q, 0<r’<q не выполняется, то под­пись считается недействительной;

2)  В находит v=(s’)(\-1) mod q

3) В вычисляет z(/-1)=H(M’)v(mod q), z(/2)=r’v(mod q)

4) далее вычисляется u=(g(\z(/1))y(\z(/2))(mod p))(mod q);

5) В проверяет условие r’=u Если оно выполняется, то подпись считается

подлинной и сообщение не измененным, т.е. M’= М.

Корректность алгоритма DSA. Пусть M=M’,s=s’, r=r’. Покажем, что тогда u=r

Итак, v=s(\-1)(mod q), z(/1)=H(M)v(mod q) Имеем u=g(\z1)y(\z2)(mod p)(mod q)=g(\H(M)*s(\-1))*g(\xrs(\-1))(mod p)(mod q)=g(\(k*(xr+H(M)))(\-1))(xr+H(M)))(mod p)(mod q)=r

Таким образом, и = r, и корректность алгоритма доказана. Для нахождения секретных параметров ЭЦП по открытым необходимо ре­шить следующую систему сравнений:

y=(\-)a(\x)(mod p)

g(\k)+pn=(\-)r’(mod p)

s’=(\-)k(\-1)(xr+H(M’))(mod p)

где неизвестными являются х, п, к.

Некоторые замечания по стойкости алгоритма DSA.

1.   В алгоритме формирования подписи есть недостаток: в редких случаях, когда S=0, при проверке подписи будет сбой, так как в этом случае не сущест­вует. Эта ошибка легко устраняется при помощи дополнительной провер­ки, что и сделано в российском стандарте ЭЦП.

2.  Алгоритм DSA медленный. В то время как скорость получения подписи сравнима со скоростью шифрования по схеме RSA, проверка подписи в боль­шом количестве случаев примерно в 100 раз медленнее, чем RSA.

3.  Тот факт, что один модуль p используется многими пользователями, ос­лабляет стойкость алгоритма, поскольку единственный «взлом» p нарушает бе­зопасность сразу всех абонентов, пользующихся этим р. Под взломом понима­ется некое предвычисление, которое позволяет в дальнейшем легко решать проблему дискретного логарифмирования для данного р.

4.   Величина 512 битов для p слишком мала. С учетом тенденции уменьше­ния стоимости вычислений стоимость взлома через несколько лет может сок­ратиться до разумной величины, что для стандарта неприемлемо.

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

6. Анализ алгоритма DSA показывает, что в данном случае проблема взлома подписи, вообще говоря, не сводится к проблеме дискретного логарифмирова­ния, поскольку в алгоритме DSA g — не первообразный корень по модулю р, а лишь элемент порядка q, что намного меньше р-1. Таким образом, вполне возможно, что проблема взлома алгоритма ЭЦП легче общей проблемы дис­кретного логарифмирования.

Арифметические свойства российского стандарта цифровой подписи

Механизм цифровой подписи. Задаются следующие параметры, используе­мые алгоритмом: p — простое число, 2(\⁵⁰⁹⁾ <р<2(\⁵¹²⁾ либо 2(\¹⁰²⁰⁾ < р< 2(\¹⁰²⁴⁾; q — простое число, 2(\²⁵⁴⁾ < q < 2(\²⁵⁶⁾; а — целое число в пределах 1 < а < p -1 такое, что a(\^q) mod p = 1; x — целое число в пределах 0 < x < q; у — це­лое число, равное а(\^х) mod p; Μ — целое число в пределах 0 < Μ < q.

Число x называют секретным ключом пользователя, у — открытым ключом пользователя, Μ — сообщением. В соответствии с алгоритмом проверки подписи в ГОСТ Ρ 34.10—94 электронную подпись можно ввести следующим образом.

Пусть дано сообщение М. Подписью к Μ называется пара целых чисел (r,s) таких, что

1<r<q, 0<s<q

r=(a(\sM(\q-2) mod q)y(\-rM(\q-2) mod q) mod p) mod q

Теорема 14.7.1. Пусть задано целое Μ(0 < Μ < q). Тогда существует ровно q различных решений (r(/k),s(/k))(\q-1)(/k=0) уравнения (14.7.2), причем

r(/k)=(a(\k) mod q), s(/k)=(x*n(/k)+kM) mod q

Доказательство. Легко проверить путем подстановки, что все пары (r(/k),s(/k)) заданные по формулам (14.7.3) и (14.7.4), удовлетворяют равенству (14.7.2). Все эти пары различны. Действительно, если (r(/i),s(/i))=(r(/j),s(/j)) при некоторых i<>j

то, используя (14.7.4), получаем xr(/i)+iM=(\-)xr(/j)+jM(mod q), откуда следует:

(i - j)M=(\-)0(mod q), что вместе с (M,q)=1 дает i=(\-)j (mod q). Последнее сравне-

ние возможно, только если i = j. Таким образом, чтобы доказать утверждение, достаточно показать, что сравнение (14.7.2) имеет не более q решений.

Будем рассматривать циклическую подгруппу группы Z(\*)(/p):

<a>(/p)={a(\k) mod p: k=0, .., q-1}

порожденную элементом а. Для mE{0, .., q-1}определим функцию кси(m) как

число различных элементов группы <a>(/p), которые по модулю q дают остаток т.

Очевидно, равенство SUM(/m=0)(\q-1)кси(m)=q.Пусть Φ — количество решений (14.7.2),

Ф(r) — количество различных s (0<=s<q) таких, что пара (r,s) есть решение

(14.7.2). Тогда Ф=SUM(/r=0)(\q-1)Ф(r)

Зафиксируем r. Поскольку у = а(\^х) тоd р, то имеем равенство

a(\sM(\q-2) mod q)y(\-rM(\q-2) mod p)=a(\a(s-rx)M(\q-2) mod p)

Когда s пробегает значения от 0 до q-1, то v=(s-rx)M(\q-2) также пробегает

(в другом порядке) эти значения. Тогда a(\v) mod p пробегает все элементы груп­пы <a>(/p), когда s изменяется от 0 до q -1. Количество различных s таких, что

r=(a(\sM(\q-2) mod q)y(\-rM(\q-2) mod q) mod p) mod q

есть Φ (r), с одной стороны, и кси(r) — с другой. Тогда

Ф=SUM(/r=0)(\q-1)Ф(r)=SUM(/r=0)(\q-1)кси(r)=q

Итак, количество различных решений сравнения (14.7.2) равно q, и все эти решения описаны по формулам (14.7.3) и (14.7.4).

Введем множества

R(M)={(r(/k),s(/k)):r(/k)=(a(\k) mod p) mod q, s(/k)=(xr(/k)+kM) mod q, 0<=k<=q-1}

S(M)={(r,s)ER(M)Lr-1)rs<>0}.

Тогда множество R(M) состоит из всех решений уравнения (14.7.2), a S(M) — из всех подписей к М.

Чтобы сформировать подпись к сообщению М, необходимо решить сравне­ние (14.7.2) относительно (r, s). Такую пару можно вычислить по формулам (14.7.3) и (14.7.4). Но для этого необходимо знать значение секретного ключа x и параметра к. Таким образом, получаем следующие алгоритмы.

Алгоритм генерации подписи

1.  Генерируем случайное к в интервале [0, q -1] (его значение держится в секрете).

2.  Находим r(/_к) и s(/_k) по формулам (14.7.3) и (14.7.4) (их вычисление осущест­вляется по алгоритмам полиномиальной сложности).

3.  Значение числа к уничтожается.

4.  Если r(/k)s(/k)<>0, то полученная пара (r(/k),s(/k)) является подписью к М. В про­тивном случае переходим к шагу 1.

Алгоритм проверки подписи

1.  Если r < 0 или r > q -1, или s < 0, или s > q -1, то подпись недействитель­ная, иначе переходим к следующему шагу.

2.   Вычисляем z(/0)=M(\q-2) mod q

3. вычисляем z(/1)=sz(/0) mod q

4. вычисляем z(/2)=-rz(/0) mod q

5. вычисляем z(/3)=a(\z1) mod p

6. вычисляем z(/4)=y(\z2) mod p

7. вычисляем z(/5)=z(/3)z(/4) mod p

8. вычисляем z(/6)=z(/5) mod q

9. Если r<>z(/6), то подпись недействительная, иначе подпись действительная.