Алгоритм цифровой подписи DSA.

Алгоритм DSA

1. Общее описание алгоритма

Алгоритм DSA основывается на двух вычислительный задачах, связанных с дискретным логарифмированием. Одной задачей является сложность вычисления логарифма в Z*p, другая задача - сложность логарифмирования в циклической подгруппе порядка q. Алгоритм является частным случаем цифровой подписи Эль-Гамаля (ElGamal) и был представлен как стандарт FIPS PUB 186-94 (DSS).
1.2 Генерация ключей DSA

Выбирается простое число q, такое, что 2159<q<2160.
Выбирается t, т.ч. 0<=t<=8 и выбирается простое число p так, что 2511+64t<p<2512+64t, причем q должно делить (p-1).
Находится производящий элемент a для циклической группы Z*p порядка q (для этого выбирается g ОZ*p и вычисляется a =g(p-1)/q mod p, Если a ?= 1, то пр. элемент найден).
Выбирается случайное целое a, т. ч. 1<=a<=q-1.
Вычисляется y=a a mod p.
Секретным ключом является a, открытым ключом - (p,q,a ,y)

1.2 Подпись сообщения

Имеется сообщение m. Подпись сообщения секретным ключом выглядит следующим образом.
Выбирается случайное секретное число k, 0<k Вычисляется r=(a k mod p) mod q.
Вычисляется k-1 mod q.
Вычисляется s=k-1{h(m)+ar} mod q, где h(m)-значение хэш-функции от сообщения m.
Подписью для сообщения m является пара (r,s).

1.3 Проверка подписи

Имеется открытый ключ (p,q,a ,y), сообщение m, подпись сообщения (r,s).
Проверить, что 0<r Вычислить w=s-1 mod q и h(m).
Вычислить u1=wh(m) mod q и u2=rw mod q.
Вычислить v=(a u1yu2 mod p) mod q.
Подпись верна, только если v=r.
1.4 Док-во корректности подписи

Если (r,s) является корректной подписью для сообщения m, тогда должно выполняться h(m)=-ar+ks (mod q). Умножим обе части равенства на w и получим, что wh(m)+arw=k (mod q). А это есть u1+au2=k (mod q). Т.е. получаем, что (a u1a au2 mod p) mod q=(a k mod p) mod q. Или (au1yu2 mod p) mod q=(a k mod p) mod q. Это есть v=r, что и требовалось доказать.
2. Практические рекомендации

В данном алгоритме предлагается использовать простое p размером от 512 до 1024 бит. Размер в 512 бит обеспечивает минимальную защищенность. Рекомендуемый размер - не менее 768 бит. Согласно FIPS 186, алгоритм не допускает простых чисел больше 1024 бит.
Совершенно не обязательно существование уникальных p и q для каждого пользователя алгоритма. FIPS допускает использование p,q и a в качестве системных параметров для группы пользователей. Однако для повышения безопасности работы лучше использовать уникальные значения.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.