История: Стандарт цифровой подписи (DSS — Digital Signature Standard) был принят национальным Институтом Стандартов и Технологии (NIST) в 1994 г. NIST издал DSS как FIPS-186 (FEDERAL INFORMATION PROCESSING STANDARD 186). DSS применяет алгоритм цифровой подписи (DSA), основанный на схеме Эль — Гамаля, с использованием некоторых идей из схемы Шнорра.
Параметры схемы цифровой подписи: Для построения системы цифровой подписи желающий должен произвести следующие действия:
- 1. Выбор криптографической хеш-функции h (x).
- 2. Выбор большого простого числа q, размерность которого N в битах совпадает с размерностью в битах значений хэш-функции h (x). (изначально значение N было равно 160)
- 3. Выбор простого числа p, такого, что q | (p — 1). Битовая длина p обозначается L (2L? 1 < p < 2L).
- 4. Выбор числа g такого, что его мультипликативный порядок по модулю p равен q. Для его вычисления можно воспользоваться формулой g = h(p-1)/q mod p, где h — некоторое произвольное число, 1 < h < p — 1такое, что g? 1.
Первоочередным параметром схемы цифровой подписи является используемая криптографическая хэш-функция. Важной характеристикой этой функции является битовая длина выходной последовательности. Стойкость криптосистемы на основе DSA не превосходит стойкость используемой хэш-функции и стойкость пары (L, N), чья стойкость не больше стойкости каждого из чисел по отдельности. Ранее рекомендовалась длина p L = 1024 бита.
Генерация ключей:
- 1. Секретный ключ представляет собой число x: 0 < x < q.
- 2. Открытый ключ вычисляется по формуле y = gx mod p.
Открытыми параметрами являются числа (p, q, g, y). Закрытый параметр только один — число x. При этом числа (p, q, g) могут быть общими для группы пользователей, а числа x и y являются соответственно закрытым и открытым ключами конкретного пользователя. При подписании сообщения используются секретные числа x и k, причем число k должно выбираться случайным образом (на практике псевдослучайным) при подписывании каждого следующего сообщения.
Подписание:
- 1. Выбор случайного числа k: 0 < k < q.
- 2. Вычисление r = (gk mod p) mod q.
- 3. Вычисление s = k-1 (h (M) + x * r) mod q.
- 4. Выбор другого k, если оказалось, что r = 0 или s = 0.
Подписью является пара чисел (r, s), общая длина подписи 2*N.
Проверка:
- 1. Вычисление w = s-1 mod q.
- 2. Вычисление u1 = h (M) * w mod q.
- 3. Вычисление u2 = r * w mod q.
- 4. Вычисление v = (gu1 * yu2 mod p) mod q.
Подпись верна, если v = r.
Поскольку фактически подписывается не само сообщение, а его хэш, то очевидно, что несколько различных сообщений могут иметь одинаковую подпись.
