Алгоритм цифровой подписи

Алгоритм цифровой подписи ( DSA ) — это криптосистема с открытым ключом и федеральный стандарт обработки информации для цифровых подписей , основанный на математической концепции модульного возведения в степень и задаче дискретного логарифма . В криптосистеме с открытым ключом генерируются два ключа: данные могут быть зашифрованы только с помощью открытого ключа, а зашифрованные данные могут быть расшифрованы только с помощью закрытого ключа. DSA — это вариант схем подписи Шнорра и Эль-Гамаля . ^{[ 1 ]}^: 486

Национальный институт стандартов и технологий (NIST) предложил DSA для использования в своем стандарте цифровой подписи (DSS) в 1991 году и принял его как FIPS 186 в 1994 году. ^{[ 2 ]} Было выпущено пять редакций первоначальной спецификации. Новейшая спецификация: FIPS 186-5 от февраля 2023 г. ^{[ 3 ]} DSA запатентован, но NIST сделал этот патент доступным по всему миру без лицензионных отчислений. Спецификация FIPS 186-5 указывает, что DSA больше не будет одобрен для создания цифровых подписей, но может использоваться для проверки подписей, созданных до даты внедрения этого стандарта.

Обзор

DSA работает в рамках криптосистем с открытым ключом и основан на алгебраических свойствах модульного возведения в степень вместе с проблемой дискретного логарифма , которая считается вычислительно неразрешимой. Алгоритм использует пару ключей, состоящую из открытого ключа и закрытого ключа. Закрытый ключ используется для создания цифровой подписи сообщения, и такую подпись можно проверить с помощью соответствующего открытого ключа подписывающего лица. Цифровая подпись обеспечивает аутентификацию сообщения (получатель может проверить происхождение сообщения), целостность (получатель может убедиться, что сообщение не было изменено с момента его подписания) и неотказуемость (отправитель не может ложно заявлять, что он не подписал сообщение).

История

В 1982 году правительство США запросило предложения по стандарту подписи с открытым ключом. В августе 1991 года Национальный институт стандартов и технологий (NIST) предложил DSA для использования в своем стандарте цифровой подписи (DSS). Первоначально была серьезная критика, особенно со стороны компаний- разработчиков программного обеспечения , которые уже вложили усилия в разработку программного обеспечения для цифровой подписи на основе криптосистемы RSA . ^{[ 1 ]}^: 484 Тем не менее, NIST принял DSA в качестве федерального стандарта (FIPS 186) в 1994 году. Было выпущено пять версий первоначальной спецификации: FIPS 186–1 в 1998 году, ^{[ 4 ]} ФИПС 186-2 в 2000 г., ^{[ 5 ]} ФИПС 186-3 в 2009 г., ^{[ 6 ]} ФИПС 186-4 в 2013 г., ^{[ 3 ]} и FIPS 186–5 в 2023 году. ^{[ 7 ]} Стандарт FIPS 186-5 запрещает подписание с помощью DSA, но позволяет проверять подписи, созданные до даты реализации стандарта в качестве документа. Он должен быть заменен более новыми схемами подписи, такими как EdDSA . ^{[ 8 ]}

DSA защищен патентом США № 5 231 668 , поданным 26 июля 1991 г., срок действия которого истек, и принадлежит Дэвиду В. Кравицу. ^{[ 9 ]} бывший сотрудник АНБ . Этот патент был передан «Соединенным Штатам Америки в лице министра торговли Вашингтона, округ Колумбия», и NIST сделал этот патент доступным по всему миру без лицензионных отчислений. ^{[ 10 ]} Клаус П. Шнорр утверждает, что его патент США № 4 995 082 (срок действия которого также истек) распространяется на DSA; это утверждение оспаривается. ^{[ 11 ]}

В 1993 году Дэйву Банисару удалось получить подтверждение по запросу FOIA , что алгоритм DSA был разработан не NIST, а АНБ. ^{[ 12 ]}

OpenSSH объявил, что DSA планируется удалить в 2025 году. ^{[ 13 ]}

Операция

