ГОСТ 34.10-2018

ГОСТ 34.10-2018 (полное название: «ГОСТ 34.10-2018. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи», англ. «Information technology. Cryptographic data security. Signature and verification processes of electronic digital signature») — действующий межгосударственный криптографический стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи реализуемой с использованием операций в группе точек эллиптической кривой, определенной над конечным простым полем.

Стандарт разработан на основе национального стандарта Российской Федерации ГОСТ Р 34.10-2012 и введен в действие с 1 июня 2019 года приказом Росстандарта № 1059-ст от 4 декабря 2018 года.

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

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

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

ИсторияПравить

Первые версии алгоритма разрабатывались Главным управлением безопасности связи ФАПСИ при участии Всероссийского научно-исследовательского института стандартизации (ВНИИстандарт), позже разработка перешла в руки Центра защиты информации и специальной связи ФСБ России и АО «ИнфоТеКС».

ОписаниеПравить

Криптографическая стойкость первых стандартов цифровой подписи ГОСТ Р 34.10-94 и ГОСТ 34.310-95 была основана на задаче дискретного логарифмирования в мультипликативной группе простого конечного поля большого порядка. Начиная с ГОСТ Р 34.10-2001 стойкость алгоритма основана на более сложной задаче вычисления дискретного логарифма в группе точек эллиптической кривой. Также стойкость алгоритма формирования цифровой подписи основана на стойкости соответствующей хеш-функции:

Тип	Наименование	Введен в действие	Функция хеширования	Приказ
Национальный	ГОСТ Р 34.10-94	1 января 1995 года	ГОСТ Р 34.11-94	Принят постановлением Госстандарта России № 154 от 23 мая 1994 года
Межгосударственный	ГОСТ 34.310-95	16 апреля 1998 года	ГОСТ 34.311-95
Национальный	ГОСТ Р 34.10-2001	1 июля 2002 года	ГОСТ Р 34.11-94	Принят постановлением Госстандарта России № 380-ст от 12 сентября 2001 года
Межгосударственный	ГОСТ 34.310-2004	2 марта 2004 года	ГОСТ 34.311-95	Принят Евразийским советом по стандартизации, метрологии и сертификации по переписке (протокол № 16 от 2 марта 2004 года)
Национальный	ГОСТ Р 34.10-2012	1 января 2013 года	ГОСТ Р 34.11-2012	Утверждён и введен в действие приказом Федерального агентства по техническому регулированию и метрологии № 215-ст от 7 августа 2012 года в качестве национального стандарта Российской Федерации с 1 января 2013 года
Межгосударственный	ГОСТ 34.10-2018	1 июня 2019 года	ГОСТ 34.11-2018	Принят Межгосударственным советом по метрологии, стандартизации и сертификации (протокол № 54 от 29 ноября 2018 года). Приказом Федерального агентства по техническому регулированию и метрологии № 1059-ст от 4 декабря 2018 г. введен в действие в качестве национального стандарта Российской Федерации с 1 июня 2019 года

Стандарты используют одинаковую схему формирования электронной цифровой подписи. Новые стандарты с 2012 года отличаются наличием дополнительного варианта параметров схем, соответствующего длине секретного ключа порядка 512 бит.

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

Сообщение М	+	Цифровая подпись Текст
		Дополнение

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

АлгоритмПравить

Приводится описание варианта схемы ЭЦП с длиной секретного ключа 256 бит. Для секретных ключей длиной 512 бит (второй вариант формирования ЭЦП, описанный в стандарте) все преобразования аналогичны.

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

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

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

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

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

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

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

• $p^t\ne <!--\; \ne \; -->1(\mathrm{mod}q)$$p^{t}\neq 1{\pmod {q}}$ , $\mathrm{\forall <!--\; \forall \; -->}t=\mathrm{1..}B$$\forall t=1..B$ , где $B\ge <!--\; \ge \; -->31$$B\geq 31$ 
• $J(E)\ne <!--\; \ne \; -->0$$J(E)\neq 0$  и $J(E)\ne <!--\; \ne \; -->1728$$J(E)\neq 1728$ 

Двоичные векторыПравить

Между двоичными векторами длины 256 $\stackrel{¯<!--\; ¯\; -->}{h}=({\mathrm{\alpha <!--\; \alpha \; -->}}_{255},...,{\mathrm{\alpha <!--\; \alpha \; -->}}_0)$${\bar {h}}=(\alpha _{{255}},...,\alpha _{0})$  и целыми числами $z\le <!--\; \le \; -->2^{256}$$z\leq 2^{{256}}$  ставится взаимно-однозначное соответствие по следующему правилу $z=\underset{i=0}{\overset{255}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}_i{2}^i$$z=\sum _{{i=0}}^{{255}}\alpha _{i}2^{i}$ . Здесь ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  либо равно 0, либо равно 1. Другими словами, $\stackrel{¯<!--\; ¯\; -->}{h}$${\bar {h}}$  — это представление числа z в двоичной системе счисления.

