Контроль Разума
Advertisement

DSA (Digital Signature Algorithm) — алгоритм с использованием открытого ключа для создания электронной подписи, но не для шифрования. Секретное создание хеш-значения и публичная проверка её — только один человек может создать хеш-значение сообщения, но любой может проверить её корректность. Основан на вычислительной сложности взятия логарифмов в конечных полях.

Алгоритм был предложен Национальным Институтом Стандартов и Технологий (США) в августе 1991 и является запатентованным U.S. Patent 5231668 (англ.), но НИСТ сделал этот патент доступным для использования без лицензионных отчислений.

Выбор параметров[]

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

Параметры алгоритма[]

  1. Выбор хеш-функции H(x). Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в число
  2. Выбор большого простого числа q, размерность которого в битах совпадает с размерностью в битах значений хэш-функции H(x)
  3. Выбор простого числа p, такого, что (p-1) делится на q. Размерность p задаёт криптостойкость системы. Ранее рекомендовалась длина в 1024 бита. В данный момент для систем, которые должны быть стойкими до 2010 (2030) года, рекомендуется длина в 2048 (3072) бита.
  4. Выбор числа g такого, что его мультипликативный порядок по модулю p равен q. Для его вычисления можно воспользоваться формулой , где h — некоторое произвольное число, такое, что . В большинстве случаев значение h = 2 удовлетворяет этому требованию

Генерация открытого и закрытого ключа[]

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

Открытыми параметрами являются числа (p, q, g, y). Закрытый параметр только один — число x.

Подпись сообщения[]

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

  1. Выбор случайного числа
  2. Вычисление
  3. Вычисление
  4. Выбор другого k, если оказалось, что r=0 или s=0

Подписью является пара чисел (r, s)

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

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

  1. Вычисление
  2. Вычисление
  3. Вычисление
  4. Вычисление

Подпись верна, если v = r

См. также[]

cs:Digital Signature Algorithm de:Digital Signature Algorithm en:Digital Signature Algorithm es:DSA fa:الگوریتم امضای رقومی fi:DSA fr:Digital Signature Algorithm he:Digital Signature Algorithm it:Digital Signature Algorithm lt:DSA pl:Digital Signature Algorithm pt:DSS ro:Algoritm pentru Semnături Digitale vi:Giải thuật ký số

Advertisement