ГОСТ 34.10-2018

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «ГОСТ Р 34.10-2001»)

ГОСТ 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 мая 94 года
Межгосударственный ГОСТ 34.310-95 16 апреля 1998 года ГОСТ 34.311-95
Национальный ГОСТ Р 34.10-2001 1 июля 2002 года ГОСТ Р 34.11-94 Принят постановлением Госстандарта России № 380-ст от 12 сентября 2001 года[1]
Межгосударственный ГОСТ 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 бит (второй вариант формирования ЭЦП, описанный в стандарте) все преобразования аналогичны.

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

  • простое число [math]\displaystyle{ p }[/math] — модуль эллиптической кривой такой, что [math]\displaystyle{ p\gt 2^{255} }[/math]
  • эллиптическая кривая [math]\displaystyle{ E }[/math] задаётся своим инвариантом [math]\displaystyle{ J(E) }[/math] или коэффициентами [math]\displaystyle{ a,b\in F_p }[/math], где [math]\displaystyle{ F_p }[/math] — конечное поле из p элементов. [math]\displaystyle{ J(E) }[/math] связан с коэффициентами [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] следующим образом
[math]\displaystyle{ J(E)=1728\frac{4a^3}{4a^3+27b^2}\pmod{p} }[/math], причём [math]\displaystyle{ 4a^3+27b^2\not\equiv 0\pmod{p} }[/math].
  • целое число [math]\displaystyle{ m }[/math] — порядок группы точек эллиптической кривой, [math]\displaystyle{ m }[/math] должно быть отлично от [math]\displaystyle{ p }[/math]
  • простое число [math]\displaystyle{ q }[/math], порядок некоторой циклической подгруппы группы точек эллиптической кривой, то есть выполняется [math]\displaystyle{ m=nq }[/math], для некоторого [math]\displaystyle{ n\in\N }[/math]. Также [math]\displaystyle{ q }[/math] лежит в пределах [math]\displaystyle{ 2^{254}\lt q\lt 2^{256} }[/math].
  • точка [math]\displaystyle{ P=(x_P,\;y_P) }[/math] эллиптической кривой [math]\displaystyle{ E }[/math], являющаяся генератором подгруппы порядка [math]\displaystyle{ q }[/math], то есть [math]\displaystyle{ q\cdot P=\mathbf{0} }[/math] и [math]\displaystyle{ k\cdot P\ne \mathbf{0} }[/math] для всех k = 1, 2, …, q-1, где [math]\displaystyle{ \mathbf{0} }[/math] — нейтральный элемент группы точек эллиптической кривой E.
  • [math]\displaystyle{ h(M) }[/math] — хеш-функция (ГОСТ Р 34.11-2012), которая отображает сообщения M в двоичные векторы длины 256 бит.

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

  • ключ шифрования [math]\displaystyle{ d }[/math] — целое число, лежащее в пределах [math]\displaystyle{ 0\lt d\lt q }[/math].
  • ключ расшифрования [math]\displaystyle{ Q=(x_Q,\;y_Q) }[/math], вычисляемый как [math]\displaystyle{ Q = d\cdot P }[/math].

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

  • [math]\displaystyle{ p^t\neq 1 \pmod{q} }[/math], [math]\displaystyle{ \forall t=1..B }[/math], где [math]\displaystyle{ B\geq 31 }[/math]
  • [math]\displaystyle{ J(E)\neq 0 }[/math] и [math]\displaystyle{ J(E)\neq 1728 }[/math]

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

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

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

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

Блок-схемы:

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

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

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

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

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

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

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

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

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

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

Один из самых быстрых алгоритмов, на данный момент, при правильном выборе параметров — [math]\displaystyle{ \rho }[/math]-метод и [math]\displaystyle{ \Iota }[/math]-метод Полларда.[4]

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

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

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

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

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

Использование математического аппарата группы точек эллиптической кривой позволяет существенно сократить порядок модуля [math]\displaystyle{ p }[/math] без потери криптостойкости.[2]

Также старый стандарт описывает механизмы получения чисел [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] и [math]\displaystyle{ a }[/math].

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

Примечания

  1. ↑ О принятии и введении в действие государственного стандарта. Постановление Госстандарта РФ от 12.09.2001 N 380-ст (недоступная ссылка). bestpravo.ru. Дата обращения: 1 сентября 2019. Архивировано 1 сентября 2019 года.
  2. ↑ 2,0 2,1 2,2 2,3 Игоничкина Е. В. Анализ алгоритмов электронной цифровой подписи. Дата обращения: 16 ноября 2008. Архивировано 15 января 2012 года.
  3. ↑ Семёнов Г. Цифровая подпись. Эллиптические кривые. «Открытые системы» № 7-8/2002 (8 августа 2002). Дата обращения: 16 ноября 2008. Архивировано 31 декабря 2012 года.
  4. ↑ Бондаренко М. Ф., Горбенко И. Д., Качко Е. Г., Свинарев А. В., Григоренко Т. А. Сущность и результаты исследований свойств перспективных стандартов цифровой подписи X9.62-1998 и распределения ключей X9.63-199X на эллиптических кривых. Дата обращения: 16 ноября 2008. Архивировано 22 февраля 2012 года.
  5. ↑ 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
  6. ↑ 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
  7. ↑ 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)
  8. ↑ Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (декабрь 2008). — Internet-Drafts, work in progress. Дата обращения: 12 июня 2009. Архивировано 24 августа 2011 года.
  9. ↑ 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. Дата обращения: 12 июня 2009. Архивировано 24 августа 2011 года.
  10. ↑ V. Dolmatov, Ed. Use of GOST signature algorithms in DNSKEY and RRSIG Resource Records for DNSSEC (англ.) (апрель 2009). — Internet-Drafts, work in progress. Дата обращения: 12 июня 2009. Архивировано 22 февраля 2012 года.

Ссылки

  • Текст стандарта ГОСТ Р 34.10-94 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма»
  • Текст стандарта ГОСТ Р 34.10-2001 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи»
  • Текст стандарта ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи»
  • Текст стандарта ГОСТ 34.10-2018 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи»
Программные реализации
Аппаратные реализации
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=ГОСТ_34.10-2018&oldid=5871545