Материал предоставлен https://it.rfei.ru

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

Во многих странах сегодня существуют стандарты на электронную (цифровую) подпись. В этом разделе мы опишем российский государственный стандарт ГОСТ Р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%%, которое необходимо подписать. Генерация подписи выполняется следующим образом:

  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 не дает нужного результата, то подпись считается недействительной.

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

Замечание.

Чтобы найти параметр а, удовлетворяющий равенству %%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%%.

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

  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%%.

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

Закон «Об электронной подписи»Проверка знаний. Современная криптография и государственные стандарты