Алгоритмы ЭЦП. Алгоритм цифровой подписи DSА

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

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

• Выбор хеш-функции H(x). Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в число

• Выбор большого простого числа q, размерность которого в битах совпадает с размерностью в битах значений хэш-функции H(x)

• Выбор простого числа p, такого, что (p-1) делится на q. Размерность p задаёт криптостойкость системы. Ранее рекомендовалась длина в 1024 бита. В данный момент для систем, которые должны быть стойкими до 2010 (2030) года, рекомендуется длина в 2048 (3072) бита.

• Выбор числа g такого, что его мультипликативный порядок по модулю p равен q. Для его вычисления можно воспользоваться формулой g = h^(p-1)mod p, где h — некоторое произвольное число, такое, что . В большинстве случаев значение h = 2 удовлетворяет этому требованию

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

• Выбор случайного числа

• Вычисление

• Вычисление

• Выбор другого k, если оказалось, что r=0 или s=0

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

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

• Вычисление

• Вычисление

• Вычисление

• Вычисление

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