Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 12 сентября 2016 года; проверки требуют 78 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 12 сентября 2016 года; проверки требуют 78 правок.
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].
Для работы системы требуется база соответствия между реальными реквизитами автора (это может быть как частное лицо, так и организация) и открытыми ключами, а также всеми необходимыми параметрами схемы цифровой подписи (хеш-функция, простые числа). Например, подобной базой может служить центр сертификации.
Выбор простого числа q, размерность которого N в битах совпадает с размерностью в битах значений хеш-функции H(x).
Выбор простого числа p, такого, что (p-1) делится на q. Битовая длина p обозначается L.
Выбор числа g () такого, что его мультипликативный порядок по модулюp равен q. Для его вычисления можно воспользоваться формулой , где h — некоторое произвольное число, такое, что . В большинстве случаев значение h = 2 удовлетворяет этому требованию.[5]
Как упомянуто выше, первоочередным параметром схемы цифровой подписи является используемая криптографическая хеш-функция, необходимая для преобразования текста сообщения в число, для которого и вычисляется подпись. Важной характеристикой этой функции является битовая длина выходной последовательности, обозначаемая далее N. В первой версии стандарта DSS рекомендована функция SHA-1[2] и, соответственно, битовая длина подписываемого числа 160 бит. Сейчас SHA-1 уже не является достаточно безопасной[8][9]. В стандарте указаны следующие возможные пары значений чисел L и N:
L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256
В соответствии с этим стандартом рекомендованы хеш-функции семейства SHA-2. Правительственные организации США должны использовать один из первых трех вариантов, центры сертификации должны использовать пару, которая равна или превосходит пару, используемую подписчиками[5]. Проектирующий систему может выбрать любую допустимую хеш-функцию. Поэтому далее не будет заостряться внимание на использовании конкретной хеш-функции.
Стойкость криптосистемы на основе DSA не превосходит стойкость используемой хеш-функции и стойкость пары (L,N), чья стойкость не больше стойкости каждого из чисел по отдельности. Также важно учитывать, как долго система должна оставаться безопасной. В данный момент для систем, которые должны быть стойкими до 2010 (2030) года, рекомендуется длина в 2048 (3072) бита.[5][10]
Открытыми параметрами являются числа (p, q, g, y). Закрытый параметр только один — число x. При этом числа (p, q, g) могут быть общими для группы пользователей, а числа x и y являются соответственно закрытым и открытым ключами конкретного пользователя. При подписывании сообщения используются секретные числа x и k, причем число k должно выбираться случайным образом (на практике псевдослучайным) при вычислении подписи каждого следующего сообщения.
Поскольку (p, q, g) могут быть использованы для нескольких пользователей, на практике часто делят пользователей по некоторым критериям на группы с одинаковыми (p, q, g). f
Данная схема цифровой подписи корректна в той степени, что желающий проверить подлинность подписи всегда получит положительный результат в случае подлинности. Покажем это:
Алгоритм 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). Она заключается в том, что для подписи (либо вообще случайной, либо созданной по некоторому правилу) возможно создать корректное сообщение (которое, правда, обычно не несет смысла), используя только открытые параметры.
Для схемы DSA подпись , при любом корректна для сообщения с хешем .
Это одна из причин хеширования входного сообщения. При корректном выборе хеш-функции алгоритм DSA защищен от этой атаки, потому что обращение криптографической хеш-функции (т.е. для заданного нахождение такого, что ) является вычислительно сложной задачей.[18]
условие корректности подписи можно переписать в ином виде:
это уравнение эквивалентно (т.к. мультипликативный порядок g по модулю p равен q)
значит можно считать, что злоумышленнику для восстановления ключа требуется решить систему уравнений вида
но в этой системе неизвестен и все , значит число неизвестных на единицу больше, чем уравнений и при любом найдутся , удовлетворяющие системе. Так как q - большое простое число, то для восстановления потребуется экспоненциальное число пар (сообщение, подпись).[1]
Условия лицензии позволяют реализовывать алгоритм программно и аппаратно. НИСТ создал DSAVS[19] (англ.The Digital Signature Algorithm Validation System - система проверки алгоритма цифровой подписи). DSAVS состоит из нескольких модулей проверки на соответствие стандарту, которые тестируют каждый компонент системы независимо от других. Тестируемые компоненты реализации:
Генерация доменных параметров
Проверка доменных параметров
Генерация пары открытый-закрытый ключ
Создание подписи
Проверка подписи
Для проверки реализации разработчик должен подать заявку на тестирование его реализации в CMT laboratory (англ.Cryptographic Module Testing Laboratory - лаборатория тестирования криптографических модулей).[5]
При работе алгоритма DSA требуется два простых числа ( и ), следовательно необходим генератор простых или псевдопростых чисел.
Для генерации простых чисел используется алгоритм Шо-Тейлора[20].
Псевдопростые числа генерируются с помощью хеш-функции и для проверки на простоту используется вероятностный тест Миллера — Рабина. К нему может добавляться одиночный тест простоты Люка.[5]
Необходимое число итераций зависит от длины используемых чисел и от алгоритма проверки[5]:
Для работы алгоритма требуется также генератор случайных или псевдослучайных чисел. Этот генератор нужен для создания частного пользовательского ключа x, а также для создания секретного случайного параметра .
Cтандарт предлагает различные способы генерации псевдослучайных чисел используя блочные шифры или хеш-функции.[5][21]