Электронная цифровая подпись (ЭЦП)

Теоретические положения

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

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

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

Стандарт на процедуры электронно-цифровой подписи ГОСТ Р34.10-94

Российским стандартом на процедуры выработки и проверки электронно-цифровой подписи является ГОСТ Р 34.10-94. Схема электронно-цифровой подписи, предложенная в данном стандарте, во многом напоминает подпись в DSA.

Цифровая подпись представляет собой два больших целых простых числа. Общедоступные параметры схемы электронно-цифровой подписи (p,q,a) должны удовлетворять следующим условиям:

p: 2^501<p<2^512 или 2^1020<p<2^1020

q: простой делитель числа (p-1), который удовлетворяет условию 2^254<q<2^256

a: 1<a<p-1, a^q(mod p) =1

Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете.

Открытый ключ вычисляется: y=a^x mod p.

Генерация электронно-цифровой подписи

  Процесс генерации электронно-цифровой подписи состоит из нескольких этапов:

1. Вычисляется хэш-код сообщения m: h=H(m) (хэш-функция, используемая в данном стандарте в соответствии с ГОСТ Р 34.10-94), если

h(m)(mod p) = 0,

то h(m) присваивается значение 0…02551

2. Из диапазона [1,q] случайным образом выбирается значение k

3. Вычисляется:

r= (a^k mod p) , r1=r(mod p);

если r1=0, следует вернуться к предыдущему этапу и выработать другое значение k.

4. Вычисляется:

s= (xr1+kh(m))(mod p);

если s=0, то необходимо выработать другое значение k.

Значения r1,s1 являются электронно-цифровой подписью сообщения m и передаются вместе с ним по каналам связи.

Проверка электронно-цифровой подписи

  Проверка электронно-цифровой подписи происходит следующим образом:

- Проверяется выполнение условий 0<r<q, 0<s<q, и если хотя бы одно из них нарушено, подпись отвергается.

- Вычисляется хэш-код данного сообщения h=H(m); Если h(m)(mod p) = 0, то битовое представление h(m): 0…02551

- Вычисляется значение v=(h(m))^q-2(mod p).

- Вычисляется значения z1=sv(mod p); z2=(q-r1)v(mod p).

- Вычисляется значение u=(a^z1y^z2(mod p))(mod q)

- проверяется равенство u = r1

Если последнее равенство выполняется, то подпись принимается.

Алгоритм реализации ЭЦП

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

1. Выбрать простое число p.

2. Выбрать число q так, чтобы q являлось простым делителем числа p-1.

3. Выработать число a следующим образом:

а) произвольно выбрать число d: 1<d<p-1

б) вычислить f=d^p-1/q mod p

в) если f=1, то перейти к а). Если f<>1, то a:=f.

4. Выбрать секретный ключ x.

5. Вычислить открытый ключ пользователя y=a^x mod p. Проверить, что y<q, если условие выполняется, то x и y открытый и закрытый ключи соответственно. Если не выполняется условие вернуться к п.2.4.

Алгоритм выработки подписи

1. Вычислить h(M) - значение хеш-функции от каждой строки сообщения М как контрольная сумма 1 в строке сообщения. Если h(M) mod q = 0, присвоить h(M) = 1.

2. Выбрать целое число 0<k<q - секретный ключ

3. Вычислить два значения: r=a^k mod q и r1=r mod q. Если r1=0 перейти к п.3.2 и выработать другое значение числа k.

4. С использованием секретного ключа x пользователя вычислить значение s=(x*r1+k*h(M)) mod q. Если s=0 перейти к п.3.2, в противном случае - конец.

5. Подписью сообщения является вектор <r1>II<s>.

Алгоритм проверки подписи

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

2. Вычислить h(M1) – значение хеш-функции от каждой строки полученного сообщения М1 как контрольную сумму 1 в строке сообщения. Если h(M) mod q = 0, присвоить h(M) = 1.

3. Вычислить значение V=(h(M1)) ^q-2 modq

4. Вычислить значения Z1=SV mod q

Z2=(q-r1)Vmod q

5. Вычислить значение U=(a^z1y^z2(mod p))(mod q)

6. Проверить условие r’=u

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

Предлагаю ознакомиться с аналогичными статьями: