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

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

Алгоритм цифровой подписи ( 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, а NSA. ^[12]

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

Операция

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

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

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

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

• Выберите одобренную криптографическую хэш-функцию с длиной выходных данных бит. В исходном DSS всегда был SHA-1 , но в текущем DSS одобрены для использования более сильные хэш-функции SHA-2 . ^{[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
• wolfCrypt
• GnuTLS

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

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

Ссылки

1. Schneier, Bruce (1996). Прикладная криптография. Wiley. ISBN 0-471-11709-9.
2. "FIPS PUB 186: Стандарт цифровой подписи (DSS), 1994-05-19". qcsrc.nist.gov . Архивировано из оригинала 2013-12-13.
3. "FIPS PUB 186-4: Стандарт цифровой подписи (DSS), июль 2013 г." (PDF) . csrc.nist.gov .
4. "FIPS PUB 186-1: Стандарт цифровой подписи (DSS), 15.12.1998" (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 26.12.2013.
5. "FIPS PUB 186-2: Стандарт цифровой подписи (DSS), 2000-01-27" (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. "1994 Annual Report of CSSPAB". 26 августа 2009 г. Архивировано из оригинала 26 августа 2009 г.
12. Нойманн, Питер Г. (29.02.2020). "The RISKS Digest Volume 14 Issue 59". Архивировано из оригинала 29.02.2020 . Получено 03.10.2023 .{{cite web}}: CS1 maint: bot: original URL status unknown (link)
13. "OpenSSH объявляет о сроках удаления DSA [LWN.net]". lwn.net . Получено 11 января 2024 г. .
14. "FIPS PUB 180-4: Стандарт безопасного хэширования (SHS), март 2012 г." (PDF) . csrc.nist.gov .
15. "NIST Special Publication 800-57" (PDF) . csrc.nist.gov . Архивировано из оригинала (PDF) 2014-06-06.
16. "Катастрофа Debian PGP, которая едва не случилась". root labs rdist . 18 мая 2009 г.
17. Требования к значению DSA k {\displaystyle k}
18. Бендель, Майк (29.12.2010). «Хакеры описывают безопасность PS3 как эпический провал, получают неограниченный доступ». Exophase.com . Получено 05.01.2011 .
19. Verbücheln, Stephan (2 января 2015 г.). «Как идеальные офлайн-кошельки все еще могут допускать утечку закрытых ключей Bitcoin». arXiv : 1501.00447 [cs.CR].

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

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