Алгоритм DSA

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

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

Секретным ключом является a, открытым ключом - (p,q,a ,y)

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

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

1.3 Проверка подписи
Имеется открытый ключ (p,q,a ,y), сообщение m, подпись сообщения (r,s).
  1. Проверить, что 0<r<q и 0<s<q. Если это не так, отвергнуть подпись.
  2. Вычислить w=s-1 mod q и h(m).
  3. Вычислить u1=wh(m) mod q и u2=rw mod q.
  4. Вычислить v=(a u1yu2 mod p) mod q.
  5. Подпись верна, только если 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 в качестве системных параметров для группы пользователей. Однако для повышения безопасности работы лучше использовать уникальные значения.