Алгоритм цифровой подписи - Digital Signature Algorithm

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

В Национальный институт стандартов и технологий (NIST) предложили DSA для использования в своем стандарте цифровой подписи (DSS) в 1991 году и приняли его как FIPS 186 в 1994 году.^[2] Было выпущено четыре версии исходной спецификации. Новейшая спецификация FIPS 186-4 с июля 2013 г.^[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 запрещает подписание с помощью DSA, но разрешает проверку подписей, созданных до даты внедрения стандарта в качестве документа. Он должен быть заменен более новыми схемами подписи, такими как EdDSA.^[7]

DSA покрывается Патент США 5231668 , поданной 26 июля 1991 г., срок действия которой истек, приписывается Дэвиду В. Кравицу,^[8] бывший АНБ наемный рабочий. Этот патент был выдан "Соединенным Штатам Америки в лице Министр торговли, Вашингтон, округ Колумбия ", и NIST сделали этот патент доступным во всем мире без лицензионных отчислений.^[9] Клаус П. Шнорр утверждает, что его Патент США 4,995,082 (срок действия также истек) покрытые суточные; это требование оспаривается.^[10]

Операция

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

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

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

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

• Выберите одобренный криптографическая хеш-функция ${\displaystyle H}$ с выходной длиной ${\displaystyle |H|}$ биты. В исходном DSS ${\displaystyle H}$ всегда был SHA-1, но тем сильнее SHA-2 хэш-функции одобрены для использования в текущем DSS.^[3][11] Если ${\displaystyle |H|}$ больше, чем длина модуля ${\displaystyle N}$, только крайний левый ${\displaystyle N}$ используются биты хеш-вывода.
• Выберите длину ключа ${\displaystyle L}$. Исходный DSS ограничен ${\displaystyle L}$ быть кратным 64 от 512 до 1024 включительно. NIST 800-57 рекомендует длину 2048 (или 3072) для ключей со сроком службы безопасности, превышающим 2010 (или 2030).^[12]
• Выберите длину модуля ${\displaystyle N}$ такой, что ${\displaystyle N<L}$ и ${\displaystyle N\leq |H|}$. FIPS 186-4 указывает ${\displaystyle L}$ и ${\displaystyle N}$ иметь одно из значений: (1024, 160), (2048, 224), (2048, 256) или (3072, 256).^[3]
• Выберите ${\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}$ это открытый ключ.

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

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

Подписание

Сообщение ${\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}$.

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

Можно убедиться, что подпись ${\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~({\text{mod}}~p)}$ у нас есть

${\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 энтропия, секретность и уникальность значения случайной подписи ${\displaystyle k}$ критичны. Это настолько важно, что нарушение любого из этих трех требований может раскрыть злоумышленнику весь закрытый ключ.^[13] Использование одного и того же значения дважды (даже при сохранении ${\displaystyle k}$ secret), используя предсказуемое значение, или даже несколько битов ${\displaystyle k}$ в каждой из нескольких подписей достаточно, чтобы раскрыть закрытый ключ ${\displaystyle x}$.^[14]

Эта проблема затрагивает как DSA, так и ECDSA - в декабре 2010 г. группа, называющая себя fail0verflow объявил о восстановлении ECDSA закрытый ключ, используемый Sony подписать программное обеспечение для PlayStation 3 игровая консоль. Атака стала возможной, потому что Sony не удалось сгенерировать новый случайный ${\displaystyle k}$ за каждую подпись.^[15]

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

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

Реализации

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

• Ботан
• Надувной Замок
• cryptlib
• Крипто ++
• libgcrypt
• Крапива
• OpenSSL
• волк
• GnuTLS

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

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

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

1. Шнайер, Брюс (1996). Прикладная криптография. ISBN  0-471-11709-9.
2. "FIPS PUB 186: Стандарт цифровой подписи (DSS), 1994-05-19". qcsrc.nist.gov. Архивировано из оригинал 13 декабря 2013 г.
3. «FIPS PUB 186-4: Стандарт цифровой подписи (DSS), июль 2013 г.» (PDF). csrc.nist.gov.
4. "FIPS PUB 186-1: Стандарт цифровой подписи (DSS), 1998-12-15" (PDF). csrc.nist.gov. Архивировано из оригинал (PDF) на 2013-12-26.
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. «Стандарт цифровой подписи (DSS)». Министерство торговли США. 31 октября 2019 г.. Получено 21 июля 2020.
8. Д-р Дэвид В. Кравиц В архиве 9 января 2013 г. Wayback Machine
9. Вернер Кох. «DSA и патенты»
10. . 26 августа 2009 г. https://web.archive.org/web/20090826042831/http://csrc.nist.gov/groups/SMA/ispab/documents/94-rpt.txt. Архивировано из оригинал 26 августа 2009 г. Отсутствует или пусто | название = (помощь)
11. «FIPS PUB 180-4: Стандарт безопасного хеширования (SHS), март 2012 г.» (PDF). csrc.nist.gov.
12. «Специальная публикация NIST 800-57» (PDF). csrc.nist.gov. Архивировано из оригинал (PDF) на 2014-06-06.
13. «Катастрофа Debian PGP, которая почти закончилась». root labs rdist.
14. DSA ${\displaystyle k}$-value Требования
15. Бендель, Майк (29 декабря 2010). «Хакеры описывают безопасность PS3 как эпический провал, получают неограниченный доступ». Exophase.com. Получено 2011-01-05.
16. Вербюхельн, Стефан (2 января 2015 г.). «Как совершенные офлайн-кошельки все еще могут пропускать секретные ключи биткойнов». arXiv:1501.00447 [cs.CR ].

внешняя ссылка

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