Алгоритм цифровой подписи DSА (Digital Signature Algorithm) предложен в 1991 г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSА является развитием алгоритмов цифровой подписи Эль Гамаля и К.Шнорра.
Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р - простые числа, L бит каждое (512 £ L £ 1024); q - простое число длиной 160 бит (делитель числа (Р-1)). Числа G, Р, q являются открытыми и могут быть общими для всех пользователей сети.
Отправитель выбирает случайное целое число X, 1 < Х < q. Число Х является секретным ключом отправителя для формирования электронной цифровой подписи.
Затем отправитель вычисляет значение
Y = GX mod Р.
Число Y является открытым ключом для проверки подписи отправителя и передается всем получателям документов.
Этот алгоритм также предусматривает использование односторонней функции хэширования h(·).
В стандарте DSS определен алгоритм безопасного хэширования SНА (Secure Hash Algorithm).
Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m:
m = h(М), 1<m<q ,
затем генерирует случайное целое число К, 1< К< q, и вычисляет число r:
r = (GK mod Р) mod q .
Затем отправитель вычисляет с помощью секретного ключа Х целое число s:
s = ((m + r * X)/K) mod q .
Пара чисел (r,s) образует цифровую подпись
S = (r,s)
под документом М.
Таким образом, подписанное сообщение представляет собой тройку чисел (М,r,s).
Получатель подписанного сообщения (М,r,s) проверяет выполнение условий
0 < r < q, 0 < s < q
и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение
w = (1/s) mod q ,
хэш-значение
m = h(М)
и числа
u1 = (m * w) mod q , u2 = (r * w) mod q .
Далее получатель с помощью открытого ключа Y вычисляет значение
v = ((Gu1 * Yu2 ) mod Р) mod q
и проверяет выполнение условия
v = r .
Если условие v = r выполняется, тогда подпись S=(r,s) под документом М признается получателем подлинной.
Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(r,s) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом Х (не раскрывая при этом значения ключа X) и что отправитель подписал именно данный документ М.
По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSА имеет следующие основные преимущества:
1. При любом допустимом уровне стойкости, т.е. при любой паре чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.
2. Большинство операций с числами К, r, s, Х при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.
3. При проверке подписи большинство операций с числами u1, u2, v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.
Недостатком алгоритма DSА является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q:
s = ((m + rX)/K) (mod q), w = (1/s) (mod q) ,
что не позволяет получать максимальное быстродействие.
Следует отметить, что реальное исполнение алгоритма DSА может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m. Можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения r. Можно также заранее вычислить обратные значения К-1 для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и К-1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSА.
4. ОТЕЧЕСТВЕННЫЙ СТАНДАРТ ЦИФРОВОЙ ПОДПИСИ
Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSА.
В нем используются следующие параметры:
р - большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит; q - простой сомножитель числа (р-1), имеющий длину 254...256 бит; а - любое число, меньшее (р-1), причем такое, что аq mod p = 1; х - некоторое число, меньшее q; у = аx mod р.
Кроме того, этот алгоритм использует однонаправленную хэш-функцию Н(х). Стандарт ГОСТ Р 34.11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.
Первые три параметра р, q, а являются открытыми и могут быть общими для всех пользователей сети. Число х является секретным ключом. Число у является открытым ключом. Чтобы подписать некоторое сообщение m, а затем проверить подпись, выполняются следующие шаги.
1. Пользователь А генерирует случайное число k, причем k < q.
2. Пользователь А вычисляет значения
r = (аk mod p) mod p , s = (х * r + k (Н(m))) mod p .
Если Н(m) mod q = 0, то значение Н(m) mod q принимают равным единице. Если r=0, то выбирают другое значение k и начинают снова. Цифровая подпись представляет собой два числа:
r mod 2256 и s mod 2256 .
Пользователь А отправляет эти числа пользователю В.
3. Пользователь В проверяет полученную подпись, вычисляя
v = Н(m)q-2 mod q , z1 = (s * v) mod q , z2 = ((q-r) * v) mod q , u = ((аz1 * уz2 ) mod р) mod p .
4. Если u = r, то подпись считается верной.
Различие между этим алгоритмом и алгоритмом DSА заключается в том, что в DSА
s = (k-1 (х * r + (Н(m)))) mod q ,
что приводит к другому уравнению верификации.
Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит.
Западных криптографов вполне устраивает q длиной примерно 160 бит.
Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи.
