DSA

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

История и стандартизация

Разработка в США

В начале 1990-х годов NIST инициировал разработку стандарта цифровой подписи для государственных нужд. В августе 1991 года был опубликован проект DSA, который вызвал споры в криптографическом сообществе из-за использования более медленного алгоритма проверки подписи по сравнению с RSA. После публичных обсуждений и доработок в 1994 году алгоритм был утверждён как стандарт FIPS 186.

Обновления версий

Стандарт DSA неоднократно пересматривался:

• FIPS 186-1 (1998) — добавлена поддержка большего размера ключей (до 1024 бит) и хеш-функции SHA-1.
• FIPS 186-2 (2000) — включена поддержка алгоритмов на эллиптических кривых (ECDSA).
• FIPS 186-3 (2009) — увеличен максимальный размер ключа до 3072 бит, добавлена поддержка SHA-2.
• FIPS 186-4 (2013) — уточнены требования к генерации параметров и тестированию.
• FIPS 186-5 (2023) — исключён DSA на основе дискретных логарифмов (классический DSA), оставлен только ECDSA и EdDSA.

Использование в России

В Российской Федерации DSA не является стандартизированным алгоритмом для государственных нужд. Вместо него применяются отечественные криптографические стандарты ГОСТ Р 34.10-2012 (на основе эллиптических кривых) и ГОСТ Р 34.10-2001. Однако DSA может использоваться в коммерческих системах и международных протоколах.

Математические основы

Задача дискретного логарифмирования

Безопасность DSA основана на сложности вычисления дискретного логарифма в мультипликативной группе простого поля Zₚ*. Для заданных чисел g и y найти x такое, что gˣ ≡ y (mod p), при больших p (не менее 1024 бит) считается вычислительно неосуществимым.

Параметры алгоритма

DSA использует три открытых параметра:

• p — простое число длиной от 512 до 3072 бит (в классической версии до 1024 бит).
• q — простой делитель p-1 длиной 160 бит (в классической версии) или 256 бит (в расширенной).
• g — генератор подгруппы порядка q в Zₚ*.

Ключи

• Закрытый ключ (x) — случайное число в интервале 1 < x < q.
• Открытый ключ (y) — вычисляется как y = gˣ mod p.

Алгоритм работы

Генерация подписи

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

1. Вычисляется хеш-значение h = H(m), где H — криптографическая хеш-функция (SHA-1, SHA-256).
2. Генерируется случайное число k (1 < k < q).
3. Вычисляется r = (gᵏ mod p) mod q.
4. Вычисляется **s = (k⁻¹ (h + x r)) mod q**.
5. Подпись представляет собой пару (r, s).

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

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

1. Вычисляется h = H(m).
2. Вычисляется w = s⁻¹ mod q.
3. Вычисляется **u1 = (h * w) mod q**.
4. Вычисляется **u2 = (r * w) mod q**.
5. Вычисляется **v = (gᵘ¹ * yᵘ² mod p) mod q**.
6. Подпись считается верной, если v = r.

Классификация и варианты

Классический DSA (FIPS 186-4)

Основан на дискретных логарифмах в полях Галуа. Использует параметры p, q, g фиксированной длины. Поддерживает размеры ключей от 512 до 1024 бит (в более поздних версиях до 3072 бит).

ECDSA (Elliptic Curve Digital Signature Algorithm)

Вариант DSA, использующий эллиптические кривые. Обеспечивает аналогичную безопасность при меньших размерах ключей (например, 256-битный ключ ECDSA эквивалентен 3072-битному ключу DSA). Стандартизирован в ANSI X9.62, IEEE P1363, FIPS 186-5.

EdDSA (Edwards-curve Digital Signature Algorithm)

Современный вариант, использующий кривые Эдвардса (например, Curve25519). Отличается высокой скоростью и устойчивостью к побочным каналам. Стандартизирован в RFC 8032.

Применение

Государственные системы

• США: DSA использовался в правительственных системах для подписания документов и программного обеспечения до 2023 года.
• ЕС: применяется в некоторых национальных электронных подписях (например, в Германии — в рамках стандарта BSI TR-03111).

Коммерческие протоколы

• PGP/GnuPG: поддерживает DSA для создания и проверки подписей.
• SSH: используется в протоколе аутентификации (например, в OpenSSH).
• TLS/SSL: исторически применялся в сертификатах X.509, но в настоящее время вытесняется ECDSA и EdDSA.

Криптовалюты

• Bitcoin: использует ECDSA с кривой secp256k1 для подписания транзакций.
• Ethereum: также применяет ECDSA (кривая secp256k1).
• Litecoin, Dogecoin: аналогично Bitcoin.

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

Производительность

DSA требует значительно больше времени на проверку подписи по сравнению с RSA при одинаковом уровне безопасности. Генерация подписи также медленнее, чем в ECDSA.

Уязвимости

• Случайные числа: если значение k повторяется или предсказуемо, закрытый ключ может быть восстановлен (например, в случае уязвимости в Android-кошельках Bitcoin).
• Атаки по побочным каналам: DSA чувствителен к атакам по времени и энергопотреблению, если не используются защищённые реализации.

Устаревание

С 2023 года классический DSA (на основе дискретных логарифмов) исключён из стандарта FIPS 186-5. NIST рекомендует переходить на ECDSA или EdDSA.

Сравнение с другими алгоритмами

Будущее алгоритма

Классический DSA постепенно вытесняется более эффективными и безопасными алгоритмами на эллиптических кривых. В 2023 году NIST официально исключил его из стандарта FIPS 186-5. Тем не менее, DSA остаётся важным историческим алгоритмом, который заложил основы для современных криптографических стандартов. В России и других странах СНГ DSA не имеет широкого распространения из-за использования национальных стандартов ГОСТ.

Источники

• National Institute of Standards and Technology. FIPS PUB 186-5: Digital Signature Standard (DSS). — 2023.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996.
• RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA).
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.
• Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. — 2nd ed. — Wiley, 1996.