Алгоритм цифровой Подписи
Алгоритм цифровой подписи (DSA) - федеральный стандарт обработки информации для цифровых подписей, основанный на математической концепции модульного возведения в степень и задаче дискретного логарифма. DSA-это вариант сигнатурных схем Шнорра и Эльгамаля.
Национальный институт стандартов и технологий (NIST) предложил DSA для использования в своем стандарте цифровой подписи (DSS) в 1991 году и принял его как FIPS 186 в 1994 году. Новейшая спецификация-FIPS 186-4 от июля 2013 г. DSA запатентована, но NIST сделала этот патент доступным во всем мире без роялти. В черновой версии спецификации FIPS 186-5 указывается, что DSA больше не будет утверждаться для генерации цифровых подписей, но может использоваться для проверки подписей, созданных до даты внедрения этого стандарта.
Обзор[править]
Алгоритм 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,231,668 , поданным 26 июля 1991 года и теперь истекшим, и приписывается Дэвиду У. Кравитцу, бывшему сотруднику АНБ. Этот патент был выдан "Соединенным Штатам Америки в лице министра торговли, Вашингтон, Округ Колумбия", и NIST сделал этот патент доступным во всем мире без роялти. Клаус П. Шнорр утверждает, что его патент США 4995 082 (также теперь истек) охватывал DSA; эта претензия оспаривается.
Операция[править]
Алгоритм DSA включает в себя четыре операции: генерацию ключа (который создает пару ключей), распределение ключей, подписание и проверку подписи.
Генерация ключей[править]
Генерация ключей состоит из двух фаз. Первая фаза-это выбор параметров алгоритма, которые могут быть разделены между различными пользователями системы, в то время как вторая фаза вычисляет одну пару ключей для одного пользователя.
Генерация параметров[править]
- Выберите одобренную криптографическую хэш-функцию H Х с выходными | H | |H|} |H|битами длины. В исходном DSS H Хвсегда был SHA-1, но более сильные хэш-функции SHA-2 одобрены для использования в текущем DSS. Если | H | |H|длина модуля больше N Н, то используются только самые левые N Нбиты выходного хэша.
- Выберите длину ключа L Л. Исходная DSS ограничена L Лкратностью 64 между 512 и 1024 включительно. NIST 800-57 рекомендует длину ключей 2048 (или 3072) года для ключей со сроком службы безопасности, выходящим за пределы 2010 года (или 2030 года).]
- Выберите модуль длины N Нтакой N < L , чтобы N ≤ | H | }и. FIPS 186-4 определяет L Ли N } Нимеет одно из значений: (1024, 160), (2048, 224), (2048, 256), или (3072, 256).]
- Выберите N Н-битное простое q qчисло .
- Выберите L Л-битное простое p пчисло такое, чтобы p п− 1 было кратно q q.
- Выберите целое число h хслучайным образом { 2 … p − 2 }
- Вычислить g := h ( p − 1 ) / q mod p . В том редком случае, чтобы g = 1 g=1попробовать еще раз с другим h х. Обычно h = 2 h=2используется. Это модульное возведение в степень может быть эффективно вычислено даже при больших значениях.
Параметры алгоритма ( p п, q q, g г). Они могут быть разделены между различными пользователями системы.
Ключи для каждого пользователя[править]
Учитывая набор параметров, вторая фаза вычисляет пару ключей для одного пользователя:
- Выберите целое число x иксслучайным образом { 1 … q − 1 }
- Вычислить y := g x mod p .
x икс является закрытым ключом и y {\displaystyle y} yявляется открытым ключом.
Распределение ключей[править]
Подписавший должен опубликовать открытый ключ y y. То есть они должны передать ключ получателю через надежный, но не обязательно секретный механизм. Подписавший должен хранить секретный ключ x } иксв секрете.
Подпись[править]
Сообщение m мподписывается следующим образом:
- Выберите целое число k кслучайным образом из { 1 … q − 1 } {
- Вычислить r := ( g k mod p ) mod q . В том маловероятном случае , если это r = 0 r=0произойдет, начните снова с другого случайного k } к.
- Вычислить s := ( k − 1 ( H ( m ) + x r ) ) mod q }. В маловероятном случае этого s = 0 s=0, начните снова с другого случайного k к.
Подпись ( r , s )
Расчет k ки r { Рсумма для создания нового ключа для каждого сообщения. Модульное возведение в степень в вычислениях r Рявляется наиболее дорогостоящей частью операции подписи, но оно может быть вычислено до того, как сообщение станет известно. Вычисление модульного обратного k − 1 mod q \,qявляется второй по стоимости частью, и оно также может быть вычислено до того, как сообщение станет известно. Он может быть вычислен с использованием расширенного евклидова алгоритма или с использованием малой теоремы Ферма as k q − 2 mod q ,q.
Проверка подписи[править]
Можно проверить, что подпись ( r , s ) является действительной подписью для сообщения m } мследующим образом:
- Проверьте это 0 < r < q
- Вычислить w := s − 1 mod q
- Вычислить u 1 := H ( m ) ⋅ w mod q .
- Вычислить u 2 := r ⋅ w mod q
- Вычислить v := ( g u 1 y u 2 mod p ) mod q
- Подпись действительна тогда и только тогда, когда v = r v = r.
Корректность алгоритма[править]
Схема подписи верна в том смысле, что верификатор всегда будет принимать подлинные подписи. Это можно показать следующим образом:
Во-первых, поскольку g = h ( p − 1 ) / q mod p из этого следует g q ≡ h p − 1 ≡ 1 mod p \equiv 1\mod p}маленькая теоремаФерма . Так g > 0 g>0как и q qпервичен, g гдолжен иметь порядок q q.
Подписавший вычисляет
- s = k − 1 ( H ( m ) + x r ) mod q
Таким образом
- k ≡ H ( m ) s − 1 + x r s − 1 ≡ H ( m ) w + x r w ( mod q )
С g {\displaystyle g} гимеет заказ q {\displaystyle q} qмы имеем
- g k ≡ g H ( m ) w g x r w ≡ g H ( m ) w y r w ≡ g u 1 y u 2 ( mod p )
Наконец, правильность DSA следует из
- r = ( g k mod p ) mod q = ( g u 1 y u 2 mod p ) mod q = v
Чувствительность[править]
При использовании DSA энтропия, секретность и уникальность случайного значения сигнатуры k кимеют решающее значение. Это настолько важно, что нарушение любого из этих трех требований может раскрыть злоумышленнику весь закрытый ключ. Использование одного и того же значения дважды (даже при сохранении k ксекрета), использование предсказуемого значения или утечка даже нескольких битов k кв каждой из нескольких сигнатур достаточно для раскрытия закрытого ключа x икс.]
Эта проблема затрагивает как DSA, так и ECDSA – в декабре 2010 года группа, называющая себя fail0verflow, объявила о восстановлении закрытого ключа ECDSA, используемого Sony для подписи программного обеспечения для игровой консоли PlayStation 3. Эта атака стала возможной благодаря тому, что Sony не смогла сгенерировать новый случайный k ккод для каждой сигнатуры.]
Эта проблема может быть предотвращена k кдетерминированным выводом из закрытого ключа и хэша сообщения, как описано ниже. RFC 6979. Это гарантирует, что k кон будет разным для каждого H ( m ) H(m)и непредсказуемым для злоумышленников, которые не знают секретного ключа x икс.
Кроме того, вредоносные реализации DSA и ECDSA могут быть созданы там, где k кэто выбрано для подсознательной утечки информации через сигнатуры. Например, автономный закрытый ключ может быть утечен с идеального автономного устройства, которое выпускает только невинные на вид подписи.
Реализации[править]
Ниже приведен список криптографических библиотек, обеспечивающих поддержку DSA: