Отечественный стандарт цифровой подписи

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

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

1. р должно быть простым числом в диапазоне

2. 2⁵⁰⁹ < p < 2⁵¹²

3. либо

2¹⁰²⁰ < p < 2¹⁰²⁴

1. q должно быть простым числом в диапазоне

2²⁵⁴ < q < 2²⁵⁶

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

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

В соответствии с теоремой Ферма это эквивалентно условию в DSS, что 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