Результатом операции конкатенации двух векторов $\stackrel{¯<!--\; ¯\; -->}{h_1}=({\mathrm{\alpha <!--\; \alpha \; -->}}_{255},...,{\mathrm{\alpha <!--\; \alpha \; -->}}_0)$${\bar {h_{1}}}=(\alpha _{{255}},...,\alpha _{0})$  и $\stackrel{¯<!--\; ¯\; -->}{h_2}=({\mathrm{\beta <!--\; \beta \; -->}}_{255},...,{\mathrm{\beta <!--\; \beta \; -->}}_0)$${\bar {h_{2}}}=(\beta _{{255}},...,\beta _{0})$  называется вектор длины 512 $(\stackrel{¯<!--\; ¯\; -->}{h_1}|\stackrel{¯<!--\; ¯\; -->}{h_2})=({\mathrm{\alpha <!--\; \alpha \; -->}}_{255},...,{\mathrm{\alpha <!--\; \alpha \; -->}}_0,{\mathrm{\beta <!--\; \beta \; -->}}_{255},...,{\mathrm{\beta <!--\; \beta \; -->}}_0)$$({\bar {h_{1}}}|{\bar {h_{2}}})=(\alpha _{{255}},...,\alpha _{0},\beta _{{255}},...,\beta _{0})$ . Обратная операция — операция разбиения одного вектора длины 512 на два вектора длины 256.

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

Блок-схемы:

•  

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

•  

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

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

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

1. Вычисление по цифровой подписи $\mathrm{\xi <!--\; \xi \; -->}$$\xi$  чисел $r$$r$  и $s$$s$ , учитывая, что $\mathrm{\xi <!--\; \xi \; -->}=(\stackrel{¯<!--\; ¯\; -->}{r}|\stackrel{¯<!--\; ¯\; -->}{s})$$\xi =({\bar {r}}|{\bar {s}})$ , где $r$$r$  и $s$$s$  — числа, соответствующие векторам $\stackrel{¯<!--\; ¯\; -->}{r}$${\bar {r}}$  и $\stackrel{¯<!--\; ¯\; -->}{s}$${\bar {s}}$ . Если хотя бы одно из неравенств $r<q$  и $s<q$  неверно, то подпись неправильная.
2. Вычисление хеш-функции от сообщения М: $\stackrel{¯<!--\; ¯\; -->}{h}=h(M).$${\bar {h}}=h(M).$ 
3. Вычисление $e=zmodq$$e=z\,{\bmod \,}q$ , и если $e=0$$e=0$ , положить $e=1$$e=1$ . Где $z$$z$  — целое число соответствующее $\stackrel{¯<!--\; ¯\; -->}{h}.$${\bar {h}}.$ 
4. Вычисление $\mathrm{\nu <!--\; \nu \; -->}=e^{-<!--\; -\; -->1}modq.$$\nu =e^{{-1}}\,{\bmod \,}q.$ 
5. Вычисление $z_1=s\mathrm{\nu <!--\; \nu \; -->}modq$$z_{1}=s\nu \,{\bmod \,}q$  и $z_2=-<!--\; -\; -->r\mathrm{\nu <!--\; \nu \; -->}modq.$$z_{2}=-r\nu \,{\bmod \,}q.$ 
6. Вычисление точки эллиптической кривой $C=z_{1}P+z_{2}Q$$C=z_{1}P+z_{2}Q$ . И определение $R=x_{c}modq$$R=x_{c}\,{\bmod \,}q$ , где $x_c$$x_{c}$  — координата $x$$x$  точки $C.$$C.$ 
7. В случае равенства $R=r$$R=r$  подпись правильная, иначе — неправильная.

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

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

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

Один из самых быстрых алгоритмов, на данный момент, при правильном выборе параметров — $\mathrm{\rho <!--\; \rho \; -->}$$\rho$ -метод и $\mathrm{I}$$\mathrm{I}$ -метод Полларда.

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

Отличия от ГОСТ Р 34.10-94 (стандарт 1994—2001 гг)Править

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

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

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

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

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

Возможные примененияПравить

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

СсылкиПравить

• Текст стандарта ГОСТ Р 34.10-94 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма»
• Текст стандарта ГОСТ Р 34.10-2001 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи»
• Текст стандарта ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи»
• Текст стандарта ГОСТ 34.10-2018 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи»

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

• МагПро КриптоПакет  (неопр.). — криптографический проект компании ООО «Криптоком» по добавлению российских криптографических алгоритмов в библиотеку OpenSSL.
• Проект Эталонная реализация российских алгоритмов шифрования в openssl на сайте GitHub
• КриптоПро CSP — криптографический проект компании «Крипто-Про».
• Signal-COM CSP  (неопр.). — криптографический проект компании ЗАО «Сигнал-КОМ».
• ЛИРССЛ-CSP  (неопр.). — кроссплатформенная криптографическая библиотека компании ООО «ЛИССИ».
• ViPNet CSP  (неопр.). — программные комплексы, средства криптографической защиты информации компании ОАО «ИнфоТеКС».
• Проект WebCrypto GOST Javascript библиотека на сайте GitHub
• Libgcrypt^[en]
• Bouncy Castle

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

• Рутокен ЭЦП 2.0
• JaCarta-2 ГОСТ
• ESMART Token ГОСТ  (неопр.). Архивировано из оригинала 15 июля 2017 года.
• MS_KEY K «Ангара»  (неопр.). Архивировано из оригинала 27 декабря 2017 года.