Материал из РУВИКИ — свободной энциклопедии

DSA

DSA, Digital Signature Algorithm
Создатель NIST
Создан 1991 год
Опубликован 1998 год
Размер ключа закрытый: 160-256 бит, открытый: 1024-3072 бит
Размер подписи два числа по 160-256 бит

DSA (англ. Digital Signature Algorithm — алгоритм цифровой подписи) — криптографический алгоритм с использованием закрытого ключа (из пары ключей: <открытый; закрытый>) для создания электронной подписи, но не для шифрования (в отличие от RSA и схемы Эль-Гамаля). Подпись создается секретно (закрытым ключом), но может быть публично проверена (открытым ключом). Это означает, что только один субъект может создать подпись сообщения, но любой может проверить её корректность. Алгоритм основан на вычислительной сложности взятия логарифмов в конечных полях.

Алгоритм был предложен Национальным институтом стандартов и технологий (США) в августе 1991 и является запатентованным[1] (автор патента — David W. Kravitz), НИСТ сделал этот патент доступным для использования без лицензионных отчислений. DSA является частью DSS (англ. Digital Signature Standard — стандарт цифровой подписи), впервые опубликованного 15 декабря 1998 (документ FIPS-186[2] (англ. Federal Information Processing Standards — федеральные стандарты обработки информации)). Стандарт несколько раз обновлялся[3][4], последняя версия FIPS-186-4[5]. (июль 2013).

Описание алгоритма[править | править код]

иллюстрация работы DSA

DSA включает в себя два алгоритма (S, V): для создания подписи сообщения (S) и для ее проверки (V).

Оба алгоритма вначале вычисляют хеш сообщения, используя криптографическую хеш-функцию. Алгоритм S использует хеш и секретный ключ для создания подписи, алгоритм V использует хеш сообщения, подпись и открытый ключ для проверки подписи.

Стоит подчеркнуть, что фактически подписывается не сообщение (произвольной длины), а его хеш (160 - 256 бит), поэтому неизбежны коллизии и одна подпись, вообще говоря, действительна для нескольких сообщений с одинаковым хешем. Поэтому выбор достаточно "хорошей" хеш-функции очень важен для всей системы в целом. В первой версии стандарта использовалась хеш-функция SHA-1[6][2] (англ. Secure Hash Algorithm - безопасный алгоритм хеширования), в последней версии также можно использовать любой алгоритм семейства SHA-2[6][5]. В августе 2015 был опубликован FIPS-202[7], описывающий новую хеш-функцию SHA-3. Но на сегодняшний день она не включена в стандарт DSS[5].

Для работы системы требуется база соответствия между реальными реквизитами автора (это может быть как частное лицо, так и организация) и открытыми ключами, а также всеми необходимыми параметрами схемы цифровой подписи (хеш-функция, простые числа). Например, подобной базой может служить центр сертификации.

Параметры схемы цифровой подписи[править | править код]

Для построения системы цифровой подписи нужно выполнить следующие шаги:

  1. Выбор криптографической хеш-функции H(x).
  2. Выбор простого числа q, размерность которого N в битах совпадает с размерностью в битах значений хеш-функции H(x).
  3. Выбор простого числа p, такого, что (p-1) делится на q. Битовая длина p обозначается L.
  4. Выбор числа g () такого, что его мультипликативный порядок по модулю p равен q. Для его вычисления можно воспользоваться формулой , где h — некоторое произвольное число, такое, что . В большинстве случаев значение h = 2 удовлетворяет этому требованию.[5]

Как упомянуто выше, первоочередным параметром схемы цифровой подписи является используемая криптографическая хеш-функция, необходимая для преобразования текста сообщения в число, для которого и вычисляется подпись. Важной характеристикой этой функции является битовая длина выходной последовательности, обозначаемая далее N. В первой версии стандарта DSS рекомендована функция SHA-1[2] и, соответственно, битовая длина подписываемого числа 160 бит. Сейчас SHA-1 уже не является достаточно безопасной[8][9]. В стандарте указаны следующие возможные пары значений чисел L и N:

  1. L = 1024, N = 160
  2. L = 2048, N = 224
  3. L = 2048, N = 256
  4. L = 3072, N = 256

В соответствии с этим стандартом рекомендованы хеш-функции семейства SHA-2. Правительственные организации США должны использовать один из первых трех вариантов, центры сертификации должны использовать пару, которая равна или превосходит пару, используемую подписчиками[5]. Проектирующий систему может выбрать любую допустимую хеш-функцию. Поэтому далее не будет заостряться внимание на использовании конкретной хеш-функции.

