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

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

Национальный институт стандартов и технологий (NIST) предложил DSA для использования в их цифровой подписи Standard (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 защищена патентом США 5 231 668 , поданным 26 июля 1991 г., срок действия которого истек и приписывается Дэвиду В. Кравитцу ^[8], бывшему сотруднику NSA . Этот патент был выдан «Соединенным Штатам Америки в лице министра торговли Вашингтона, округ Колумбия», и NIST сделал этот патент доступным во всем мире без лицензионных отчислений. ^[9] Клаус П. Шнорр утверждает, что его патент США 4 995 082 (также истекший) распространяется на DSA; это требование оспаривается. ^[10]

Операция [ править ]

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

Генерация ключей [ править ]

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

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

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

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

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

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

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

Реализации [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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