4.3.4. Алгоритмы электронной цифровой подписи гост р 34.10–94 и гост р 34.10–2001

Алгоритм цифровой подписи, определяемый этим стандартом ГОСТ Р 34.10–94, концептуально близок к алгоритму DSA. В нем используются следующие параметры: р – большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит; q – простой сомножитель числа (р – 1), имеющий длину 254...256 бит; а – любое число, меньшее (р – 1), причем такое, что a^q (mod p) = 1; х – некоторое число, меньшее q; у = а^х (mod p).

Кроме того, этот алгоритм использует однонаправленную хэш-функцию h(х), определенную стандартом ГОСТ Р 34.11–94.

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

Чтобы подписать некоторое сообщение M, а затем проверить подпись, выполняются следующие шаги.

1. Отправитель генерирует случайное число k, причем k < q.

2. Отправитель вычисляет значения m = h(M), r = (a^k (mod p))(mod q) s = (xr + km)(mod q). Если m (mod q) = 0, то значение m принимают равным единице. Если r = 0, то выбирают другое значение k и начинают снова. Цифровая подпись представляет собой два числа: r mod 2²⁵⁶ и s mod 2²⁵⁶. Подписанное сообщение отправляется получателю.

3. Получатель проверяет подпись, вычисляя:

v = h(M)^q–2 (mod q),

z₁ = s  v (mod q),

z₂ ⁼ ((q – r)  v) (mod q),

.

Если u = r, то подпись считается верной.

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

Параметрами схемы цифровой подписи являются.

1. Простое число p – модуль эллиптической кривой, удовлетворяющее неравенству p > 2²⁵⁵.

2. Эллиптическая кривая E_p(a,b), задаваемая своим инвариантом J или коэффициентами a и b.

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

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

, , где .

3. Целое число m, удовлетворяющее условию

.

4. Простое число q, для которого выполнены следующие условия:

m = nq, n  1;

2²⁵⁴ < q < 2²⁵⁶.

5. Точка P  O эллиптической кривой E_p(a,b), с координатами (x_P, y_P), удовлетворяющая равенству qP = O.

6. Хэш-функция h, определенная в ГОСТ Р 34.11–94.

Каждый пользователь схемы цифровой подписи должен обладать личными ключами: ключом подписи (целым числом d, удовлетворяющим неравенству 0 < d < q) и ключом проверки (точкой эллиптической кривой Q с координатами (x_Q, y_Q), удовлетворяющей равенству Q = dP).

На приведенные выше параметры схемы цифровой подписи накладываются следующие требования:

• должно быть выполнено условие p^t  1(mod q), для всех целых t = 1, 2, ... B, где B удовлетворяет неравенству B  31;

• должно быть выполнено неравенство m  p;

• инвариант кривой должен удовлетворять условию или 1728.

Исходными данными процесса получения электронной цифровой подписи являются ключ подписи d и подписываемое сообщение M, а выходным результатом – ЭЦП S. Данный процесс заключается в следующем.

1. Вычислить хэш-код сообщения: h_M = h(M).

2. Вычислить целое число , двоичным представлением которого является вектор h_M, и определить значение e   (mod q). Если e = 0, то определить e = 1.

3. Cгенерировать случайное (псевдослучайное) целое число k, удовлетворяющее неравенству 0 < k < q.

4. Вычислить точку эллиптической кривой C = kP и определить r  x_C (mod q), где x_C – x-координата точки C. Если r = 0, то повторить предыдущее действие.

5. Вычислить значение s  (rd + ke)(mod q). Если s = 0, то подобрать другое число k и повторить шаги 4 и 5.

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

Исходными данными процесса проверки электронной цифровой подписи являются подписанное сообщение M, цифровая подпись S и ключ проверки Q, а выходным результатом – свидетельство о достоверности или ошибочности данной подписи. Для этого необходимо выполнить следующие действия.

1. По полученной подписи S, вычислить целые числа r и s. Если выполнены неравенства 0 < r < q и 0<s<q, то перейти к следующему шагу. В противном случае подпись неверна.

2. Вычислить хэш-код полученного сообщения M: h_M = h(M).

3. Вычислить целое число , двоичным представлением которого является вектор h_M, и определить значение e   (mod q). Если e = 0, то определить e = 1.

4. Вычислить значение v  e^–1 (mod q).

5. Вычислить значения z₁  sv (mod q) и z₂  –rv (mod q).

6. Вычислить точку эллиптической кривой C = z₁P + z₂Q и определить R  x_C (mod q), где x_C – x-координата точки C.

7. Если выполнено равенство R = r, то подпись принимается, в противном случае, подпись неверна.