Алгоритм цифровой подписи ГОСТ Р 34.10-94

Алгоритм использует следующие параметры:

· p= простое число, длина которого либо между 509 и 512 битами, либо между 1020 и 1024 битами.

· q = простое число - множитель p-1, длиной от 254 до 256 битов.

· a= любое число, меньшее p-1, для которого a^q mod p= 1.

· x= число, меньшее q.

· y= a^x mod p.

Этот алгоритм также использует однонаправленную хэш-функцию: H(x). Стандарт определяет использование хэш-функции ГОСТ Р 34.11-94, основанной на симметричном алгоритме ГОСТ 28147-89.

Первые три параметра, p, q и a, открыты и могут использоваться совместно пользователями сети. Закрытым ключом служит x, а открытым - y. Чтобы подписать сообщение m

(1) Алиса генерирует случайное число k, меньшее q

(2) Алиса генерирует I = (a* mod p) mod q s = (ct + k(H(m))) mod q

r= (a^k mod p)mod q

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

Если H(m)mod q =0, то значение хэш-функции устанавливается равным 1. Если r =0, то выберите другое значение k и начните снова. Подписью служат два числа: rmod 2²⁵⁶ и smod 2²⁵⁶, Алиса посылает их Бобу.

(3) Боб проверяет подпись, вычисляя

v = H(m)^q-2mod q

z₁ = (sv)mod q

z₂ = ((q-r)*v)mod q

u= (() mod p) mod q

Если u= r, то подпись правильна.

Различие между этой схемой и DSA в том, что в DSA s = (k-1 (H(m) + xr)) mod q, что дает другое уравнение проверки. Любопытно, однако, что длина q равна 256 битам. Большинству западных криптографов кажется достаточным q примерно 160 битов длиной.

Есть и еще один отечественный стандарт вычисления ЭЦП – ГОСТ Р 34.10‑2001 «Информационная технология. Криптографическая защита информации. Т.к. срок действия ГОСТ Р 34.10‑94 заканчивается 31 декабря 2007 года, в разрабатываемых системах криптографической защиты информации алгоритмом ЭЦП по умолчанию является ГОСТ Р 34.10‑2001, а стандарт 1994 года используется лишь для достижения совместимости с раннее разработанными программами защиты.

Большинство схем выработки ЭЦП однотипны и могут уложиться в следующую схему:

Даже при поверхностном анализе двух стандартов ЭЦП (ГОСТ Р 34.10‑94 и ГОСТ Р 34.10‑2001) видно, что собственно сама схема генерации и проверки ЭЦП одинаковые. Различны только способы обеспечения сложности подделки ЭЦП, т.е. так называемой стойкости алгоритма ЭЦП. Стойкость алгоритма ЭЦП из ГОСТ Р 34.10‑94 обеспечивается трудностью логарифмирования больших чисел в конечном простом поле. Стойкость же алгоритма ЭЦП из ГОСТ Р 34.10‑2001 обеспечивается трудностью определения n по исходному произведению nP точки P эллиптической кривой Е конечном простом поле.