Стойкость криптосистемы на основе DSA не превосходит стойкость используемой хеш-функции и стойкость пары (L,N), чья стойкость не больше стойкости каждого из чисел по отдельности. Также важно учитывать, как долго система должна оставаться безопасной. В данный момент для систем, которые должны быть стойкими до 2010 (2030) года, рекомендуется длина в 2048 (3072) бита.[5][10]

Открытый и секретный ключи[править | править код]

  1. Секретный ключ представляет собой число
  2. Открытый ключ вычисляется по формуле

Открытыми параметрами являются числа (p, q, g, y). Закрытый параметр только один — число x. При этом числа (p, q, g) могут быть общими для группы пользователей, а числа x и y являются соответственно закрытым и открытым ключами конкретного пользователя. При подписывании сообщения используются секретные числа x и k, причем число k должно выбираться случайным образом (на практике псевдослучайным) при вычислении подписи каждого следующего сообщения.

Поскольку (p, q, g) могут быть использованы для нескольких пользователей, на практике часто делят пользователей по некоторым критериям на группы с одинаковыми (p, q, g). f

Подпись сообщения[править | править код]

Подпись сообщения выполняется по следующему алгоритму[5]:

  1. Выбор случайного числа
  2. Вычисление
  3. Выбор другого k, если
  4. Вычисление
  5. Выбор другого k, если
  6. Подписью является пара общей длины

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

Проверка подписи[править | править код]

Проверка подписи выполняется по алгоритму[5]:

1 Вычисление 
2 Вычисление 
3 Вычисление 
4 Вычисление 
5 Подпись верна, если 

При проверке вычислительно сложные операции это два возведения в степень , вычисление хеша и нахождение обратного элемента .

Корректность схемы[править | править код]

Данная схема цифровой подписи корректна в той степени, что желающий проверить подлинность подписи всегда получит положительный результат в случае подлинности. Покажем это:

Во-первых, если , то из этого по Малой теореме Ферма следует . Поскольку g>1 и q простое число, то g должно иметь мультипликативный порядок q по модулю p.

Для подписи сообщения вычисляется

Из этого следует

Так как g имеет порядок q, получим

Наконец, корректность схемы DSA следует из

[5]

Пример работы[править | править код]

Приведем пример работы алгоритма для небольших чисел. Пусть значение хеш - функции нашего сообщения .

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

  1. длина хеша , значит можно выбрать
  2. выберем , так как
  3. выберем

Создание ключей[править | править код]

  1. в качестве секретного ключа выберем
  2. тогда открытый ключ

Подпись сообщения[править | править код]

  1. выберем
  2. тогда
  3. , идем дальше
  4. , где учтено, что
  5. , идем дальше
  6. подписью является пара чисел

Проверка подписи[править | править код]

  1. получили, что , значит подпись верна.

Аналоги[править | править код]

Алгоритм DSA основывается на трудности вычисления дискретных логарифмов и является модификацией классической схемы Эль-Гамаля[11], где добавлено хеширование сообщения, а также все логарифмы вычисляются по , что позволяет сделать подпись короче по сравнению с аналогами [12]. На основе схемы Эль-Гамаля построены и другие алгоритмы, например - российский ГОСТ 34.10-94, который сейчас считается устаревшим. На смену ему пришел стандарт ГОСТ Р 34.10-2012[13], в котором используется группа точек эллиптической кривой.

Подобная модификация, т.е. переход от мультипликативной группы по модулю простого числа к группе точек эллиптической кривой существует и для DSA - ECDSA[14] ( англ. Elliptic Curve Digital Signature Algorithm - алгоритм цифровой подписи на эллиптических кривых). Он применяется, например, в криптовалюте bitcoin для подтверждения транзакций. Этот перевод позволяет уменьшить размер ключей без ущерба для безопасности - в системе bitcoin размер закрытого ключа 256 бит, а соответствующего ему открытого - 512 бит.

Другой распространенный алгоритм с открытым ключом (используется и для шифрования, и для цифровой подписи), RSA (назван в честь авторов: РивестШамир, Адлеман), основан на сложности факторизации больших чисел.

Криптографическая стойкость[править | править код]

Любую атаку на алгоритм можно описать так: злоумышленник получает все открытые параметры подписи и некий набор пар (сообщение, подпись) и пытается, используя этот набор, создать действительную подпись для нового сообщения, не представленного в наборе.

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

