Введение
Стандарт цифровой верификации
Алгоритм цифровой подписи (DSA) — это криптосистема с открытым ключом и Федеральный стандарт обработки информации для цифровых подписей, основанный на математической концепции модульной экспоненциации и дискретной логарифмической задаче. DSA является вариантом схем подписей Шнорра и Эль-Гамаля. Национальный институт стандартов и технологий (NIST) предложил DSA для использования в своем Стандарте цифровой подписи (DSS) в 1991 году и принял его как FIPS 186 в 1994 году. Было выпущено пять редакций первоначальной спецификации. Новейшая спецификация: FIPS 186-5 от февраля 2023 года. FIPS 186–2 в 2000 году, FIPS 186–3 в 2009 году, FIPS 186–4 в 2013 году и FIPS 186–5 в 2023 году. Стандарт FIPS 186-5 запрещает подписывать данные с использованием DSA, но разрешает проверять подписи, созданные до даты вступления стандарта в силу. Он должен быть заменен более новыми схемами подписи, такими как EdDSA. DSA защищен патентом, поданным 26 июля 1991 года и ныне истекшим, и автором которого является Дэвид В. Кравиц, бывший сотрудник АНБ. Этот патент был выдан "Соединенным Штатам Америки в лице секретаря торговли, Вашингтон, округ Колумбия", и NIST сделал этот патент доступным во всем мире без уплаты роялти. Клаус П. Шнорр утверждает, что его (также истекший) патент покрывал DSA; это утверждение оспаривается. В 1993 году Дэйву Банисару удалось получить подтверждение через запрос в соответствии с Законом о свободе информации, что алгоритм DSA был разработан не NIST, а АНБ. OpenSSH объявил, что DSA планируется удалить в 2025 году.
The Digital Signature Algorithm (DSA) is a public key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant of the Schnorr and ElGamal signature schemes. The National Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS) in 1991, and adopted it as FIPS 186 in 1994. Five revisions to the initial specification have been released. The newest specification is: FIPS 186 5 from February 2023. FIPS 186–2 in 2000, FIPS 186–3 in 2009, FIPS 186–4 in 2013, and FIPS 186–5 in 2023. Standard FIPS 186 5 forbids signing with DSA, while allowing verification of signatures generated prior to the implementation date of the standard as a document. It is to be replaced by newer signature schemes such as EdDSA. DSA is covered by , filed July 26, 1991 and now expired, and attributed to David W. Kravitz, a former NSA employee. This patent was given to "The United States of America as represented by the Secretary of Commerce, Washington, D. C.", and NIST has made this patent available worldwide royalty free. Claus P. Schnorr claims that his (also now expired) covered DSA; this claim is disputed. In 1993, Dave Banisar managed to get confirmation, via a FOIA request, that the DSA algorithm hasn't been designed by the NIST, but by the NSA. OpenSSH announced that DSA is scheduled to be removed in 2025.
Операция
Алгоритм DSA включает в себя четыре операции: генерация ключа (создание пары ключей), распространение ключей, подписание и проверка подписи.
1. генерация ключей
Генерация ключей состоит из двух фаз. На первой фазе происходит выбор параметров алгоритма, которые могут быть общими для различных пользователей системы, а на второй фазе вычисляется одна пара ключей для конкретного пользователя.
Создание параметров
Выберите одобренную криптографическую хеш-функцию с выходной длиной в битах. В оригинальном DSS всегда использовался SHA-1, но более надежные хеш-функции SHA-2 одобрены для использования в текущей DSS. Если длина хеша больше длины модуля, используются только старшие биты хеша. Выберите длину ключа. Оригинальный DSS ограничивал длину ключа кратной 64 в диапазоне от 512 до 1024 включительно. NIST 800-57 рекомендует длины 2048 (или 3072) для ключей с периодом действия безопасности, превышающим 2010 (или 2030) год. Выберите длину модуля таким образом, чтобы выполнялись требования FIPS 186-4, и чтобы пара (длина модуля, длина хеша) имела одно из следующих значений: (1024, 160), (2048, 224), (2048, 256) или (3072, 256). Использование одного и того же значения дважды (даже при сохранении его в секрете), использование предсказуемого значения или утечка даже нескольких бит в каждой из нескольких подписей достаточно для раскрытия секретного ключа. Эта проблема касается как DSA, так и алгоритма цифровой подписи на эллиптических кривых (ECDSA). В декабре 2010 года группа fail0verflow объявила об успешном восстановлении секретного ключа ECDSA, который Sony использовала для подписи программного обеспечения для игровой консоли PlayStation 3. Атака стала возможной из-за того, что Sony не генерировала новый случайный параметр для каждой подписи. Эту проблему можно предотвратить, детерминированно вычисляя параметр на основе секретного ключа и хеша сообщения, как описано в данном разделе. Это гарантирует, что параметр будет отличаться для каждой подписи и непредсказуем для злоумышленников, не знающих секретный ключ. Кроме того, могут быть созданы вредоносные реализации DSA и ECDSA, в которых параметр выбирается таким образом, чтобы скрыто передавать информацию через подписи. Например, секретный ключ, используемый в автономном режиме, может быть скомпрометирован с идеального автономного устройства, которое выпускает только кажущиеся безобидными подписи.
This issue affects both DSA and Elliptic Curve Digital Signature Algorithm (ECDSA) – in December 2010, the group fail0verflow announced the recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random for each signature. This issue can be prevented by deriving deterministically from the private key and the message hash, as described by This ensures that is different for each and unpredictable for attackers who do not know the private key
In addition, malicious implementations of DSA and ECDSA can be created where is chosen in order to subliminally leak information via signatures. For example, an offline private key could be leaked from a perfect offline device that only released innocent looking signatures.