Алгоритм цифровой подписи DSA

Алгоритм цифровой подписи DSA (Digital Signature Algorithm) пред­ложен в 1991 г. в НИСТ США для использования в стандарте цифро­вой подписи DSS (Digital Signature Standard). Ал­горитм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К.Шнорра. Он состоит из следующих шагов:

1. Отправитель и получатель электронного документа генерируют ис­пользуемые при вычислениях большие целые числа g, p, q, являющи­еся открытыми параметрами криптосистемы:

- g и p - простые числа, L бит каждое (512< L £1024);

- q - простое число дли­ной 160 бит (делитель числа (p -1)).

Они могут быть общими для всех пользователей сети.

2. Отправитель выбирает случайное целое число x (1< x<q), являюще­еся его секретным ключом.

3. Затем отправитель вычисляет значение открытого ключа

y = g^х mod p,

которое передается всем получателям документов.

Ø Для того чтобы подписать документ M, отправитель хэширует его в целое хэш-значение m с использованием односторонней функ­ции хэширования h (·), опре­деленной в алгоритме безопасного хэширо­вания SHA:

m = h (M), 1< m<q.

5. Затем отправитель генерирует случайное целое число k, 1< k<q, и вычисляет:

r = (g^k mod p) mod q.

6. Далее отправитель вычисляет с помощью секретного ключа x число:

s =(m + r*x)/ k mod q.

Пара чисел (r,s)= S образует цифровую подпись S под документом M.

Таким образом, подписанное сообщение представляет собой тройку чисел [ M, r, s ].

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

8. Затем получатель вычисляет хэш-функцию m = h (M), значение

w =1 /s mod q

и числа                         U ₁ = (m * w) mod q,

U ₂ = (r * w) mod q.

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

v =((g^{U 1} * y ^{U 2}) mod p) mod q

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

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

Можно строго математически доказать, что последнее равенство будет выполняться тогда и только тогда, когда подпись S = (r,s) под документом M получена с помощью именно того секретного ключа x, из которого был получен секретный ключ y.

Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом x (не раскрывая при этом значения ключа x) и что отправитель подписал именно данный документ M.

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

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

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

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

s = (m+r x)/ k mod q, w = 1/ s mod q,

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

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

Отечественный стандарт цифровой подписи

Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Он исполь­зу­ет однонаправленную хэш-фун­кцию h (M), осно­ванную на использовании стандартного симметричного алгоритма ГОСТ 28147-89. Алгоритм цифро­вой подписи, опреде­ляемый этим стандартом, концептуально близок к алгоритму DSA.

Стандарт ГОСТ Р 34.11-94 использует следующие параметры алгоритма:

открытые:

р - большое простое число длиной 509-512 бит либо 1020-1024 бит;

q - простой сомножитель числа (р -1), имеющий длину 254-256 бит.

секретный:

а - любое число, меньшее (р -1), такое, что a^q mod p =1;

Секретный ключ:х –случайное число, меньше q;

Открытый ключ:у = a^х mod p.

Чтобы подписать некоторое сообщение m, а затем проверить подпись, выполняются следующие шаги.

1. Пользователь А генерирует случайное число k, причем k < q.

2. Пользователь А вычисляет значения

r = (a^k mod p) mod q,

s = (х · r + k · h (m)) mod q.

Если h (m) mod q = 0, то значение h (m) mod q принимают равным единице. Если r = 0 или s =0, то выбирают другое значение k и начинают снова.

Цифровая подпись представляет собой два числа, каждое длиной 256 битов, которые пользователь А отправляет эти числа пользователю В:

r mod 2²⁵⁶ и s mod 2²⁵⁶..

3. Пользователь В проверяет полученную подпись, вычисляя

v = h (m) ^{q -2} mod q,

z ₁ = (s · v) mod q,

  z ₂= ((q - r) · v) mod q,

u = ((а ^{z 1} · у ^{z 2}) mod p) mod q.

Если u = r, то подпись считается верной.

Различие между этим алгоритмом и алгоритмом DSA заключается в том, что в DSA

s = (k ^-1 (х · r + h (m))) mod q,

что приводит к другому уравнению верификации.

Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в зна­чениях параметра q является отражением стремления разработ­чиков отечественного стандарта к получению более безопасной подписи.

Криптографические протоколы