Предсказуемость случайного параметра[править | править код]

Равномерное распределение случайного параметра очень важно для безопасности системы. Если известны несколько последовательных бит параметра для ряда подписей, то секретный ключ возможно восстановить с высокой вероятностью.[15]

Повторение параметра для двух сообщений ведет к простому взлому системы. Это может произойти при использовании плохого генератора псевдослучайных чисел. Данная уязвимость в системе PlayStation 3 позволяла подписывать от имени Sony любые программы. В некоторых реализациях системы bitcoin для Android злоумышленник мог получить доступ к кошельку.[16][17] В обоих примерах использовалась система ECDSA[14].

Если для двух сообщений использовался один и тот же параметр , тогда их подписи будут иметь одинаковые , но разные , назовем их .

Из выражения для можно выразить общий :

.

И приравнять общий для разных сообщений:

Отсюда легко выразить секретный ключ :

Existential forgery[править | править код]

На некоторые алгоритмы цифровой подписи возможна атака существующей подделки (Existential forgery). Она заключается в том, что для подписи (либо вообще случайной, либо созданной по некоторому правилу) возможно создать корректное сообщение (которое, правда, обычно не несет смысла), используя только открытые параметры.

Для схемы DSA подпись , при любом корректна для сообщения с хешем .

Это одна из причин хеширования входного сообщения. При корректном выборе хеш-функции алгоритм DSA защищен от этой атаки, потому что обращение криптографической хеш-функции (т.е. для заданного нахождение такого, что ) является вычислительно сложной задачей.[18]

Восстановление ключа[править | править код]

условие корректности подписи можно переписать в ином виде:

это уравнение эквивалентно (т.к.  мультипликативный порядок g  по модулю p равен q)

значит можно считать, что злоумышленнику для восстановления ключа требуется решить систему уравнений вида

но в этой системе неизвестен и все , значит число неизвестных на единицу больше, чем уравнений и при любом найдутся , удовлетворяющие системе. Так как q - большое простое число, то для восстановления потребуется экспоненциальное число пар (сообщение, подпись).[1]

Подделка подписи[править | править код]

Можно попытаться подделать подпись, не зная секретный ключ, то есть попытаться решить уравнение

относительно и . При каждом фиксированном уравнение эквивалентно вычислению дискретного логарифма.[1]

Система проверки реализации алгоритма[править | править код]

Условия лицензии позволяют реализовывать алгоритм программно и аппаратно. НИСТ создал DSAVS[19] (англ. The Digital Signature Algorithm Validation System - система проверки алгоритма цифровой подписи). DSAVS состоит из нескольких модулей проверки на соответствие стандарту, которые тестируют каждый компонент системы независимо от других. Тестируемые компоненты реализации:

  1. Генерация доменных параметров
  2. Проверка доменных параметров
  3. Генерация пары открытый-закрытый ключ
  4. Создание подписи
  5. Проверка подписи

Для проверки реализации разработчик должен подать заявку на тестирование его реализации в CMT laboratory (англ. Cryptographic Module Testing Laboratory  - лаборатория тестирования криптографических модулей).[5]

Генерация простых чисел[править | править код]

При работе алгоритма DSA требуется два простых числа ( и ), следовательно необходим генератор простых или псевдопростых чисел.

Для генерации простых чисел используется алгоритм Шо-Тейлора[20].

Псевдопростые числа генерируются с помощью хеш-функции и для проверки на простоту используется вероятностный тест Миллера — Рабина. К нему может добавляться одиночный тест простоты Люка.[5]

Необходимое число итераций зависит от длины используемых чисел и от алгоритма проверки[5]:

параметры только М-Р тест М-Р тест + тест Люка
p: 1024 бит

q: 160 бит

вероятность ошибки

40 р: 3

q: 19

p: 2048 бит

q: 224 бит

вероятность ошибки

56 р: 3

q: 24

p: 2048 бит

q: 256 бит

вероятность ошибки

56 р: 3

q: 27

p: 3072 бит

q: 256 бит

вероятность ошибки

64 р: 2

q: 27

Генерация случайных чисел[править | править код]

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

Cтандарт предлагает различные способы генерации псевдослучайных чисел используя блочные шифры или хеш-функции.[5][21]

Примечания[править | править код]

Литература[править | править код]

Стандарты и патенты[править | править код]

Статьи[править | править код]