Во многих странах сегодня существуют стандарты на электронную (цифровую) подпись. В этом разделе мы опишем российский государственный стандарт ГОСТ Р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%%.
Равенство (2) означает, что при возведении о в степени по модулю р показатели приводятся по модулю %%q%%, т.е. %%a \, mod\, p = а^{b \, mod \, q} mod\, р%%. Такое приведение будет постоянно выполняться при генерации и проверке подписи, в результате чего длина показателей степени в рамках рассматриваемого алгоритма никогда не будет превышать 256 бит, что упрощает вычисления.
Далее, каждый пользователь выбирает случайно число х, удовлетворяющее неравенству %%0 < x < q%%, и вычисляет %%у = a^x mod\, p%%. (3)
Число х будет секретным ключом пользователя, а число у — открытым ключом. Предполагается, что открытые ключи всех пользователей указываются в некотором несекретном, но «сертифицированном» справочнике, который должен быть у всех, кто собирается проверять подписи. Отметим, что в настоящее время найти х по у практически невозможно при указанной выше длине модуля р. На этом этап выбора параметров заканчивается, и мы готовы к тому, чтобы формировать и проверять подписи.
Пусть имеется сообщение %%m%%, которое необходимо подписать. Генерация подписи выполняется следующим образом:
Для проверки подписи делаем следующее.
Если хотя бы одна из проверок на шагах 2 и 5 не дает нужного результата, то подпись считается недействительной.
Если все проверки удачны, то подпись считается подлинной.
Чтобы найти параметр а, удовлетворяющий равенству %%a^q mod p = 1%%, рекомендуется использовать следующий метод. Берем случайное число g > 1 и вычисляем
$$а = g^{(p-1)/q} mod р. $$
Если %%a > 1%%, то это то, что нам нужно.
Приведем пример. Выберем общие не секретные параметры
$$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%%.
Теперь остановимся на отличиях американского стандарта от российского. Они сводятся к следующему.
С учетом этих отличий нетрудно переписать всю схему подписи в «американском» стиле.
| Закон «Об электронной подписи» | Проверка знаний. Современная криптография и государственные стандарты |