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

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

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

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

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

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

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

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

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

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

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

р - простое число, 2509 <р < 2512, либо 21020 < р < 21024; 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) значение 02551.
  • 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) значение 02551.
  • 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 = т. В противном случае подпись считается недействительной.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >