Digital Signature Standard

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

История

Разработка DSS началась в конце 1980-х годов в рамках усилий Национального института стандартов и технологий США (NIST) по созданию единого криптографического стандарта для государственных нужд. В 1991 году NIST опубликовал первый проект стандарта, основанный на алгоритме Digital Signature Algorithm (DSA), разработанном Агентством национальной безопасности (АНБ). Первоначальная версия вызвала критику со стороны криптографического сообщества из-за ограниченного размера ключа (512 бит) и отсутствия возможности шифрования. В 1994 году после общественных обсуждений и доработок была принята первая версия стандарта FIPS 186.

В 2000 году вышла версия FIPS 186-2, которая добавила поддержку алгоритмов RSA и Elliptic Curve Digital Signature Algorithm (ECDSA). Это расширило область применения стандарта, так как RSA был уже широко распространён в коммерческих системах. В 2009 году была принята версия FIPS 186-3, увеличившая минимальный размер ключа до 1024 бит для DSA и добавившая новые размеры ключей для ECDSA. В 2013 году вышла версия FIPS 186-4, которая уточнила требования к генерации ключей и добавила поддержку хэш-функций семейства SHA-2. В 2023 году была опубликована текущая версия FIPS 186-5, которая исключила устаревшие алгоритмы (например, DSA с ключом 1024 бит) и добавила поддержку алгоритмов на основе эллиптических кривых EdDSA (Edwards-curve Digital Signature Algorithm).

Алгоритмы, входящие в стандарт

DSS определяет три основных алгоритма цифровой подписи: DSA, RSA и ECDSA. Каждый из них имеет свои особенности, области применения и уровни безопасности.

DSA (Digital Signature Algorithm)

DSA — алгоритм, основанный на задаче дискретного логарифмирования в конечном поле. Он был разработан АНБ и стал первым алгоритмом, включённым в стандарт. DSA работает следующим образом:

• Генерация ключей: выбираются простые числа \( p \) (длиной от 1024 до 3072 бит) и \( q \) (длиной 256 бит), а также генератор \( g \). Закрытый ключ \( x \) — случайное число от 1 до \( q-1 \). Открытый ключ \( y = g^x \mod p \).
• Подписание: для сообщения \( m \) вычисляется хэш \( h(m) \). Генерируется случайное число \( k \). Вычисляются \( r = (g^k \mod p) \mod q \) и \( s = k^{-1} (h(m) + x \cdot r) \mod q \). Подпись — пара \( (r, s) \).
• Проверка: вычисляется \( w = s^{-1} \mod q \), \( u1 = h(m) \cdot w \mod q \), \( u2 = r \cdot w \mod q \), \( v = (g^{u1} \cdot y^{u2} \mod p) \mod q \). Подпись верна, если \( v = r \).

DSA медленнее RSA при проверке подписи, но быстрее при генерации. Он не поддерживает шифрование, что ограничивает его применение.

RSA (Rivest-Shamir-Adleman)

RSA — алгоритм, основанный на задаче факторизации больших целых чисел. Он был разработан в 1977 году и включён в DSS начиная с версии FIPS 186-2. RSA работает следующим образом:

• Генерация ключей: выбираются два больших простых числа \( p \) и \( q \), вычисляется \( n = p \cdot q \). Выбирается открытая экспонента \( e \) (обычно 65537). Вычисляется закрытая экспонента \( d = e^{-1} \mod \phi(n) \), где \( \phi(n) = (p-1)(q-1) \). Открытый ключ — \( (n, e) \), закрытый — \( (n, d) \).
• Подписание: для сообщения \( m \) вычисляется хэш \( h(m) \). Подпись \( s = h(m)^d \mod n \).
• Проверка: вычисляется \( h' = s^e \mod n \). Подпись верна, если \( h' = h(m) \).

RSA широко используется благодаря своей универсальности (поддерживает шифрование и подпись) и высокой скорости проверки подписи. Однако он требует больших ключей (2048 бит и более) для обеспечения безопасности.

ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA — вариант DSA, использующий эллиптические кривые. Он был включён в стандарт начиная с версии FIPS 186-2. ECDSA работает следующим образом:

• Генерация ключей: выбирается эллиптическая кривая \( E \) над конечным полем \( F_p \) и базовая точка \( G \) порядка \( n \). Закрытый ключ \( d \) — случайное число от 1 до \( n-1 \). Открытый ключ \( Q = d \cdot G \).
• Подписание: для сообщения \( m \) вычисляется хэш \( h(m) \). Генерируется случайное число \( k \). Вычисляется точка \( (x_1, y_1) = k \cdot G \). Вычисляется \( r = x_1 \mod n \). Если \( r = 0 \), выбирается новое \( k \). Вычисляется \( s = k^{-1} (h(m) + d \cdot r) \mod n \). Подпись — пара \( (r, s) \).
• Проверка: вычисляется \( w = s^{-1} \mod n \), \( u1 = h(m) \cdot w \mod n \), \( u2 = r \cdot w \mod n \), точка \( (x_1, y_1) = u1 \cdot G + u2 \cdot Q \). Подпись верна, если \( x_1 \mod n = r \).

