Цифровая подпись DSA

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

История

Разработка DSA началась в конце 1980-х годов как часть усилий NIST по созданию единого стандарта цифровой подписи для правительственных и коммерческих нужд. В 1991 году был опубликован проект стандарта, который вызвал значительную критику со стороны криптографического сообщества, в частности, из-за использования алгоритма, основанного на эллиптических кривых (ECDSA) в качестве альтернативы, и из-за возможного участия Агентства национальной безопасности (АНБ) в разработке. В 1994 году после доработки стандарт FIPS 186 (Federal Information Processing Standard) был официально принят. Впоследствии вышли обновлённые версии — FIPS 186-1 (1998), FIPS 186-2 (2000), FIPS 186-3 (2009) и FIPS 186-4 (2013). В 2023 году NIST объявил о переходе на постквантовые алгоритмы, но DSA остаётся широко используемым в legacy-системах.

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

DSA относится к классу асимметричных криптосистем, где для подписания и проверки используются разные ключи: закрытый (секретный) ключ для создания подписи и открытый ключ для её проверки. Алгоритм является детерминированным, то есть при одинаковых входных данных (документ и закрытый ключ) всегда генерируется одна и та же подпись. Это отличает его от вероятностных схем, таких как RSA-PSS.

Устройство и математические основы

DSA работает в конечной циклической группе простого порядка. Основой алгоритма является задача дискретного логарифмирования: для заданных чисел \( g \) и \( y = g^x \mod p \) вычислить \( x \) практически невозможно при достаточно больших параметрах.

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

• p — большое простое число (длиной от 512 до 3072 бит в разных версиях стандарта).
• q — простой делитель числа \( p-1 \) (длиной 160 бит в первоначальной версии, до 256 бит в FIPS 186-4).
• g — генератор подгруппы порядка \( q \) в поле \( \mathbb{Z}_p^* \), вычисляемый как \( g = h^{(p-1)/q} \mod p \), где \( 1 < h < p-1 \).
• x — закрытый ключ: случайное число в интервале \( [1, q-1] \).
• y — открытый ключ: \( y = g^x \mod p \).

Процесс создания подписи

1. Выбирается случайное число \( k \) в интервале \( [1, q-1] \).
2. Вычисляется \( r = (g^k \mod p) \mod q \). Если \( r = 0 \), выбирается новое \( k \).
3. Вычисляется хеш-значение сообщения \( H(m) \) с помощью криптографической хеш-функции (SHA-1, SHA-2 или SHA-3).
4. Вычисляется \( s = k^{-1} \cdot (H(m) + x \cdot r) \mod q \). Если \( s = 0 \), выбирается новое \( k \).
5. Подпись представляет собой пару чисел \( (r, s) \).

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

1. Проверяется, что \( r \) и \( s \) находятся в интервале \( [1, q-1] \).
2. Вычисляется \( w = s^{-1} \mod q \).
3. Вычисляется \( u_1 = H(m) \cdot w \mod q \).
4. Вычисляется \( u_2 = r \cdot w \mod q \).
5. Вычисляется \( v = (g^{u_1} \cdot y^{u_2} \mod p) \mod q \).
6. Подпись считается верной, если \( v = r \).

Характеристики и особенности

• Размер подписи: фиксированный — 320 бит (40 байт) для стандартных параметров (160-битный q), до 512 бит для 256-битного q.
• Скорость: создание подписи требует одного модульного возведения в степень (для \( g^k \)), проверка — двух возведений. DSA медленнее RSA при проверке, но быстрее при создании подписи.
• Безопасность: основана на сложности дискретного логарифмирования. Для обеспечения стойкости на уровне 128 бит требуется p длиной 3072 бита и q длиной 256 бит.
• Детерминированность: в классической версии DSA детерминирован, что делает его уязвимым к атакам по побочным каналам (side-channel attacks), если генерация случайного числа \( k \) не защищена. Существует вероятностная модификация — DSA с использованием случайного k (probabilistic DSA).
• Зависимость от хеш-функции: DSA не включает хеширование в себя, а использует внешнюю хеш-функцию (обычно SHA-2). Длина хеша должна быть не больше длины q.

Применение

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

• Электронная подпись документов: в государственных и коммерческих системах, например, в рамках российского стандарта ГОСТ Р 34.10-2012 (который, хотя и основан на эллиптических кривых, концептуально близок к DSA).
• Протоколы безопасности: в SSH (Secure Shell) для аутентификации серверов и клиентов, в DNSSEC (Domain Name System Security Extensions) для подписи DNS-записей, в OpenPGP для шифрования и подписи электронной почты.
• Блокчейн и криптовалюты: некоторые криптовалюты, такие как Bitcoin (до перехода на SegWit), использовали ECDSA — вариант DSA на эллиптических кривых. Однако классический DSA в блокчейне применяется редко из-за меньшей эффективности.
• Государственные стандарты: DSA является основой для стандартов цифровой подписи в США (FIPS 186) и ряде других стран. В России аналогом является ГОСТ Р 34.10-2012, который, однако, использует эллиптические кривые.

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

• Уязвимость к повторному использованию k: если дважды использовать одно и то же случайное число \( k \) для подписи разных сообщений, закрытый ключ может быть восстановлен. Это произошло, например, в случае с уязвимостью в протоколе Sony PlayStation 3 (2010 год), где использовался фиксированный k.
• Медленная проверка: DSA требует двух модульных возведений в степень, что делает проверку подписи медленнее, чем у RSA (одно возведение). Это критично для систем с высокой нагрузкой.
• Ограниченная длина хеша: в ранних версиях DSA использовался только SHA-1 (160 бит), что стало проблемой с ростом вычислительных мощностей. В FIPS 186-4 добавлена поддержка SHA-2 (256, 384, 512 бит).
• Постквантовая угроза: алгоритм DSA уязвим к атакам с использованием квантовых компьютеров (алгоритм Шора), что делает его непригодным для долгосрочной безопасности. NIST рекомендует переход на постквантовые алгоритмы, такие как CRYSTALS-Dilithium.

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

• DSA был запатентован правительством США, но патент был передан в общественное достояние.
• В 1990-х годах существовали опасения, что АНБ могло встроить «чёрный ход» в DSA, однако независимый анализ не подтвердил этого.
• Алгоритм DSA является основой для стандарта ECDSA (Elliptic Curve Digital Signature Algorithm), который использует эллиптические кривые вместо модульной арифметики, что позволяет достичь той же безопасности при меньших размерах ключей.

Источники

• FIPS 186-4: Digital Signature Standard (DSS). National Institute of Standards and Technology, 2013.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996.
• Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, 1996.
• Katz J., Lindell Y. Introduction to Modern Cryptography. CRC Press, 2014.
• NIST. Post-Quantum Cryptography: Standardization Process. 2023.