4.3.3. Алгоритм цифровой подписи dsa

Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритма цифровой подписи Эль Гамаля.

Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р – простые числа, L бит каждое (512 < L< 1024); q – простое число длиной 160 бит (делитель числа (Р – 1)). Числа G, P, q являются открытыми и могут быть общими для всех пользователей сети.

Отправитель выбирает случайное целое число X, 1< Х< q. Число X является секретным ключом отправителя для формирования электронной цифровой подписи.

Затем отправитель вычисляет значение . Число Y является открытым ключом для проверки подписи отправителя. Число Y передается всем получателям документов.

Этот алгоритм также предусматривает использование односторонней функции хэширования h( ). В стандарте DSS определен алгоритм безопасного хэширования SHA.

Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m = h(M), 1 < m < q, затем генерирует случайное целое число K, 1< K < q, и вычисляет число r = (G^K(mod P))(mod q). Затем отправитель вычисляет с помощью секретного ключа X целое число . Пара чисел r и s образует цифровую подпись S = (r, s) под документом М. Таким образом, подписанное сообщение представляет собой тройку чисел (М, r, s).

Получатель подписанного сообщения (М, r, s) проверяет выполнение условий 0 < r < q, 0 < s < q и отвергает подпись, если хотя бы одно из этих условий не выполнено.

Затем получатель вычисляет значение

,

хэш-значение m = h(M) и числа u₁ = mw (mod q), u₂ = mr (mod q).

Далее получатель с помощью открытого ключа Y вычисляет значение

и проверяет выполнение условия v = r.

Если условие v = r выполняется, тогда подпись S = (r, s) под документом М признается получателем подлинной.

По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSA имеет следующие основные преимущества:

1. При любом допустимом уровне стойкости, т.е. при любой паре чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.

2. Большинство операций с числами K, r, s, X при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.

3. При проверке подписи большинство операций с числами u₁, u₂, v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.

Недостатком алгоритма DSA является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q:

, ,

что не позволяет получать максимальное быстродействие.

Следует отметить, что реальное исполнение алгоритма DSA может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m. Можно заранее создать строку случайных значений K и затем для каждого из этих значений вычислить значения r. Можно также заранее вычислить обратные значения K^–1 для каждого из значений K. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и K^–1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSA.