ГОСТ Р 34.10-2001

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

Содержание

1 Область применения
2 История
3 Описание
4 Алгоритм
5 Криптостойкость
6 Отличия от ГОСТ 34.10-94 (старый стандарт)
7 Возможные применения
8 Примечания
9 Ссылки

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

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

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

История

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

Описание

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

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

Сообщение М

Цифровая подпись

Текст

Дополнение

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

Алгоритм

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

простое число $p$ — модуль эллиптической кривой такой, что $p>2^{255}$
эллиптическая кривая $E$ задаётся своим инвариантом $J(E)$ или коэффициентами $a,b\in F_p$ , где $F_p$ — конечное поле из p элементов. $J(E)$ связан с коэффициентами $a$ и $b$ следующим образом

$J(E)=1728\frac{4a^3}{4a^3+27b^2}\pmod{p}$ , причём $4a^3+27b^2\not\equiv 0\pmod{p}$ .

целое число $m$ — порядок группы точек эллиптической кривой, $m$ должно быть отлично от $p$
простое число $q$ , порядок некоторой циклической подгруппы группы точек эллиптической кривой, то есть выполняется $m=nq$ , для некоторого $n\in\N$ . Так же $q$ лежит в пределах $2^{254}<q<2^{256}$ .
точка $P=(x_P,\;y_P)$ эллиптической кривой $E$ , являющаяся генератором подгруппы порядка $q$ , то есть $q\cdot P=\mathbf{0}$ и $k\cdot P\ne \mathbf{0}$ для всех k = 1, 2, …, q-1, где $\mathbf{0}$ — нейтральный элемент группы точек эллиптической кривой E.
$h(M)$ — хэш-функция (ГОСТ Р 34.11-94), которая отображает сообщения M в двоичные векторы длины 256 бит.

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

ключ шифрования $d$ — целое число, лежащее в пределах $0<d<q$ .
ключ расшифрования $Q=(x_Q,\;y_Q)$ , вычисляемый как $Q = d\cdot P$ .

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

$p^t\neq 1 \pmod{q}$ , $\forall t=1..B$ , где $B\geq 31$
$J(E)\neq 0$ и $J(E)\neq 1728$

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

Между двоичными векторами длины 256 $\bar{h}=(\alpha_{255},...,\alpha_0)$ и целыми числами $z\leq 2^{256}$ ставится взаимно-однозначное соответствие по следующему правилу $z=\sum^{255}_{i=0}\alpha_i2^i$ . Здесь $\alpha_i$ либо равно 0, либо равно 1. Другими словами, $\bar{h}$ — это двоичное представление числа z.

Результатом операции конкатенации двух векторов $\bar{h_1}=(\alpha_{255},...,\alpha_0)$ и $\bar{h_2}=(\beta_{255},...,\beta_0)$ называется вектор длины 512 $(\bar{h_1}|\bar{h_2})=(\alpha_{255},...,\alpha_0,\beta_{255},...,\beta_0)$ . Обратная операция — операция разбиения одного вектора длины 512 на два вектора длины 256.

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

Блок-схемы:

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

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

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

Вычисление по цифровой подписи $\xi$ чисел $r$ и $s$ , учитывая, что $\xi=(\bar{r}|\bar{s})$ , где $r$ и $s$ — числа, соответствующие векторам $\bar{r}$ и $\bar{s}$ . Если хотя бы одно из неравенств $r<q$ и $s<q$ неверно, то подпись неправильная.
Вычисление хэш-функции от сообщения М: $\bar{h} = h(M).$
Вычисление $e=z\,\bmod\,q$ , и если $e=0$ , положить $e=1$ . Где $z$ — целое число соответствующее $\bar{h}.$
Вычисление $\nu=e^{-1}\,\bmod\,q.$
Вычисление $z_1=s\nu\,\bmod\,q$ и $z_2=-r\nu\,\bmod\,q.$
Вычисление точки эллиптической кривой $C=z_1P+z_2Q$ . И определение $R=x_c\,\bmod\,q$ , где $x_c$ — координата $x$ кривой $C.$
В случае равенства $R=r$ подпись правильная, иначе — неправильная.

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

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

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

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

Для оптимизированного $\rho$ -метода Полларда вычислительная сложность оценивается как $O(\sqrt{q})$ . Таким образом для обеспечения криптостойкости ${10}^{30}$ операций необходимо использовать 256-разрядное $q$ .^[1]

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

Новый и старый ГОСТы цифровой подписи очень похожи друг на друга. Основное отличие — в старом стандарте часть операций проводится над полем $\mathbb{Z}_p$ , а в новом — над группой точек эллиптической кривой, поэтому требования налагаемые на простое число $p$ в старом стандарте( $2^{509}<p<2^{512}$ или $2^{1020}<p<2^{1024}$ ) более жёсткие, чем в новом.

Алгоритм формирования подписи отличается только в пункте 4. В старом стандарте в этом пункте вычисляются $\tilde{r}=a^k\,\bmod\,p$ и $r=\tilde{r}\,\mod\,q$ и, если $r=0$ , возвращаемся к пункту 3. Где $1<a<p-1$ и $a^q=1\,\bmod\,q$ .

Алгоритм проверки подписи отличается только в пункте 6. В старом стандарте в этом пункте вычисляется $R = (a^{z_1}y^{z_2}\,\bmod\,p)\,\bmod\,q$ , где $y$ — открытый ключ для проверки подписи, $y=a^d\,\bmod\,p$ . Если $R=r$ , подпись правильная, иначе неправильная. Здесь $q$ — простое число, $2^{254}<q<2^{256}$ и $q$ является делителем $p-1$ .

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

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

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

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

Примечания

↑ ¹ ² ³ ⁴ Игоничкина Е. В. Анализ алгоритмов электронной цифровой подписи. Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.
↑ Семёнов Г. Цифровая подпись. Эллиптические кривые. «Открытые системы» № 7-8/2002 (8 августа 2002). Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.
↑ Бондаренко М. Ф., Горбенко И. Д., Качко Е. Г., Свинарев А. В., Григоренко Т. А. Сущность и результаты исследований свойств перспективных стандартов цифровой подписи X9.62-1998 и распределения ключей X9.63-199X на эллиптических кривых. Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.
↑ RFC 4357, глава 5.2, «VKO GOST R 34.10-2001» — Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms
↑ RFC 4491 — Using the GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms with the Internet X.509 Public Key Infrastructure
↑ RFC 4490 — Using the GOST 28147-89, GOST R 34.11-94, GOST R 34.10-94, and GOST R 34.10-2001 Algorithms with Cryptographic Message Syntax (CMS)
↑ Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (декабрь 2008). — Internet-Drafts, work in progress. Архивировано из первоисточника 24 августа 2011. Проверено 12 июня 2009.
↑ S. Leontiev, P. Smirnov, A. Chelpanov. Using GOST 28147-89, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms for XML Security (англ.) (декабрь 2008). — Internet-Drafts, work in progress. Архивировано из первоисточника 24 августа 2011. Проверено 12 июня 2009.
↑ V. Dolmatov, Ed. Use of GOST signature algorithms in DNSKEY and RRSIG Resource Records for DNSSEC (англ.) (апрель 2009). — Internet-Drafts, work in progress. Архивировано из первоисточника 22 февраля 2012. Проверено 12 июня 2009.

Ссылки

ГОСТ Р 34.10-2001. Информационные технологии. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. (2001). Архивировано из первоисточника 22 февраля 2012. Проверено 11 августа 2009.
ГОСТ Р 34.10-94. Информационные технологии. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма. (1995). Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.

Программные реализации

