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

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. Таким образом, вполне возможно, что проблема взлома алгоритма ЭЦП легче общей проблемы дис­кретного логарифмирования.