Российский стандарт ГОСТ Р 34.10-2001

История: полное название: «ГОСТ Р 34.10−2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» — российский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи. Принят и введён в действие Постановлением Госстандарта России от 12 сентября 2001 года.

Данный алгоритм разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Разрабатывался взамен ГОСТ Р 34.10−94 для обеспечения большей стойкости алгоритма.

Описание алгоритма: ГОСТ Р 34.10−2001 основан на эллиптических кривых. Его стойкость основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции по ГОСТ Р 34.11−94.

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

Параметры схемы цифровой подписи:

• 1. Простое число p — модуль эллиптической кривой такой, что p > 2²⁵⁵
• 2. Эллиптическая кривая E задается своим инвариантом J (E) или коэффициентами a, b Є F_p где F_p —конечное простое поле. J (E) связан с коэффициентами a и b следующим образом

.

при этом 4a³ + 27b²? 0 (mod p).

• 3. Целое число m — порядок группы точек эллиптической кривой (то есть число элементов группы). m не должно совпадать с p.
• 4. Простое число q, порядок одной из циклических подгрупп группы точек эллиптической кривой, то есть выполняется m = nq, для некоторого n — натурального. Так же q лежит в пределах 2²⁵⁴ < q < 2²⁵⁶.
• 5. Точка P (x_p, y_p)? 0 эллиптической кривой E, являющаяся генератором подгруппы порядка q, или другими словами qP = 0. Здесь qP = P + P + …(q раз). А 0 — нулевой элемент группы точек эллиптической кривой.
• 6. h (M) — хэш-функция (ГОСТ Р 34.11−94) длина хэша — 256 бит.
• 7. Каждый пользователь цифровой подписи имеет личные ключи: 1) ключ шифрования d — целое число, лежащее в пределах 0 < d < q. 2) ключ расшифрования Q (x_q, y_q) — точка эллиптич. кривой, dP = Q.
• 8. При этом должны выполняться: 1) p^t? 1 (mod q), где B? 31. 2) J (E)? 0 и J (E)? 1728.

Подписывание:

• 1. Вычисление хэш-функции от сообщения М: m = h (M)
• 2. Вычисление e = z (mod q), и если e = 0, положить e = 1. Где z — целое число соответствующее m
• 3. Генерация случайного числа k, такого что 0 < k < q
• 4. Вычисление точки эллиптической кривой C = kP, и по ней нахождение r = x_c (mod q) (x_c — координата x точки C). Если r = 0, возвращаемся к предыдущему шагу.
• 5. Нахождение s = rd + ke (mod q). Если s = 0, возвращаемся к шагу 3.
• 6. Формирование цифровой подписи (r, s)

Проверка:

• 1. Если хотя бы одно из неравенств r < q и s < q неверно, то подпись неправильная.
• 2. Вычисление хэш-функции от сообщения М: m = h (M)
• 3. Вычисление e = z (mod q), и если e = 0, положить e = 1. Где z — целое число соотвествующее
• 4. Вычисление v = e — ¹ (mod q)
• 5. Вычисление z₁ = sv (mod q) и z₂ = - rv (mod q)
• 6. Вычисление точки эллиптической кривой C = z₁P + z₂Q. И определение R = x_c(mod q), где x_c — координата x кривой C. В случае равенства R = r подпись правильная, иначе — неправильная.