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

И числа

Хэш-значение

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

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

Y = G^X mod P.

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

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

(В стандарте DSS определен алгоритм безопасного хэширования SHA (Secure Hash Algorithm)).

Для того чтобы подписать документ M, отправител ь хэширует его в целое хэш-значение m:

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

затем генерирует случайное целое число K, 1< K< q, и вычисляет число r:

r = (G^K mod P) mod q.

Затем отправитель вычисляет с помощью секретного ключа X целое число s:

s = mod q.

Пара чисел r и s образует цифровую подпись

S = (r,s)

под докумен том M.

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

Получатель подписанного сообщения [ M, r, s] проверяет выполнение условий

0 < r < q, 0 < s < q

и отвергает подпись, если хотя бы одно из этих условий не вы-

полнено.

w = mod q,

m = h(M)

u₁ = (m * w) mod q,

u₂ = (r * w) mod q.

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

v = (()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. Большинство операций с числами K, r, s, X при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.

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

Недостатки алгоритма DSA

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

s = (mod q),

w = (mod q),

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

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

Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94 Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA.

В нем используются следующие параметры:

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

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

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

x – некоторо е число, меньшее q;

y = a^х mod p.

Кроме того, этот алгоритм использует однонаправленнуюхэш-функцию H(x).

Стандарт ГОСТ Р 34.11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.

Первые три параметра p, q и a являются открытыми и могут быть общими для всех пользователей сети.

Число x является секретным ключом.

Число y является открытым ключом.

Процедура подписания некоторого сообщени m, и, затем, проверки подписи:

1. Пользователь A генерирует случайное число k,

при-чем k < q.

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

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

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

При вычислении значения S и r возможны следующие:случаи:

1) Если H(m) mod q=0, то значение H(m) mod q принимают равным Единице.

2) Если r=0, то выбирают другое значение k и начинают снова.

Цифровая подпись представляет собой два числа:

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 = (mod p) mod q.

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

Дата добавления: 2014-01-04