Алгоритм цифровой подписи (digital Signature Algorithm, DSA)

В августе 19991 года Национальный институт стандартов и техники (National Institute of Standards and Technology, NIST) предложил для использования в своем Стандарте цифровой подписи (Digital Signature Standard, DSS) Алгоритм цифровой подписи (Digital Signature Algorithm, DSA). DSA, представляющий собой вариант алгоритмов подписи Schnorr и EIGamal.

Алгоритм использует следующие параметры:

· p = простое число длиной L битов, где L принимает значение, кратное 64, в диапазоне от 512 до 1024. (В первоначальном стандарте размер p был фиксирован и равен 512 битам.)

· q= 160-битовой простое число - множитель p-1.

· g= h^(p-1)/qmod p, где h- любое число, меньшее p-1, для которого h^(p-1)/qmod p больше 1.

· x = число, меньшее q.

· y= g^xmod p.

В алгоритме также используется однонаправленная хэш-функция: H(m). Стандарт определяет использование SHA.

Первые три параметра, p, q и g, открыты и могут быть общими для пользователей сети. Закрытым ключом является x, а открытым - y. Чтобы подписать сообщение, m:

(1) Алиса генерирует случайное число k, меньшее q

(2) Алиса генерирует

r= (g^k mod p)mod q

s = (k ^-1(H(m)+ xr))mod q

Ее подписью служат параметры rи s, она посылает их Бобу.

(3) Боб проверяет подпись, вычисляя

w = s^-1 mod q

u₁ = (H(m) * w)mod q

u₂ = (rw)mod q

v= (() mod p) mod q

Если v= r, то подпись правильна.

Таблица 3.4. представляет собой краткое описание алгоритма.

Открытый ключ:

Закрытый ключ:

Подпись:

Проверка:

w	= s-1 mod q
u1	= (H(m) * w)mod q
u2	= (rw)mod q
v	= (() mod p) mod q
Если v= r, то подпись правильна.