Верба-W, Верба-OW. — криптографические проекты компании ЗАО «МО ПНИЭИ». Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.
ГОСТы для OpenSSL. — криптографический проект компании ООО «Криптоком» по добавлению российских криптографических алгоритмов в библиотеку OpenSSL. Архивировано из первоисточника 24 августа 2011. Проверено 16 ноября 2008.
КриптоПро CSP. — криптографический проект компании «Крипто-Про». Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.
Крипто-КОМ. — криптографический проект компании ЗАО «Сигнал-КОМ». Архивировано из первоисточника 22 февраля 2012. Проверено 16 ноября 2008.
LISSICryptoLib. — кроссплатформенная криптографическая библиотека компании ООО «ЛИССИ». Архивировано из первоисточника 19 мая 2012. Проверено 16 ноября 2008.
Крипто-Си. — программная библиотека защиты информации компании ООО «КриптоЭкс».(недоступная ссылка — история) Проверено 16 ноября 2008.
Домен-КС2, Домен-КМ. — программные комплексы, средства криптографической защиты информации компании ОАО «ИнфоТеКС». Архивировано из первоисточника 22 февраля 2012. Проверено 03 мая 2009.
GOST 2.0. Архивировано из первоисточника 22 февраля 2012. Проверено 13 мая 2009.

Аппаратные реализации

Шипка. — программно-аппаратный криптографический комплекс компании ОКБ САПР.(недоступная ссылка — история) Проверено 16 ноября 2008.

Криптосистемы с открытым ключом
RSA • DSA • DSS • NTRUEncrypt • Эль-Гамаля • Меркля — Хеллмана • Шнорра • Эллиптические • ГОСТ Р 34.10-2001 • ДСТУ 4145-2002

Категории:

Стандарты криптографии
ГОСТ

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное

Смотреть что такое "ГОСТ Р 34.10-2001" в других словарях:

ГОСТ Р ИСО 9000-2001 — „Системы менеджмента качества. Основные положения и словарь“ описывает основные положения систем менеджмента качества и устанавливает терминологию для систем менеджмента качества. Разработан Всероссийским научно исследовательским институтом… … Википедия
ГОСТ Р ИСО 9001-2001 — «Системы менеджмента качества. Требования» устанавливает требования к системе менеджмента качества, которые могут использоваться для внутреннего применения организациями, в целях сертификации или заключения контрактов. Он направлен на… … Википедия
ГОСТ 12.4.034-2001 — (ЕН 133 90) 7 с. (2) Система стандартов безопасности труда. Средства индивидуальной защиты органов дыхания. Классификация и маркировка Взамен: ГОСТ 12.4.034 85 раздел 13.340.30 … Указатель национальных стандартов 2013
ГОСТ 12.4.041-2001 — 7 с. (2) Система стандартов безопасности труда. Средства индивидуальной защиты органов дыхания фильтрующие. Общие технические требования Взамен: ГОСТ 12.4.041 89 раздел 13.340.30 … Указатель национальных стандартов 2013
ГОСТ 12.4.129-2001 — 9 с. (3) Система стандартов безопасности труда. Обувь специальная, средства индивидуальной защиты рук, одежда специальная и материалы для их изготовления. Метод определения проницаемости нефти и нефтепродуктов Взамен: ГОСТ 12.4.129 83 раздел… … Указатель национальных стандартов 2013
ГОСТ 13.1.401-2001 — 8 с. (2) Репрография. Микрография. Аппараты для съемки микрофильмов. Технические требования Взамен: ГОСТ 13.1.401 74 раздел 37.080 … Указатель национальных стандартов 2013
ГОСТ 13.2.001-2001 — 12 с. (3) Репрография. Копирография. Аппараты копировальные электрофотографические. Общие технические требования Взамен: ГОСТ 13.2.001 90 раздел 37.080 … Указатель национальных стандартов 2013
ГОСТ ИСО 4378-1-2001 — 20 с. (4) Подшипники скольжения. Термины, определения и классификация. Часть 1. Конструкция, подшипниковые материалы и их свойства Взамен: ГОСТ 18282 88 разделы 01.040.21, 21.100.10 … Указатель национальных стандартов 2013
ГОСТ ИСО 8124-2-2001 — Утратил силу в РФ Пользоваться: ГОСТ Р ИСО 8124 2 2008 … Указатель национальных стандартов 2013
ГОСТ Р 41.34-2001 — (Правила ЕЭК ООН № 34) 19 с. (4) Единообразные предписания, касающиеся официального утверждения транспортных средств в отношении предотвращения опасности возникновения пожара Взамен: ГОСТ Р 50464 93 раздел 43.020 … Указатель национальных стандартов 2013

Словари и энциклопедии на Академике

ГОСТ Р 34.10-2001

Содержание

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

История

Описание