ГОСТ Р 34.10-94

ГОСТ Р 34.10-94 — государственный стандарт Российской Федерации, устанавливающий процедуры выработки и проверки электронной цифровой подписи (ЭЦП) на основе криптографических алгоритмов с открытым ключом. Принят и введён в действие Постановлением Госстандарта России от 23 мая 1994 года № 134. Стандарт стал первым российским национальным нормативным документом в области асимметричной криптографии, регламентирующим применение цифровой подписи в информационных системах общего пользования и государственных информационных системах. В 2001 году был заменён новым стандартом ГОСТ Р 34.10-2001, а затем — ГОСТ Р 34.10-2012, однако ГОСТ Р 34.10-94 остаётся важной вехой в истории развития отечественной криптографии.

История создания

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

Работы по созданию стандарта велись под руководством Главного управления безопасности связи (ГУБС) ФАПСИ (Федеральное агентство правительственной связи и информации) при участии ведущих научно-исследовательских институтов, в том числе Академии криптографии РФ и Института проблем передачи информации РАН. В основу алгоритма были положены математические разработки отечественных криптографов, основанные на теории эллиптических кривых.

Стандарт был официально опубликован в 1994 году и вступил в силу с 1 января 1995 года. Он действовал до 1 июля 2002 года, когда был заменён новым ГОСТ Р 34.10-2001, который, в свою очередь, был разработан с учётом накопленного опыта эксплуатации и требований международных стандартов.

Математические основы

ГОСТ Р 34.10-94 базируется на криптосистеме с открытым ключом, стойкость которой основана на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой, определённой над конечным полем GF(p), где p — простое число.

Эллиптическая кривая

В стандарте используется эллиптическая кривая вида:

\[ y^2 = x^3 + ax + b \pmod{p} \]

где a и b — коэффициенты, удовлетворяющие условию \(4a^3 + 27b^2 \neq 0 \pmod{p}\), что гарантирует отсутствие особых точек. Кривая выбирается таким образом, чтобы порядок её группы точек (число точек на кривой) содержал большой простой делитель. Это необходимо для обеспечения стойкости алгоритма к атакам на дискретное логарифмирование.

Параметры схемы

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

• p — простое число, модуль эллиптической кривой (длина — 256 бит).
• a, b — коэффициенты эллиптической кривой.
• m — порядок группы точек эллиптической кривой.
• q — простое число, делящее m (длина — 256 бит).
• P — точка эллиптической кривой порядка q (базовая точка).

Все параметры являются открытыми и могут быть опубликованы.

Ключи

• Закрытый ключ (d) — случайное целое число, удовлетворяющее условию \(0 < d < q\).
• Открытый ключ (Q) — точка эллиптической кривой, вычисляемая как \(Q = d \cdot P\) (умножение точки на число по правилам группы).

Процедуры формирования и проверки подписи

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

Для подписания сообщения M (представленного в виде хеш-значения h) выполняются следующие шаги:

1. Вычисляется хеш-значение сообщения h с помощью хеш-функции, определённой в ГОСТ Р 34.11-94 (функция «Стрибог»).
2. Генерируется случайное число k, удовлетворяющее условию \(0 < k < q\).
3. Вычисляется точка \(R = k \cdot P\).
4. Вычисляется первая компонента подписи r как \(r = x_R \pmod{q}\), где \(x_R\) — x-координата точки R.
5. Если r = 0, процедура повторяется с новым k.
6. Вычисляется вторая компонента подписи s по формуле:

\[ s = (k \cdot h + d \cdot r) \pmod{q} \]

1. Если s = 0, процедура повторяется с новым k.

Подпись представляет собой пару чисел (r, s).

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

Для проверки подписи (r, s) под сообщением M с открытым ключом Q выполняются следующие шаги:

1. Вычисляется хеш-значение сообщения h.
2. Проверяются условия \(0 < r < q\) и \(0 < s < q\). Если хотя бы одно из них не выполняется, подпись считается недействительной.
3. Вычисляется значение \(v = h^{-1} \pmod{q}\).
4. Вычисляются значения \(z_1 = s \cdot v \pmod{q}\) и \(z_2 = -r \cdot v \pmod{q}\).
5. Вычисляется точка \(R' = z_1 \cdot P + z_2 \cdot Q\).
6. Если \(x_{R'} \pmod{q} = r\), подпись признаётся подлинной. В противном случае — подпись недействительна.

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

Стандарт ГОСТ Р 34.10-94 обеспечивает стойкость, эквивалентную стойкости алгоритма DSA (Digital Signature Algorithm) при аналогичной длине ключа. Однако по сравнению с современными стандартами (например, ГОСТ Р 34.10-2012 с длиной ключа 512 бит) стойкость ГОСТ Р 34.10-94 считается недостаточной для долгосрочного использования.

Основные замечания к стандарту:

• Длина ключа — 256 бит, что на момент разработки считалось достаточным, но с развитием вычислительных мощностей и появлением алгоритмов квантового компьютера стало недостаточным для защиты на длительный срок.
• Хеш-функция — использовалась хеш-функция ГОСТ Р 34.11-94, которая также имеет длину хеша 256 бит и уязвима к коллизиям при определённых условиях.
• Отсутствие доказательной стойкости — в отличие от некоторых современных схем, для ГОСТ Р 34.10-94 не было строгого доказательства стойкости в модели случайного оракула.

Применение

ГОСТ Р 34.10-94 применялся в следующих областях:

• Государственные информационные системы — для подписания электронных документов, передаваемых между органами государственной власти.
• Системы электронного документооборота — в коммерческих организациях, работающих с государственными заказчиками.
• Банковская сфера — для подписания платёжных поручений и других финансовых документов.
• Системы сертификации — для выдачи и проверки цифровых сертификатов.

С 2002 года стандарт был заменён на ГОСТ Р 34.10-2001, который, в свою очередь, уступил место ГОСТ Р 34.10-2012. Однако в некоторых устаревших системах, не прошедших модернизацию, ГОСТ Р 34.10-94 мог использоваться вплоть до 2010-х годов.

Сравнение с последующими стандартами

Источники

• ГОСТ Р 34.10-94. Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на основе асимметричного криптографического алгоритма. — М.: ИПК Издательство стандартов, 1994.
• ГОСТ Р 34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. — М.: ИПК Издательство стандартов, 2001.
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. — М.: Стандартинформ, 2012.
• Шнайер Б. Прикладная криптография. — М.: Триумф, 2002. — 816 с.
• Материалы Академии криптографии РФ (1994–2002).