Описание dsa

DSA, представляющий собой вариант алгоритмов подписи Schnorr и EIGamal, полностью описан в [1154]. Алгоритм использует следующие параметры:

p = простое число длиной L битов, где L принимает значение, кратное 64, в диапазоне от 512 до 1024. (В первоначальном стандарте размер p был фиксирован и равен 512 битам [1149]. Это вызвало множество критических замечаний, и NIST этот пункт алгоритма [1154].)

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

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

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

y = g^x mod p.

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

Первые три параметра, 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, то подпись правильна.

Доказательства математических соотношений можно найти в [1154]. Табл. 20 -1 представляет собой краткое описание алгоритма.

Табл. 20-1. Подписи DSA

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

p	простое число длиной от 512 до 1024 битов (может использоваться группой пользователей)
q	160-битовый простой множитель p-1 (может использоваться группой пользователей)
g	= h(p-1)/q mod p, где h - любое число, меньшее p-1, для которого h(p-1)/q mod p > 1 (может использоваться группой пользователей)
y	= gx mod p (p-битовое число)

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

x	< q (160-битовое число)

Подпись:

k	выбирается случайно, меньшее q
r	(подпись) = (gk mod p) mod q
s	(подпись) = (k-1 (H(m) + xr)) mod q

Проверка:

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

Ускоряющие предварительные вычисления

В Табл. 20 -2 приведены примеры скорости работы программных реализаций DSA [918].

Табл. 20-2. Скорость DSA для различных длин модулей с 160-битовым показателем степени (на SPARC II)

	512 битов	768 битов	1024 бита
Подпись	0.20 ñ	0.43 ñ	0.57 ñ
Проверка	0.35 ñ	0.80 ñ	1.27 с

Практические реализации DSA часто можно ускорить с помощью предварительных вычислений. Обратите внимание, что значение r не зависит от сообщения. Можно создать строку случайных значений k, и затем рассчитать значения r для каждого из них. Можно также вычислить k^-1 для каждого из этих значений k. Затем, когда приходит сообщение, можно вычислить s для заданных r и k^-1.

Эти предварительные вычисления заметно ускоряют DSA. В Табл. 20 -3 приведены сравнения времени вычисления DSA и RSA для конкретной реализации интеллектуальной карточки [1479].

Табл. 20-3. Сравнение времени вычислений RSA и DSA

	DSA	RSA	DSA с общими p, q, g
Глобальные вычисления	Off-card (P)	N/A	Off-card (P)
Генерация ключа	14 ñ	Off-card (S)	4ñ
Предварительные вычисления	14 ñ	N/A	4 ñ
Подпись	0.03 ñ	15 ñ	0.03 ñ
Проверка	16 ñ	l.5 ñ	10 с
	1-5 ñ off-card (P)	1-3 ñ off-card (P)

Вычисления вне карточки (off-card) выполнялись на персональном компьютере i80386/33 МГц. (P) указывает открытые параметры off-card, а (S) - на закрытые параметры off-card. В обоих алгоритмах используется 512-битовый модуль.