Стандарт цифровой подписи ГОСТ Р .-
Российский стандарт ЭЦП разрабатывался позже американского, поэтому параметры этого алгоритма выбраны с учетом возросших возможностей потенциального противника по вскрытию криптосистем. В частности, увеличена длина значения хэш-функции, что снижает вероятность столкновений, и, соответственно, порядок элемента-генератора, что делает более сложным решение задачи дискретного логарифма для восстановления секретного ключа. При описании алгоритма будут использоваться следующие обозначения:
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. В противном случае подпись считается недействительной.