Алгоритм DSA включает в себя четыре операции: генерацию ключей (которая создает пару ключей), распределение ключей, подписание и проверку подписи.

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

Генерация ключей состоит из двух этапов. Первый этап — это выбор параметров алгоритма , которые могут быть общими для разных пользователей системы, а второй этап — вычисление одной пары ключей для одного пользователя.

Генерация параметров

Выберите утвержденную криптографическую хеш-функцию. $H$ с выходной длиной $|H|$ биты. В оригинальном DSS $H$ всегда был SHA-1 , но более сильные хеш-функции SHA-2 одобрены для использования в текущем DSS. ^{[ 3 ]}^{[ 14 ]} Если $|H|$ больше длины модуля $N$ , только крайний левый $N$ используются биты хэш-вывода.
Выберите длину ключа $L$ . Исходный DSS ограничен $L$ быть кратным 64 между 512 и 1024 включительно. NIST 800-57 рекомендует длину 2048 (или 3072) для ключей со сроком действия, превышающим 2010 (или 2030). ^{[ 15 ]}
Выберите длину модуля $N$ такой, что $N<L$ и $N\leq |H|$ . FIPS 186-4 определяет $L$ и $N$ иметь одно из значений: (1024, 160), (2048, 224), (2048, 256) или (3072, 256). ^{[ 3 ]}
Выберите $N$ -битное простое число $q$ .
Выберите $L$ -битное простое число $p$ такой, что $p-1$ кратно $q$ .
Выберите целое число $h$ случайно из $\{2\ldots p-2\}$ .
Вычислить $g:=h^{(p-1)/q}\mod p$ . В том редком случае, когда $g=1$ попробуйте еще раз с другим $h$ . Обычно $h=2$ используется. Это модульное возведение в степень можно эффективно вычислить, даже если значения велики.

Параметры алгоритма: ( $p$ , $q$ , $g$ ). Они могут использоваться разными пользователями системы.

Ключи для каждого пользователя

Учитывая набор параметров, второй этап вычисляет пару ключей для одного пользователя:

Выберите целое число $x$ случайно из $\{1\ldots q-1\}$ .
Вычислить $y:=g^{x}\mod p$ .

$x$ это закрытый ключ и $y$ является открытым ключом.

2. Распределение ключей

Подписавшаяся сторона должна опубликовать открытый ключ. $y$ . То есть они должны отправить ключ получателю через надежный, но не обязательно секретный механизм. Подписавшаяся сторона должна хранить закрытый ключ. $x$ секрет.

3. Подписание

Сообщение $m$ подписывается следующим образом:

Выберите целое число $k$ случайно из $\{1\ldots q-1\}$
Вычислить $r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q$ . В том маловероятном случае, что $r=0$ , начните снова с другим случайным образом $k$ .
Вычислить $s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q$ . В том маловероятном случае, что $s=0$ , начните снова с другим случайным образом $k$ .

Подпись $\left(r,s\right)$

Расчет $k$ и $r$ равносильно созданию нового ключа для каждого сообщения. Модульное возведение в степень в вычислениях $r$ — это самая затратная в вычислительном отношении часть операции подписания, но ее можно вычислить до того, как сообщение станет известно. Вычисление обратного модуля $k^{-1}{\bmod {\,}}q$ — вторая по стоимости часть, и ее также можно вычислить до того, как сообщение станет известно. Его можно вычислить с помощью расширенного алгоритма Евклида или малой теоремы Ферма : $k^{q-2}{\bmod {\,}}q$ .

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

Можно проверить, что подпись $\left(r,s\right)$ является допустимой подписью для сообщения $m$ следующее:

Убедитесь, что $0<r<q$ и $0<s<q$ .
Вычислить $w:=s^{-1}{\bmod {\,}}q$ .
Вычислить $u_{1}:=H(m)\cdot w\,{\bmod {\,}}q$ .
Вычислить $u_{2}:=r\cdot w\,{\bmod {\,}}q$ .
Вычислить $v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q$ .
Подпись действительна тогда и только тогда, когда $v=r$ .

Корректность алгоритма

Схема подписи правильна в том смысле, что проверяющая сторона всегда принимает подлинные подписи. Это можно показать следующим образом:

Во-первых, поскольку ${\textstyle g=h^{(p-1)/q}~{\text{mod}}~p}$ , отсюда следует, что ${\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}$ по малой теореме Ферма . С $g>0$ и $q$ является простым, $g$ должен быть порядок $q$ .

Подписавшаяся сторона вычисляет

s=k^{-1}(H(m)+xr){\bmod {\,}}q

Таким образом

{\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}

С $g$ имеет порядок $q$ у нас есть

{\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned}}

Наконец, корректность DSA следует из

{\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}

Чувствительность

При использовании DSA энтропия, секретность и уникальность случайного значения подписи $k$ являются критическими. Это настолько важно, что нарушение любого из этих трех требований может раскрыть злоумышленнику весь закрытый ключ. ^{[ 16 ]} Использование одного и того же значения дважды (даже при сохранении $k$ секрет), использование предсказуемого значения или утечка даже нескольких битов $k$ в каждой из нескольких подписей достаточно, чтобы раскрыть закрытый ключ $x$ . ^{[ 17 ]}

Эта проблема затрагивает как DSA, так и алгоритм цифровой подписи с эллиптической кривой ( ECDSA ) — в декабре 2010 года группа Fail0verflow объявила о восстановлении закрытого ключа ECDSA, используемого Sony для подписи программного обеспечения для игровой консоли PlayStation 3 . Атака стала возможной, потому что Sony не удалось сгенерировать новый случайный $k$ за каждую подпись. ^{[ 18 ]}

Эту проблему можно предотвратить, выведя $k$ детерминированно из закрытого ключа и хэша сообщения, как описано РФК 6979 . Это гарантирует, что $k$ различен для каждого $H(m)$ и непредсказуем для злоумышленников, не знающих закрытый ключ $x$ .

Кроме того, могут быть созданы вредоносные реализации DSA и ECDSA, где $k$ выбран для подсознательной утечки информации через подписи. Например, автономный закрытый ключ может быть украден из идеального автономного устройства, которое выпускает только невинно выглядящие подписи. ^{[ 19 ]}

Реализации

Ниже приведен список криптографических библиотек, обеспечивающих поддержку DSA:

См. также

Ссылки

^ Jump up to: ^а ^б Шнайер, Брюс (1996). Прикладная криптография . Уайли. ISBN 0-471-11709-9 .
^ «FIPS PUB 186: Стандарт цифровой подписи (DSS), 19 мая 1994 г.» . qcsrc.nist.gov . Архивировано из оригинала 13 декабря 2013 г.
^ Jump up to: ^а ^б ^с ^д «FIPS PUB 186-4: Стандарт цифровой подписи (DSS), июль 2013 г.» (PDF) . csrc.nist.gov .
^ «FIPS PUB 186-1: Стандарт цифровой подписи (DSS), 15 декабря 1998 г.» (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 26 декабря 2013 г.
^ «FIPS PUB 186-2: Стандарт цифровой подписи (DSS), 27 января 2000 г.» (PDF) . csrc.nist.gov .
^ «FIPS PUB 186-3: Стандарт цифровой подписи (DSS), июнь 2009 г.» (PDF) . csrc.nist.gov .
^ «FIPS PUB 186-5: Стандарт цифровой подписи (DSS), февраль 2023 г.» (PDF) . csrc.nist.gov .
^ «Стандарт цифровой подписи (DSS)» . Министерство торговли США. 31 октября 2019 года . Проверено 21 июля 2020 г.
↑ Доктор Дэвид В. Кравиц. Архивировано 9 января 2013 г., в Wayback Machine.
^ Вернер Кох. «DSA и патенты»
^ «Годовой отчет CSSPAB за 1994 год» . 26 августа 2009 г. Архивировано из оригинала 26 августа 2009 г.
^ Нойманн, Питер Г. (29 февраля 2020 г.). «Дайджест RISKS, том 14, выпуск 59» . Архивировано из оригинала 29 февраля 2020 г. Проверено 3 октября 2023 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
^ «OpenSSH объявляет график удаления DSA [LWN.net]» . lwn.net . Проверено 11 января 2024 г.
^ «FIPS PUB 180-4: Стандарт безопасного хеширования (SHS), март 2012 г.» (PDF) . csrc.nist.gov .
^ «Специальная публикация NIST 800-57» (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 6 июня 2014 г.
^ «Катастрофа Debian PGP, которая почти случилась» . корневые лаборатории rdist . 18 мая 2009 г.
^ ДСА $k$ -значение Требования
^ Бендель, Майк (29 декабря 2010 г.). «Хакеры описывают безопасность PS3 как эпический провал: получите неограниченный доступ» . Exophase.com . Проверено 5 января 2011 г.
^ Вербюхельн, Стефан (2 января 2015 г.). «Как идеальные офлайн-кошельки все еще могут утекать приватные ключи Биткойнов». arXiv : 1501.00447 [ cs.CR ].

Внешние ссылки

FIPS PUB 186-4: Стандарт цифровой подписи (DSS) , четвертая (и текущая) версия официальной спецификации DSA.
Рекомендации по управлению ключами. Часть 1: общие сведения , Специальная публикация NIST 800-57, стр. 62–63

[schneier-1] Jump up to: ^а ^б Шнайер, Брюс (1996). Прикладная криптография . Уайли. ISBN 0-471-11709-9 .

[FIPS-186-2] «FIPS PUB 186: Стандарт цифровой подписи (DSS), 19 мая 1994 г.» . qcsrc.nist.gov . Архивировано из оригинала 13 декабря 2013 г.

[FIPS-186-4-3] Jump up to: ^а ^б ^с ^д «FIPS PUB 186-4: Стандарт цифровой подписи (DSS), июль 2013 г.» (PDF) . csrc.nist.gov .

[FIPS-186-1-4] «FIPS PUB 186-1: Стандарт цифровой подписи (DSS), 15 декабря 1998 г.» (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 26 декабря 2013 г.

[FIPS-186-2-5] «FIPS PUB 186-2: Стандарт цифровой подписи (DSS), 27 января 2000 г.» (PDF) . csrc.nist.gov .

[FIPS-186-3-6] «FIPS PUB 186-3: Стандарт цифровой подписи (DSS), июнь 2009 г.» (PDF) . csrc.nist.gov .

[FIPS-186-5-7] «FIPS PUB 186-5: Стандарт цифровой подписи (DSS), февраль 2023 г.» (PDF) . csrc.nist.gov .

[8] «Стандарт цифровой подписи (DSS)» . Министерство торговли США. 31 октября 2019 года . Проверено 21 июля 2020 г.

[9] Доктор Дэвид В. Кравиц. Архивировано 9 января 2013 г., в Wayback Machine.

[10] Вернер Кох. «DSA и патенты»

[11] «Годовой отчет CSSPAB за 1994 год» . 26 августа 2009 г. Архивировано из оригинала 26 августа 2009 г.

[12] Нойманн, Питер Г. (29 февраля 2020 г.). «Дайджест RISKS, том 14, выпуск 59» . Архивировано из оригинала 29 февраля 2020 г. Проверено 3 октября 2023 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[13] «OpenSSH объявляет график удаления DSA [LWN.net]» . lwn.net . Проверено 11 января 2024 г.

[FIPS-180-4-14] «FIPS PUB 180-4: Стандарт безопасного хеширования (SHS), март 2012 г.» (PDF) . csrc.nist.gov .

[15] «Специальная публикация NIST 800-57» (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 6 июня 2014 г.

[16] «Катастрофа Debian PGP, которая почти случилась» . корневые лаборатории rdist . 18 мая 2009 г.

[17] ДСА $k$ -значение Требования

[18] Бендель, Майк (29 декабря 2010 г.). «Хакеры описывают безопасность PS3 как эпический провал: получите неограниченный доступ» . Exophase.com . Проверено 5 января 2011 г.

[19] Вербюхельн, Стефан (2 января 2015 г.). «Как идеальные офлайн-кошельки все еще могут утекать приватные ключи Биткойнов». arXiv : 1501.00447 [ cs.CR ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]