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

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

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

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

$a^q\; mod\; p = 1$. (2)

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

Далее, каждый пользователь выбирает случайно число х, удовлетворяющее неравенству $0 < x < q$, и вычисляет $у = a^x mod\,  p$. (3)

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

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

1. Вычисляем значение хеш-функции $h = h(\bar{m})$ для сообщения m, значение хеш-функции должно лежать в пределах $0 < h < q$ (в российском варианте хеш-функция определяется ГОСТом Р34.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. Получаем подписанное сообщение $(\bar{m}, r, s)$.

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

1. Вычисляем хеш-функцию для сообщения $h = h(\bar{m})$.
2. Проверяем выполнение неравенств $0 < r < q$, $0 < s < q$.
3. Вычисляем $u_1 = s \cdot h_{-1} mod\, q$, $u_2 = — r \cdot h_{-1} mod \,q$.
4. Вычисляем $v = (a^{u_1}y^{u_2} mod \,p) mod \,q$.
5. Проверяем выполнение равенства $v = r$.

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

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

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

$$q = 11, \; p = 6q + 1 = 67$$

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

$$a = 10^6 mod \,67 = 25.$$

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

$$y = 25^6 mod\, 67 = 62.$$

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

Вычислим: $$r = (25^8 mod\, 67) mod \,11 = 24 mod\, 11 = 2,$$ $$s = (8 \cdot 3 + 6 \cdot 2) mod \,11 = 36 mod\, 11 = 3.$$

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

(baaaab; 2, 3).

Теперь выполним проверку подписи. Если сообщение не изменено, то h = 3. Вычислим $$h^{-1} = З^{-1} mod \,11 = 4,$$ $$u_1 = 3 \cdot 4 mod\, 11 = 1,$$ $$u_2 = -2 \cdot 4 mod\, 11 = -8 mod \,11 = 3,$$

$$v = (25^1 \cdot 62^3 mod\, 67) mod \,11 = \\ (25 \cdot 9\, mod\, 67) mod \,11 =\\ 24 \,mod\, 11 = 2.$$

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

Утверждение. Если подпись к сообщению была сформирована законно, т.е. обладателем секретного ключа $х$, то $v = r$.

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

1. Длина числа $q$ берется равной 160 бит.
2. В качестве хеш-функции используется алгоритм SHA-1.
3. При генерации подписи на шаге 4 параметр s вычисляется по формуле $s = k^{-1}(h + xr) \,mod\, q$.
4. При проверке подписи на шаге 3 $u_1$ и $u_2$ вычисляются по формулам $u_1 = h \cdot s_{-1}\, mod\,q$, $u_2 = — r \cdot s_{-1}\, mod \,q$.

С учетом этих отличий нетрудно переписать всю схему подписи в «американском» стиле.