Digital Signature Algorithm

Digital Signature Algorithm (DSA) — это криптографический алгоритм, предназначенный для создания и проверки электронных цифровых подписей. Он основан на математической задаче дискретного логарифмирования в конечных полях и обеспечивает аутентификацию, целостность и неотказуемость электронных документов. DSA был принят в качестве стандарта США (FIPS 186) в 1994 году и широко применяется в системах защиты информации, включая протоколы SSH, PGP и некоторые реализации TLS.

История

Разработка DSA началась в конце 1980-х годов в рамках усилий Национального института стандартов и технологий США (NIST) по созданию единого стандарта цифровой подписи. В 1991 году NIST опубликовал проект стандарта Digital Signature Standard (DSS), который предполагал использование алгоритма, основанного на схеме Эль-Гамаля. После публичных обсуждений и доработок, в 1994 году стандарт FIPS 186 был утверждён. В 1996 году вышла вторая версия стандарта (FIPS 186-1), а в 2000 году — третья (FIPS 186-2), которая включала дополнительные алгоритмы, включая RSA и ECDSA. В 2013 году стандарт был обновлён до версии FIPS 186-4, а в 2023 году — до FIPS 186-5, где DSA остаётся одним из допустимых алгоритмов, хотя его использование постепенно вытесняется более современными схемами, такими как ECDSA и EdDSA.

Криптографические основы

DSA основан на сложности задачи дискретного логарифмирования в мультипликативной группе конечного поля. Безопасность алгоритма зависит от размера используемых параметров: модуля p (обычно 1024 или 2048 бит) и порядка q (160 или 256 бит). Для генерации подписи используется секретный ключ, а для проверки — открытый ключ, который вычисляется как возведение генератора в степень секретного ключа по модулю p.

Описание алгоритма

Генерация ключей

Выбираются простые числа p и q, такие что q делит (p-1). Длина q обычно составляет 160 бит, а p — 1024 или 2048 бит.
Выбирается генератор g подгруппы порядка q. Для этого вычисляется g = h^(p-1)/q mod p, где h — произвольное число от 1 до p-1, такое что g ≠ 1.
Случайным образом выбирается секретный ключ x, удовлетворяющий условию 0 < x < q.
Вычисляется открытый ключ y = g^x mod p.

Параметры (p, q, g) являются общедоступными, x — секретным, y — открытым.

Создание подписи

Для подписи сообщения M:

Вычисляется хеш-значение сообщения H(M) с помощью криптографической хеш-функции (например, SHA-1, SHA-256).
Генерируется случайное число k, такое что 0 < k < q.
Вычисляется r = (g^k mod p) mod q. Если r = 0, выбирается другое k.
Вычисляется s = k^(-1) (H(M) + x r) mod q. Если s = 0, выбирается другое k.

Подпись представляет собой пару (r, s).

Проверка подписи

Для проверки подписи (r, s) для сообщения M:

Проверяется, что 0 < r < q и 0 < s < q.
Вычисляется w = s^(-1) mod q.
Вычисляется u1 = H(M) * w mod q.
Вычисляется u2 = r * w mod q.
Вычисляется v = (g^(u1) * y^(u2) mod p) mod q.
Если v = r, подпись считается действительной; в противном случае — недействительной.

Классификация

DSA относится к классу асимметричных криптосистем с открытым ключом. По типу используемой математической задачи он является алгоритмом на основе дискретного логарифмирования. В зависимости от размера параметров различают:

DSA-1024 — с модулем p длиной 1024 бита (обеспечивает примерно 80-битный уровень безопасности).
DSA-2048 — с модулем p длиной 2048 бит (обеспечивает примерно 112-битный уровень безопасности).
DSA-3072 — с модулем p длиной 3072 бита (обеспечивает примерно 128-битный уровень безопасности).

Также существует вариант алгоритма для эллиптических кривых — ECDSA (Elliptic Curve Digital Signature Algorithm), который является адаптацией DSA к эллиптическим кривым и обеспечивает более высокую производительность при том же уровне безопасности.

Применение

DSA широко используется в различных областях информационной безопасности:

Протокол SSH — для аутентификации пользователей и серверов.
PGP и OpenPGP — для подписи и шифрования электронной почты и файлов.
TLS/SSL — в некоторых реализациях для аутентификации сторон.
Электронный документооборот — в государственных и корпоративных системах (например, в России — в рамках ГОСТ Р 34.10-2012, который является аналогом ECDSA).
Блокчейн и криптовалюты — например, в Bitcoin используется ECDSA с кривой secp256k1.

Критика и ограничения

Несмотря на широкое распространение, DSA имеет ряд недостатков:

Скорость — генерация подписи требует вычисления модульного возведения в степень, что медленнее, чем в RSA с малым показателем степени.
Зависимость от случайности — для каждой подписи требуется уникальное случайное число k. Повторное использование k (даже с разными сообщениями) позволяет восстановить секретный ключ. Известны случаи взлома ключей Bitcoin из-за этой уязвимости.
Размер подписи — подпись DSA (r, s) имеет длину 320 бит для 1024-битного модуля, что больше, чем у некоторых альтернатив (например, RSA-PSS).
Устаревание — современные рекомендации (например, NIST SP 800-57) рекомендуют использовать ECDSA или EdDSA как более эффективные и безопасные альтернативы. DSA с модулем менее 2048 бит считается небезопасным.
Патентные ограничения — в 1990-х годах существовали патентные споры, связанные с DSA, хотя в настоящее время алгоритм является общественным достоянием.

Интересные факты

DSA был разработан как альтернатива RSA, который на момент создания был запатентован (патент RSA истёк в 2000 году).
В 2010 году исследователи продемонстрировали атаку на DSA с использованием некачественных генераторов случайных чисел в смарт-картах.
Стандарт FIPS 186-5 (2023) включает DSA как опциональный алгоритм, но рекомендует использовать ECDSA или EdDSA для новых приложений.
В России аналогом DSA является ГОСТ Р 34.10-2012, который основан на эллиптических кривых, а не на конечных полях.

Источники

FIPS PUB 186-5: Digital Signature Standard (DSS), NIST, 2023.
Bruce Schneier, «Applied Cryptography», 2nd edition, 1996.
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, «Handbook of Applied Cryptography», 1996.
NIST SP 800-57: Recommendation for Key Management, Part 1, 2020.
RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), 2013.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →