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

Стандарт цифровой верификации

Алгоритм цифровой подписи ( 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] FIPS 186–2 в 2000 году, ^{[5] ]} FIPS 186–3 в 2009 г., ^[6] FIPS 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. Генерация ключей

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

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

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

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

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

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

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

${\displaystyle x}$является закрытым ключом и является открытым ключом. ${\displaystyle y}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку есть порядок, у нас есть ${\displaystyle g}$ ${\displaystyle q}$

${\displaystyle {\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 следует из

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

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

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

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

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

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

Реализации

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

• Ботан
• Надувной замок
• криптлиб
• Крипто++
• libgcrypt
• Крапива
• OpenSSL
• волкСклеп
• ГнуTLS

Смотрите также

• Модульная арифметика
• RSA (криптосистема)
• ECDSA

Рекомендации

1. Шнайер, Брюс (1996). Прикладная криптография. Уайли. ISBN 0-471-11709-9.
2. «FIPS PUB 186: Стандарт цифровой подписи (DSS), 19 мая 1994 г.» . qcsrc.nist.gov . Архивировано из оригинала 13 декабря 2013 г.
3. «FIPS PUB 186-4: Стандарт цифровой подписи (DSS), июль 2013 г.» (PDF) . csrc.nist.gov .
4. «FIPS PUB 186-1: Стандарт цифровой подписи (DSS), 15 декабря 1998 г.» (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 26 декабря 2013 г.
5. «FIPS PUB 186-2: Стандарт цифровой подписи (DSS), 27 января 2000 г.» (PDF) . csrc.nist.gov .
6. «FIPS PUB 186-3: Стандарт цифровой подписи (DSS), июнь 2009 г.» (PDF) . csrc.nist.gov .
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 г.). «Дайджест РИСКОВ, том 14, выпуск 59». Архивировано из оригинала 29 февраля 2020 г. Проверено 03 октября 2023 г.{{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
13. «OpenSSH объявляет график удаления DSA [LWN.net]» . lwn.net . Проверено 11 января 2024 г.
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. DSA k {\displaystyle k} -значение Требования
18. Бендель, Майк (29 декабря 2010 г.). «Хакеры описывают безопасность PS3 как эпический провал: получите неограниченный доступ» . Exophase.com . Проверено 5 января 2011 г.
19. Вербюхельн, Стефан (2 января 2015 г.). «Как идеальные офлайн-кошельки все еще могут утекать приватные ключи Биткойнов». arXiv : 1501.00447 [cs.CR].

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

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