ГОСТ 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>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}(\mathrm{mod}p)$, причём $4a^3+27b^2\equiv ̸0(\mathrm{mod}p)$.

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

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

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

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

• $p^t\ne 1(\mathrm{mod}q)$, $\mathrm{\forall }t=1..B$, где $B\ge 31$
• $J(E)\ne 0$ и $J(E)\ne 1728$

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

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

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

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

Блок-схемы:

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

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

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

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

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

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

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

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

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

Отличия от ГОСТ Р 34.10-94 (стандарт 1994—2001 гг)Шаблон:Anchor

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

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

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

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

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

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

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

Ссылки

• Текст стандарта Шаблон:ГОСТ
• Текст стандарта Шаблон:ГОСТ
• Текст стандарта Шаблон:ГОСТ
• Текст стандарта Шаблон:ГОСТ

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

• Шаблон:Cite web
• Шаблон:Github
• КриптоПро CSP — криптографический проект компании «Крипто-Про».
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Github
• Шаблон:Нп5
• Bouncy Castle

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

• Рутокен ЭЦП 2.0
• JaCarta-2 ГОСТ
• Шаблон:Cite web
• Шаблон:Cite web