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). Поэтому эти параметры называют доменными параметрами (Domain Parameters).[5]

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

Подпись сообщения выполняется по следующему алгоритму[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. тогда открытый ключ [источник не указан 334 дня]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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