В чем разница между DSA и RSA?

Ссылаясь на https://web.archive.org/web/20140212143556/http://courses.cs.tamu.edu:80/pooch/665_spring2008/Australian-sec-2006/less19.html

RSA
Шифрование и дешифрование RSA являются коммутативными, поэтому их можно использовать непосредственно в качестве схемы цифровой подписи
с учетом схемы RSA {(e, R), (d, p, q)}
чтобы подписать сообщение M, вычислить:
S = M power d (mod R)
проверить подпись, вычислить:
M = S power e (mod R) = M мощность ed (mod R) = M (mod R)

RSA можно использовать как для шифрования, так и для цифровых подписей, просто изменив порядок, в котором используются экспоненты: секретный показатель (d) для создания подписи, публичный показатель (e) для всех, кто может проверить подпись. В остальном все идентично.

DSA (алгоритм цифровой подписи)
DSA - это вариант алгоритмов Эль-Гамаля и Шнорра. Он создает 320-битную подпись, но с 512-1024-битной безопасностью, опять же, основанной на сложности вычисления дискретных логарифмов, было довольно широко.

Генерация ключей DSA
сначала выбираются значения общих глобальных открытых ключей (p, q, g):
выбираем большое простое число p = 2 power L
где L = от 512 до 1024 бит и кратно 64
выберите q, 160-битный простой множитель p-1
выберите g = h power (p-1) / q
для любого h ‹ p-1, h (p-1) / q (mod p) ›1
затем каждый пользователь выбирает закрытый ключ и вычисляет свой открытый ключ:
выбирает x‹ q
вычисляет y = g power x (mod p)

Генерация ключей DSA связана с Эль-Гамалем, но несколько сложнее. В основном из-за использования вторичного 160-битного модуля q, используемого для ускорения вычислений и уменьшения размера результирующей подписи.

Создание и проверка подписи DSA

для подписи сообщения M
генерация случайного ключа подписи k, k ‹q
вычисление
r = (g power k (mod p)) (mod q)
s = k-1.SHA (M) + xr (mod q)
отправить подпись (r, s) с сообщением

для проверки подписи вычислите:
w = s-1 (mod q)
u1 = (SHA (M) .w) (mod q)
u2 = rw (mod q)
v = (g power u1.y power u2 (mod p)) (mod q)
если v = r, то подпись проверяется

Создание подписи снова похоже на ElGamal с использованием временного ключа подписи k для каждого сообщения, но сначала выполняется вычисление mod p, а затем mod q, чтобы уменьшить размер результата. Обратите внимание, что здесь явно используется хеш-функция SHA. Проверка также состоит из сравнения двух вычислений, которые тоже немного сложнее, но связаны с Эль-Гамалем.
Обратите внимание, что почти все вычисления производятся по модулю q и, следовательно, выполняются намного быстрее.
Но, в отличие от RSA, DSA может использоваться только для цифровых подписей