Стандарты на алгоритмы цифровой подписи
Во многих странах сегодня существуют стандарты на электронную (цифровую) подпись. Стандарт цифровой подписи DSS (Digital Signature Standard — DSS) был принят в США в 1991 году и пересмотрен в 1994 году. В основе стандарта лежит алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией подписи Эль-Гамаля. В алгоритме используется однонаправленная хеш-функция H(m). В качестве хэш-алгоритма стандарт DSS предусматривает использование алгоритма SHA-1.
- параметр р должен быть простым числом длиной от 512 до 1024 бит.
-
q — простое число длиной 160 бит; между p и q должно выполняться соотношение p = bq + 1 для некоторого целого b. Старшие биты в р и q должны быть равны единице (таким образом 2159 < q < 2160 ). - число а, удовлетворяющее неравенству 1 < a < p-1 и являющееся корнем уравнения aq mod p = 1.
Число х будет секретным ключом пользователя, а число у — открытым ключом. Вычислить у по известному х довольно просто. Однако, имея открытый ключ у, вычислительно невозможно определить х, который является дискретным логарифмом у по основанию a.
Пусть имеется сообщение m, которое один из пользователей желает подписать. Для генерации подписи пользователь должен выполнить следующие действия:
В результате пользователь получит для сообщения m подпись, состоящую из пары чисел (r,s). Сообщение вместе с подписью может быть послано любому другому абоненту системы. Проверить подпись можно следующим образом:
В силу сложности вычисления дискретных логарифмов злоумышленник не может восстановить k из r или х из s, а следовательно, не может подделать подпись. По той же самой причине автор сообщения не сможет отказаться от своей подписи, так как никто кроме него не знает закрытого ключа х.
В России принят стандарт ГОСТ Р34.10-94 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма». В этом стандарте используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Рассмотрим вначале полностью алгоритм, описанный в ГОСТ Р34.10-94, а затем отметим его отличия от алгоритма DSA.
- параметр р должен быть простым числом длиной от 512 до 1024 бит. Старший бит в р должен быть равен единице.
-
q — простое число длиной 254-256 бит; так же как и в DSA, q должно быть делителем числа (р-1). Старший бит в q должен быть равен единице. - число а, удовлетворяющее неравенству 1 < a < p-1 и являющееся корнем уравнения aq mod p = 1.
- Затем каждый пользователь может сформировать закрытый и открытый ключи. В качестве закрытого ключа выбирается произвольное число х, 0 < x < q. Открытым ключом является число y, получаемое по формуле Для создания каждой новой подписи каждый раз выбирается новое случайное число k, 0 < k < q.
где H(m) — результат вычисления хеш-функции для сообщения m.
1. Перед вычислением подписи исходное сообщение обрабатывается разными функциями хеширования: в ГОСТ Р34.10-94 применяется отечественный стандарт на хеш-функцию ГОСТ Р34.11-94, в DSS используется SHA-1, которые имеют разную длину хеш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ Р34.10-94 длина q должна быть от 254 до 256 бит, а в DSS длина q должна быть от 159 до 160 бит.
а в DSS компонента s вычисляется по формуле
В результате процедура проверки подписи по ГОСТ Р34.10-94 заключается в следующем. Получив [m, (r, s)], получатель вычисляет
В алгоритме создания ЭЦП по ГОСТ Р34.10-94, так же как и в алгоритме DSS, производятся достаточно сложные вычисления, требующие затрат вычислительных ресурсов. Для ускорения процесса генерации подписей по этим алгоритмам можно заранее вычислять некоторое количество значений параметра r, не зависящего от подписываемого сообщения. Затем эти значения можно использовать по мере необходимости для подписи документов. Для алгоритма DSS заранее может вычисляться и значение k-1.
Источник