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

Область применения

Цифровая подпись позволяет:

1. Аутентифицировать лицо, подписавшее сообщение;
2. Контролировать целостность сообщения;
3. Защищать сообщение от подделок;
4. Доказать авторство лица, подписавшего сообщение.

История

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

Описание

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

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

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

Алгоритм

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

• простое число  — модуль эллиптической кривой такой, что
• эллиптическая кривая задаётся своим инвариантом или коэффициентами , где  — конечное поле из p элементов. связан с коэффициентами и следующим образом

, причём .

• целое число  — порядок группы точек эллиптической кривой, должно быть отлично от
• простое число , порядок некоторой циклической подгруппы группы точек эллиптической кривой, то есть выполняется , для некоторого . Так же лежит в пределах .
• точка эллиптической кривой , являющаяся генератором подгруппы порядка , то есть и для всех k = 1, 2, …, q-1, где  — нейтральный элемент группы точек эллиптической кривой E.
•  — хэш-функция (ГОСТ Р 34.11-94), которая отображает сообщения M в двоичные векторы длины 256 бит.

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

• ключ шифрования  — целое число, лежащее в пределах .
• ключ расшифрования , вычисляемый как .

Дополнительные требования:

• , , где
• и

Двоичные векторы

Между двоичными векторами длины 256 и целыми числами ставится взаимно-однозначное соответствие по следующему правилу . Здесь либо равно 0, либо равно 1. Другими словами,  — это двоичное представление числа z.

Результатом операции конкатенации двух векторов и называется вектор длины 512 . Обратная операция — операция разбиения одного вектора длины 512 на два вектора длины 256.

Формирование цифровой подписи

Блок-схемы:

• Формирование цифровой подписи

• Проверка цифровой подписи

1. Вычисление хэш-функции от сообщения М:
2. Вычисление , и если , положить . Где  — целое число, соответствующее
3. Генерация случайного числа такого, что
4. Вычисление точки эллиптической кривой , и по ней нахождение где  — это координата точки Если , возвращаемся к предыдущему шагу.
5. Нахождение . Если , возвращаемся к шагу 3.
6. Формирование цифровой подписи , где и  — векторы, соответствующие и .

Проверка цифровой подписи

1. Вычисление по цифровой подписи чисел и , учитывая, что , где и  — числа, соответствующие векторам и . Если хотя бы одно из неравенств и неверно, то подпись неправильная.
2. Вычисление хэш-функции от сообщения М:
3. Вычисление , и если , положить . Где  — целое число соответствующее
4. Вычисление
5. Вычисление и
6. Вычисление точки эллиптической кривой . И определение , где  — координата кривой
7. В случае равенства подпись правильная, иначе — неправильная.

Криптостойкость

Криптостойкость цифровой подписи опирается на две компоненты — на стойкость хэш-функции и на стойкость самого алгоритма шифрования.^[1]

Вероятность взлома хэш-функции по ГОСТ 34.11-94 составляет при подборе коллизии на фиксированное сообщение и при подборе любой коллизии.^[1] Стойкость алгоритма шифрования основывается на дискретном логарифмировании в группе точек эллиптической кривой. На данный момент нет метода решения данной задачи хотя бы с субэкспоненциальной сложностью.^[2]

Одни из самых быстрых алгоритмов, на данный момент, при правильном выборе параметров — -метод и -метод Полларда.^[3]

Для оптимизированного -метода Полларда вычислительная сложность оценивается как . Таким образом для обеспечения криптостойкости операций необходимо использовать 256-разрядное .^[1]

Отличия от ГОСТ 34.10-94 (старый стандарт)

Новый и старый ГОСТы цифровой подписи очень похожи друг на друга. Основное отличие — в старом стандарте часть операций проводится над полем , а в новом — над группой точек эллиптической кривой, поэтому требования налагаемые на простое число в старом стандарте( или ) более жёсткие, чем в новом.

Алгоритм формирования подписи отличается только в пункте 4. В старом стандарте в этом пункте вычисляются и и, если , возвращаемся к пункту 3. Где и .

Алгоритм проверки подписи отличается только в пункте 6. В старом стандарте в этом пункте вычисляется , где  — открытый ключ для проверки подписи, . Если , подпись правильная, иначе неправильная. Здесь  — простое число, и является делителем .

Использование математического аппарата группы точек эллиптической кривой, позволяет существенно сократить порядок модуля , без потери криптостойкости.^[1]

Также старый стандарт описывает механизмы получения чисел , и .

Возможные применения

• Использование пары ключей (открытый, закрытый) для установления ключа сессии.^[4]
• Использование в сертификатах открытых ключей.^[5]
• Использование в S/MIME (PKCS#7, Cryptographic Message Syntax).^[6]
• Использование для защиты соединений в TLS (SSL, HTTPS, WEB).^[7]
• Использование для защиты сообщений в XML Signature (XML Encryption).^[8]
• Защита целостности Интернет адресов и имён (DNSSEC).^[9]

Примечания