Основы современной криптографии

       

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


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

B* – множество всех конечных слов в алфавите B = {0,1}.

|A| – длина слова А

Vk(2) – множество всех двоичных слов длины k.

A||B – конкатенация слов А и B, также обозначается как АВ.

Аk – конкатенация k экземпляров слова А.

<N>k – слово длины k, содержащее запись N(mod 2k), где N – неотрицательное целое.

Е – побитовое сложение слов по модулю 2.

[+] – сложение по правилу A [+] B = <A+B>k

(k = |A| = |B|).

m – передаваемое сообщение.

m1 – полученное сообщение

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



в слово h(m)О V256(2).

p – простое число, 2509 < p < 2512, либо 21020 < p < 21024.

q – простое число, 2254 < q < 2256 и q является делителем для (p – 1).

a – целое число, 1 < a < p – 1, при этом aq(mod p) = 1.

k – целое число, 0 < k < q.

x – секретный ключ пользователя для формирования подписи, 0 < x < q.

y – открытый ключ для проверки подписи, y = ax(mod

p).

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

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

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


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

1.                 Вычислить h(m) – значение хэш-функции h от сообщения m. Если h(m)(mod q) = 0, то присвоить h(m) значение 02551.

2.                 Выработать целое число k, 0 < k < q.

3.                 Вычислить два значения: r' = ak(mod p) и r = r' (mod q). Если r = 0, то перейти к шагу 2 и выработать другое значение числа k.

4.                 С использованием секретного ключа x пользователя вычислить значение s = (xr + kh(m))(mod q). Если s = 0, то перейти к шагу 2, в противном случае закончить работу алгоритма.

Заметим, что сообщение, дающее нулевое значение хэш-функции, не подписывается. В противном случае уравнение подписи упростилось бы до s

= xr (mod q) и злоумышленник легко мог бы вычислить секретный ключ x.

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

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



В самом деле,



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

1.                 Проверить условия: 0 < s < q и 0 < r < q. Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.

2.                 Вычислить h(m1) – значение хэш-функции h

от полученного сообщения m1.

Если h(m1)(mod

q) = 0, присвоить h(m1) значение 02551.

3.                 Вычислить значение v = (h(m1))q–2(mod



q), что является не чем иным, как мультипли­кативным обратным к h(m1) (mod q). Вообще говоря, алгоритм проверки можно несколько ускорить, если вычислять h(m1)?1(mod

q) с помощью расширенного алгоритма Евклида, а не путем возведения в степень.

4.                 Вычислить значения:

z1 = sv(mod

q) и

z2 = (q – r)v(mod q)

5.                 Вычислить значение

u =


6.                 Проверить условие

r = u

При совпадении значений r и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т.е. m1

= m. В противном случае подпись считается недействительной.


Содержание раздела