Стандарт цифровой подписи ГОСТ Р 34. 10-94

Российский стандарт ЭЦП разрабатывался позже первоначального варианта американского, поэтому параметры этого алгоритма выбраны с учетом возросших возможностей потенциального противника по вскрытию криптосистем. В частности, увеличена длина значения хеш-функции, что снижает вероятность столкновений, и, соответственно, порядок элементагенератора, что делает более сложным решение задачи дискретного логарифма для восстановления секретного ключа. При описании алгоритма будут использоваться следующие обозначения:

В* - множество всех конечных слов в алфавите В = {0,1};

|А| - длина слова А;

Vk (2) — множество всех двоичных слов длины к;

А||В — конкатенация слов, А и В, также обозначается как АВ;

Ак — конкатенация к экземпляров слова А;

k — слово длины к, содержащее запись N (mod 2к), где N — неотрицательное целое;

? — побитовое сложение слов по модулю 2;

[+] - сложение по правилу, А [+] В = к (к = |А| = |В|); т — передаваемое сообщение; т1 — полученное сообщение;

h — хеш-функция, отображающая последовательность т в слово h (m) eV256(2);

р — простое число, 2509 <�р < 2512, либо 21 020 < р < 21 024; q — простое число, 2254 < q < 2256 и q является делителем для (р — 1); а — целое число, 1 < а < р — 1, при этом aq (mod р) = 1; к — целое число, 0 < к < q;

х — секретный ключ пользователя для подписи, 0 < х < q; у — открытый ключ для проверки подписи у = ax (mod р).

Система ЭЦП включает в себя процедуры выработки и проверки подписи под данным сообщением.

Цифровая подпись, состоящая из двух целых чисел, вычисляется с помощью определенного набора правил, изложенных в стандарте.

Числа р, q и а, являющиеся параметрами системы, не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое число к, которое генерируется в процедуре подписи сообщения, должно быть секретным и должно быть уничтожено сразу после выработки подписи. Число к снимается с физического датчика случайных чисел или вырабатывается псевдослучайным методом с использованием секретных параметров.

Процедура выработки подписи включает в себя следующие шаги:

• 1. Вычислить h (m) — значение хеш-функции h от сообщения т. Если h (m)(mod q) = 0, то присвоить h (m) значение 2 551.
• 2. Выработать целое число к, 0 < к < q.
• 3. Вычислить два значения: г' = d k (mod р) и г = г' (mod q). Если г = О, то перейти к шагу 2 и выработать другое значение числа к.
• 4. С использованием секретного ключа х пользователя вычислить значение s = (xr + kh (m))(mod q). Если s = 0, то перейти к шагу 2, в противном случае закончить работу алгоритма.

Сообщение, дающее нулевое значение хеш-функции, нс подписывается. В противном случае уравнение подписи упростилось бы до s = xr (mod q) и злоумышленник легко мог бы вычислить секретный ключ х.

Проверка цифровой подписи возможна при наличии у получателя открытого ключа отправителя, пославшего сообщение.

Уравнение проверки будет следующим:

Вычисления по этому уравнению реализуются следующим образом:

• 1. Проверить условия: 0
• 2. Вычислить h (ml) — значение хеш-функции h от полученного сообщения т1. Если h (ml)(mod q) = 0, присвоить h (m I) значение 2 551.
• 3. Вычислить значение v = (h (ml)))q-2(mod q), что является ни чем иным, как мультипликативным обратным к h (mI)(mod q). Вообще говоря, алгоритм проверки можно несколько ускорить, если вычислять h (ml) — l (mod q) с помощью расширенного алгоритма Евклида, а ни путем возведения в степень.
• 4. Вычислить значения: zl = sv (mod q) и z2 = (q — r) v (mod q).
• 5. Вычислить значение u = (a zl у z2 (mod p))(mod q).
• 6. Проверить условие г = и.

При совпадении значений г и и получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т. е. т1 = т. В противном случае подпись считается недействительной.