DSA
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 включает в себя два алгоритма (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]. Для работы системы требуется база соответствия между реальными реквизитами автора (это может быть как частное лицо, так и организация) и открытыми ключами, а также всеми необходимыми параметрами схемы цифровой подписи (хеш-функция, простые числа). Например, подобной базой может служить центр сертификации. Параметры схемы цифровой подписиДля построения системы цифровой подписи нужно выполнить следующие шаги:
Как упомянуто выше, первоочередным параметром схемы цифровой подписи является используемая криптографическая хеш-функция, необходимая для преобразования текста сообщения в число, для которого и вычисляется подпись. Важной характеристикой этой функции является битовая длина выходной последовательности, обозначаемая далее N. В первой версии стандарта DSS рекомендована функция SHA-1[2] и, соответственно, битовая длина подписываемого числа 160 бит. Сейчас SHA-1 уже не является достаточно безопасной[8][9]. В стандарте указаны следующие возможные пары значений чисел L и N:
В соответствии с этим стандартом рекомендованы хеш-функции семейства 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). Подпись сообщенияПодпись сообщения выполняется по следующему алгоритму[5]:
Вычислительно сложные операции это возведение в степень по модулю (вычисление ), для которого существуют быстрые алгоритмы, вычисление хеша , где сложность зависит от выбранного алгоритма хеширования и размера входного сообщения, и нахождение обратного элемента используя, например, расширенный алгоритм Евклида или малую теорему Ферма в виде . Проверка подписиПроверка подписи выполняется по алгоритму[5]: 1 Вычисление 2 Вычисление 3 Вычисление 4 Вычисление 5 Подпись верна, если При проверке вычислительно сложные операции это два возведения в степень , вычисление хеша и нахождение обратного элемента . Корректность схемыДанная схема цифровой подписи корректна в той степени, что желающий проверить подлинность подписи всегда получит положительный результат в случае подлинности. Покажем это: Во-первых, если , то из этого по Малой теореме Ферма следует . Поскольку g>1 и q простое число, то g должно иметь мультипликативный порядок q по модулю p. Для подписи сообщения вычисляется Из этого следует Так как g имеет порядок q, получим Наконец, корректность схемы DSA следует из Пример работыПриведем пример работы алгоритма для небольших чисел. Пусть значение хеш - функции нашего сообщения . Генерация параметров
Создание ключей
Подпись сообщения
Проверка подписи
АналогиАлгоритм 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 состоит из нескольких модулей проверки на соответствие стандарту, которые тестируют каждый компонент системы независимо от других. Тестируемые компоненты реализации:
Для проверки реализации разработчик должен подать заявку на тестирование его реализации в CMT laboratory (англ. Cryptographic Module Testing Laboratory - лаборатория тестирования криптографических модулей).[5] Генерация простых чиселПри работе алгоритма DSA требуется два простых числа ( и ), следовательно необходим генератор простых или псевдопростых чисел. Для генерации простых чисел используется алгоритм Шо-Тейлора[20]. Псевдопростые числа генерируются с помощью хеш-функции и для проверки на простоту используется вероятностный тест Миллера — Рабина. К нему может добавляться одиночный тест простоты Люка.[5] Необходимое число итераций зависит от длины используемых чисел и от алгоритма проверки[5]:
Генерация случайных чиселДля работы алгоритма требуется также генератор случайных или псевдослучайных чисел. Этот генератор нужен для создания частного пользовательского ключа x, а также для создания секретного случайного параметра . Cтандарт предлагает различные способы генерации псевдослучайных чисел используя блочные шифры или хеш-функции.[5][21] Примечания
ЛитератураСтандарты и патенты
Статьи
|