Стандарты на электронную (цифровую) подпись

Рассмотрим российский государственный стандарт ГОСТ Р34.10-94 и стандарт США FIPS 186. Российский стандарт был принят в 1994 году, американский — в 1991. В основе обоих стандартов лежит по сути один и тот же алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией подписи Эль-Гамаля. Рассмотрим российскую версию алгоритма, а затем отличия от нее американской версии.

Вначале для некоторого сообщества пользователей выбираются общие несекретные параметры. Прежде всего необходимо найти два простых числа, q длиной 256 бит и р длиной 1024 бита, между которыми выполняется соотношение

p = bq + 1 (1)

для некоторого целого b. Старшие биты в р и q должны быть равны единице. Затем выбирается число а > 1, такое, что

a^q mod р = 1. (2)

В результате получаем три общих параметра — р, q и a.

Замечание 1. Равенство (2) означает, что при возведении а в степени по модулю р показатели приводятся по модулю q, и такое приведение будет постоянно выполняться при генерации и проверке подписи. В результате длина показателей степени в рамках рассматриваемого алгоритма никогда не будет превышать 256 бит, что упрощает вычисления.

Далее каждый пользователь выбирает случайно число х, 0 < х < q, и вычисляет

y = a^x mod p. (3)

Число х будет секретным ключом пользователя, а число у — открытым ключом.

Предполагается, что открытые ключи всех пользователей указываются в некотором несекретном, но "сертифицированном" справочнике, который должен быть у всех, кто собирается проверять подписи.

Отметим, что в настоящее время найти х по у практически невозможно при указанной выше длине модуля р. На этом этап выбора параметров заканчивается, и мы готовы к тому, чтобы формировать и проверять подписи.

Пусть имеется сообщение m, которое необходимо подписать. Генерация подписи выполняется следующим образом:

1. Вычисляем значение хеш-функции h = h(m) для сообщения m (в российском варианте хеш-функция определяется ГОСТом P34.11-94).

2. Формируем случайное число k, 0 < k < q.

3. Вычисляем r = (a^k mod p) mod q. Если оказывается, что r = 0,

то возвращаемся к шагу 2.

4. Вычисляем s = (kh + xr) mod q. Если s = 0, то возвращаемся к шагу 2.

5. Получаем подписанное сообщение <m; r, s>.

Для проверки подписи делаем следующее.

1. Вычисляем хеш-функцию для сообщения h = h(m).

2. Проверяем выполнение неравенств 0 < r <q, 0 < s < q.

3. Вычисляем u₁ = s • h^-1 mod q, u₂ = -r • h^-1 mod q.

4. Вычисляем v = (a^u1y^u2 mod p) mod q.

5. Проверяем выполнение равенства v = r.

Если хотя бы одна из проверок на шагах 2 и 5 не дает нужного результата, то подпись считается недействительной. Если же все проверки удачны, то подпись считается подлинной.

Замечание 2. Чтобы найти параметр а, удовлетворяющий (2), рекомендуется использовать следующий метод. Берем случайное число g > 1 и вычисляем

а = g^(р-1)/q mod р. (4)

Если а > 1, то это то, что нам нужно. Действительно, на основании (4) и теоремы Ферма имеем

a^q mod р = g^{((p-1)/q) q} mod p = g^p-l mod p = 1,

т.е. выполняется равенство (2). Если при вычислении по (4) мы получаем а = 1 (крайне маловероятный случай), то нужно просто взять другое число g.

Пример. Выберем общие несекретные параметры

q = 11, р = 6q + 1 = 67,

возьмем g = 10 и вычислим

а = 10⁶ mod 67 = 25.

Выберем секретный ключ х = 6 и вычислим открытый ключ

у = 25⁶ mod 67 = 62.

Сформируем подпись для сообщения m = baaaab. Пусть для хеш-функции этого сообщения h(m) = 3. Возьмем случайно число k = 8.

Вычислим

r = (25⁸ mod 67) mod 11 = 24 mod 11 = 2,

s = (8 • 3 + 6 • 2) mod 11 = 36 mod 11 = 3.

Получаем подписанное сообщение

<baaaab; 2, 3>.

Теперь выполним проверку подписи. Если сообщение не изменено, то h = 3. Вычислим

h^-1 = 3^-1 mod 11 = 4,

u₁ = 3 • 4 mod 11 = 1,

u₂ = -2 • 4 mod 11 = -8 mod 11 = 3,

v = (25¹ • 62³ mod 67) mod 11 = (25 • 9 mod 67) mod 11 = 24 mod 11 = 2.

Мы видим, что v = г, значит подпись верна.

Теперь остановимся на отличиях американского стандарта от российского. Они сводятся к следующему.

1. Длина числа q берется равной 160 бит.

2. В качестве хеш-функции используется алгоритм SHA-1.

3. При генерации подписи на шаге 4 параметр s вычисляется по формуле

s = k^-l(h + xr) mod q.

4. При проверке подписи на шаге 3 u₁ и u₂ вычисляются по формулам

u₁ = h • s^-1 mod q, u₂ = r • s^-1 mod q.