 |
Алгоритм цифровой подписи DSA. Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 г
|
|
|
|
Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К. Шнорра.
Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р — простые числа, L бит каждое 
; q — простое число длиной 160 бит (делитель числа 
). Числа G, P, q являются открытыми и могут быть общими для всех пользователей сети.
Отправитель выбирает случайное целое число 
. Число X является секретным ключом отправителя для формирования электронной цифровой подписи.
Затем отправитель вычисляет значение
Число Y является открытым ключом для проверки подписи отправителя. Число Y передается всем получателям документов. Этот алгоритм также предусматривает использование односторонней функции хэширования 
. В стандарте DSS определен алгоритм безопасного хэширования SHA (Secure Hash Algorithm).
Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m:
затем генерирует случайное целое число 
и вычисляет число r:
Затем отправитель вычисляет с помощью секретного ключа X целое число s:
Пара чисел r и s образует цифровую подпись 
под документом М.
Таким образом, подписанное сообщение представляет собой тройку чисел 
.
Получатель подписанного сообщения проверяет выполнение условий
и отвергает подпись, если хотя бы одно из этих условий не выполнено.
Затем получатель вычисляет значение
хэш-значение
и числа
Далее получатель с помощью открытого ключа Y вычисляет значение
и проверяет выполнение условия
Если условие 
выполняется, тогда подпись под документом М признается получателем подлинной. Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом X (не раскрывая при этом значения ключа X) и что отправитель подписал именно данный документ М.
|
|
|
По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSA имеет следующие основные преимущества;
1. При любом допустимом уровне стойкости, т.е. при любой паре чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.
2. Большинство операций с числами К, r, s, X при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.
3. При проверке подписи большинство операций с числами и 
, 
, v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.
Недостатком алгоритма DSA является то, что при подписывания и при проверке подписи приходится выполнять сложные операции деления по модулю q:
что не позволяет получать максимальное быстродействие.
Следует отметить, что реальное исполнение алгоритма DSA может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m. Можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения r. Можно также заранее вычислить обратные значения 
для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и . Эти предварительные вычисления значительно ускоряют работу алгоритма DSA.
|
|
|
