Российский стандарт цифровой подписи ГОСТ 34.10

В отечественном стандарте ГОСТ 34.10, принятом в 1994 году, используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ЭльГамаля.

В стандарте ГОСТ 34.10 используется хэш-функция ГОСТ 34.11, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q:

1. р должно быть простым числом в диапазоне 2⁵⁰⁹ < p < 2⁵¹²

либо 2¹⁰²⁰ < p < 2¹⁰²⁴

2. q должно быть простым числом в диапазоне 2²⁵⁴ < q < 2²⁵⁶

q также должно быть делителем (р-1).

Аналогично выбирается и параметр g. При этом требуется, чтобы g^q (mod p) = 1.

В соответствии с теоремой Ферма это эквивалентно, что g = h^(p-1)/q mod p.

Закрытым ключом является произвольное число х: 0 < x < q

Открытым ключом является число y: y = g^x mod p

Для создания подписи выбирается случайное число k: 0 < k < q

Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:

r = (g^k mod p) mod q

s = (k H(M) + xr) mod q

Обратим внимание на отличия DSS и ГОСТ 34.10.

1. Используются разные хэш-функции: в ГОСТ 34.10 применяется отечественный стандарт на хэш-функции ГОСТ 34.11, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 34.10 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.

2. По-разному вычисляется компонента s подписи. В ГОСТ 34.10 компонента s вычисляется по формуле

s = (k H(M) + xr) mod q

В DSS компонента s вычисляется по формуле

s = [k^-1 (H(M) + xr)] mod q

Последнее отличие приводит к соответствующим отличиям в формулах для проверки подписи.

Получатель вычисляет

w = H(M)^-1 mod q

u₁ = (w ´ s) mod q

u₂ = ((q-r) ´ w) mod q

v = [(g^u1 y^u2) mod p] mod q

Подпись корректна, если v = r.

Структура обоих алгоритмов довольно интересна. Заметим, что значение r совсем не зависит от сообщения. Вместо этого r есть функция от k и трех общих компонент открытого ключа. Мультипликативная инверсия k (mod p) (в случае DSS) или само значение k (в случае ГОСТ 34.10) подается в функцию, которая, кроме того, в качестве входа имеет хэш-код сообщения и закрытый ключ пользователя. Эта функция такова, что получатель может вычислить r, используя входное сообщение, подпись, открытый ключ пользователя и общий открытый ключ.

В силу сложности вычисления дискретных логарифмов нарушитель не может восстановить k из r или х из s.

Другое важное замечание заключается в том, что экспоненциальные вычисления при создании подписи необходимы только для g^k mod p. Так как это значение от подписываемого сообщения не зависит, оно может быть вычислено заранее. Пользователь может заранее просчитать некоторое количество значений r и использовать их по мере необходимости для подписи документов. Еще одна задача состоит в определении мультипликативной инверсии k^-1 (в случае DSS). Эти значения также могут быть вычислены заранее.

Подписи, созданные с использованием стандартов ГОСТ 34.10 или DSS, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (r,s), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.

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