ECDSA обеспечивает более высокую безопасность при меньших размерах ключей по сравнению с DSA и RSA. Например, ключ ECDSA длиной 256 бит эквивалентен по стойкости ключу RSA длиной 3072 бит.

EdDSA (Edwards-curve Digital Signature Algorithm)

EdDSA — алгоритм, основанный на эллиптических кривых в форме Эдвардса. Он был включён в стандарт в версии FIPS 186-5. EdDSA использует кривую Ed25519 (для 128-битного уровня безопасности) или Ed448 (для 224-битного уровня). Основные преимущества EdDSA — высокая скорость работы, устойчивость к атакам по сторонним каналам и детерминированность (не требует генерации случайных чисел).

Требования к хэш-функциям

DSS требует использования хэш-функций, утверждённых NIST. В текущей версии стандарта (FIPS 186-5) разрешены следующие хэш-функции:

• SHA-1 (только для совместимости с устаревшими системами, не рекомендуется для новых применений)
• SHA-224, SHA-256, SHA-384, SHA-512 (семейство SHA-2)
• SHA-512/224, SHA-512/256 (варианты SHA-2 с усечением)
• SHA3-224, SHA3-256, SHA3-384, SHA3-512 (семейство SHA-3)

Размер хэша должен быть не меньше размера параметра \( q \) для DSA и ECDSA, и не меньше размера модуля \( n \) для RSA.

Размеры ключей и уровни безопасности

Стандарт определяет минимальные размеры ключей для каждого алгоритма в зависимости от требуемого уровня безопасности (в битах). В таблице приведены соответствия для 128-битного уровня безопасности (рекомендуемый минимум для современных систем):

Для 192-битного и 256-битного уровней безопасности размеры ключей увеличиваются (например, для RSA — 7680 и 15360 бит соответственно).

Применение

DSS используется в широком спектре государственных и коммерческих приложений:

• Электронный документооборот: подписание контрактов, отчётов, заявлений в системах электронного правительства.
• Криптографические протоколы: TLS/SSL (для аутентификации серверов и клиентов), DNSSEC (для защиты DNS-записей), S/MIME (для электронной почты).
• Блокчейн и криптовалюты: ECDSA используется в Bitcoin, Ethereum и других блокчейнах для подписи транзакций.
• Программное обеспечение: подписание исполняемых файлов, драйверов и обновлений (например, в Microsoft Authenticode).
• Удостоверяющие центры: выдача цифровых сертификатов X.509, где подпись центра сертификации создаётся с использованием RSA или ECDSA.

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

Основные претензии к DSS связаны с его происхождением и техническими ограничениями:

• Закрытость разработки: DSA был разработан АНБ без публичного обсуждения, что вызвало подозрения о возможных закладках (backdoors). Однако последующие криптоаналитические исследования не выявили уязвимостей.
• Сложность реализации: DSA требует генерации качественных случайных чисел для каждого подписания. Повторное использование случайного числа \( k \) позволяет восстановить закрытый ключ (как в случае с уязвимостью в Sony PlayStation 3).
• Устаревание алгоритмов: DSA с ключом 1024 бит был исключён из стандарта в 2023 году из-за недостаточной стойкости. RSA также постепенно вытесняется алгоритмами на эллиптических кривых.
• Отсутствие шифрования: DSA и ECDSA не поддерживают шифрование, что ограничивает их применение в некоторых протоколах.

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

В России аналогом DSS является ГОСТ Р 34.10-2012, который определяет алгоритмы цифровой подписи на основе эллиптических кривых (ГОСТ 34.10-2012) и хэш-функции ГОСТ Р 34.11-2012 («Стрибог»). В Европейском союзе используется стандарт ETSI TS 101 733 (CAdES) и ETSI TS 101 903 (XAdES), которые базируются на тех же криптографических алгоритмах, что и DSS.

Источники

• National Institute of Standards and Technology. FIPS PUB 186-5: Digital Signature Standard (DSS). — Gaithersburg, MD: U.S. Department of Commerce, 2023. — 56 p.
• National Institute of Standards and Technology. FIPS PUB 186-4: Digital Signature Standard (DSS). — Gaithersburg, MD: U.S. Department of Commerce, 2013. — 52 p.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — Chapter 11: Digital Signatures.
• Ferguson N., Schneier B., Kohno T. Cryptography Engineering: Design Principles and Practical Applications. — Wiley, 2010. — Chapter 10: Digital Signatures.
• Bernstein D. J., Lange T. (ed.) Elliptic Curves for Security. — RFC 7748, 2016. — Section 3: Ed25519 and Ed448.