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

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

р- простое число, 2⁵¹⁰ < р < 2⁵¹² либо 2¹⁰²² < р <2¹⁰²⁴ .

q- простое число, 2²⁵⁴ < q < 2²⁵⁶ и q является делителем для (p-1)

g- целое число, 1 < g < р-1, при этом ord g = g

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

1. Вычислить h(M) -значение хеш-функции h от сообщения М.

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

3. Вычислить два значения :

4. С использованием секретного ключа х пользователя (отправителя

сообщения) вычислить значение

Проверка

Получатель должен проверить подлинность сообщения и подлинность ЭЦП, осуществляя ряд операций (вычислений).

Это возможно при наличии у получателя открытого ключа отправи-

теля, пославшего сообщение

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

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

0< s, r < q.

2. Вычислять h(M₁ )-значение хеш-функции h от полученного сообщения М₁ .

Если H(M₁ )(mod q)=0, присвоить h(M₁ ) значение 0²⁵⁵ 1.

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

w= h^-1mod q = h^q-2 mod q

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

u₁ = s*w (mod q) и

u₂ = r*w mod q = (q-1)w mod q

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

v = (g^u1*y^u2 (mod p)) (mod q) = (g^sh-1*y^-rh-1modp) mod q

6. Проверить условие: r = v При совпадении значений r и v получатель принимает решение о том, что полученное сообщение подписано данным отправителем и

в процессе передачи не нарушена целостность сообщения. В противном случае подпись считается недействительной.

ГОСТ Р 34.10-2001

В ГОСТ Р 34.10-2001 используется группа точек эллиптической кривой, определенная над конечным полем, и хэш-функций ГОСТ Р 34.11-1994. Криптографическая стойкость основывается на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой, а также на стойкости используемой хэш-функции. Электронная подпись представляет собой двоичный вектор длиной 512 бит.

Эллиптическая кривая Е – множество чисел, удовлетворяющее тождеству:

Чтобы кривая не имела особых точек должно выполняться следующее условие:

Инвариант эллиптической кривой:

Коэффициенты a, b эллиптической кривой E, по известному инварианту J(E), определяются следующим образом

Где

Точка эллиптической кривой обозначается как Q(x, y). Рассмотрим операцию сложения двух точек .

Пусть в этом случае их суммой будем называть точку , координаты которой определяются сравнением:

Где

В случае, если x-координаты точек равны, y-координаты точек равны между собой и не равны нулю, то

Где

Если x-координаты равны, а сумму точек будем называть нулевой точкой O.

Параметры схемы электронной подписи:

1. Простое число p – модуль эллиптической кривой, удовлетворяет неравенству
2. Эллиптическая кривая Е, задаваемая инвариантом J(E) или коэффициентами a, b
3. Целое число m – порядок группы точек ЭК
4. Простое число q – порядок циклической подгруппы группы точек ЭК E, для которого выполнены следующие условия:

1. Точка P не равная нулю ЭК E, с координатами , удовлетворяющая равенству qP = O
2. Хэш-функция ГОСТ Р 34.11-1994, выходное значение функции – двоичный вектор длины 256 бит

Каждый пользователь должен обладать ключами:

1. Ключом подписи – целым числом d, удовлетворяющим неравенству
2. Ключом проверки – точкой эллиптической кривой Q, такой что dP = Q

Требования к параметрам:

1. для всех целых t = 1, 2, … B, где B > 30
2. 
3. J(E) 0 или 1728

Формирование подписи:

1. Вычисляем хэш h от сообщения M
2. Вычисляем a – число, двоичным представлением которого является хэш, определяем e = a (mod q), если e = 0, определить e = 1
3. Сгенерировать случайное целое число k: 0 < k < q
4. Вычислить точку эллиптической кривой C = Kp и определить

, если r = 0 – вернуться к шагу 3

1. Вычислить

, если s = 0 – вернуться к шагу 3

1. Вычислить двоичные векторы , соответствующие r и s и определить ЭП как их конкатенацию

Проверка подписи:

1. По подписи вычислить r и s, если 0 < r < q, 0 < s < q, то идём дальше, иначе – подпись неверна
2. Вычисляем хэш h от сообщения M
3. Вычисляем a – число, двоичным представлением которого является хэш, определяем e = a (mod q), если e = 0, определить e = 1
4. Вычислить
5. Вычислить
6. Вычислить точку эллиптической кривой и определить
7. Если выполнено R = r, то подпись принимается, в противном случае – она неверна

Diffie-Hellman

, р-простое

BÎE( ) – принадлежит эллиптической кривой

A B

aB bB

El Gamal

Зашифрование , k — разовый ключ, В — долговременный ключ

Расшифрование