В стандарте ГОСТ 3410, принятом в 1994 году, используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ElGamal.
В стандарте ГОСТ 3410 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит.
Это во многом обуславливает требования к выбираемым простым числам p и q:
р должно быть простым числом в диапазоне
2509 < p < 2512 или 21020 < p < 21024
q должно быть простым числом в диапазоне
2254 < q < 2256
q должно быть делителем р - 1.
Аналогично выбирается и параметр g, при этом требуется, чтобы
gq (mod p) = 1.
В соответствии с теоремой Ферма это эквивалентно условию в DSS, что
g = h(p-1)/q mod p.
Закрытым ключом является произвольное число х, 0 < x < q
Открытым ключом является число y
y = gx mod p
Для создания подписи выбирается случайное число k , 0 < k < q
Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:
r = (gk mod p) mod q
s = (k H(M) + xr) mod q