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

редактировать

Алгоритм цифровой подписи (DSA ) является Федеральной информацией Стандарт обработки для цифровых подписей, основанный на математической концепции модульного возведения в степень и задачи дискретного логарифмирования. DSA - это вариант схем подписи Schnorr и ElGamal.

Национальный институт стандартов и технологий (NIST) предложил DSA для использования в своем стандарте цифровой подписи (DSS) в 1991 году и принял его как FIPS 186 в 1994 году. Было выпущено четыре версии исходной спецификации. Самая последняя спецификация - FIPS 186-4 от июля 2013 года. DSA запатентована, но NIST сделал этот патент доступным во всем мире без лицензионных отчислений. Черновая версия спецификации FIPS 186-5 указывает, что DSA больше не будет утверждаться для генерации цифровой подписи, но может использоваться для проверки подписей, созданных до даты реализации этого стандарта.

Содержание

1 Обзор
2 История
3 Операция
- 3.1 Генерация ключей
  - 3.1.1 Генерация параметров
  - 3.1.2 Индивидуальные ключи
- 3.2 Распределение ключей
- 3.3 Подпись
- 3.4 Проверка подписи
4 Корректность алгоритма
5 Чувствительность
6 Реализации
7 См. Также
8 Ссылки
9 Внешние ссылки

Обзор

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

История

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

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

Операция

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

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

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

Создание параметров

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

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

Пользовательские ключи

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

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

$x {\ displaystyle x}$ $x$ - закрытый ключ, а $y {\ displaystyle y}$ $y$ - открытый ключ.

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

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

Подписание

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

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

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

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

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

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

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

Правильность алгоритма

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

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

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

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

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

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

k ≡ H (m) s - 1 + xrs - 1 ≡ H (m) w + xrw (mod q) {\ displaystyle {\ begin { выровнено} k \ Equiv H (m) s ^ {- 1} + xrs ^ {- 1} \\ \ Equiv H (m) w + xrw {\ pmod {q}} \ end {align}}}

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

Поскольку $g {\ displaystyle g}$ $g$ имеет порядок $q (mod p) {\ displaystyle q ~ ({\ text {mod}} ~ p)}$ ${\ displaystyle q ~ ({\ text {mod}} ~ p)}$ у нас есть

gk ≡ g H (m) wgxrw ≡ g H (m) wyrw ≡ gu 1 yu 2 (mod p) {\ displaystyle {\ begin {align} 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 {align}}}

{\ displaystyle {\ begin {align} 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 {align}}}

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

r = (gk mod p) mod q = (gu 1 yu 2 mod p) mod q = v {\ displaystyle {\ begin {align} r = (g ^ {k} {\ bmod {\,}} p) {\ bmod {\,}} q \\ = (g ^ {u_ {1}} y ^ {u_ {2}} {\ bmod {\,}} p) {\ bmod {\,}} q \\ = v \ end {align}}}

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

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

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

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

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

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

Реализации

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

См. также

Ссылки

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

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