ГОСТ Р 34.10-2001

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

Содержание

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

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

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

[править] История

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

[править] Описание

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

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

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

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

[править] Алгоритм

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

  • простое число p — модуль эллиптической кривой такой, что p > 2255
  • эллиптическая кривая E задается своим инвариантом J(E) или коэффициентами a,b\in F_p, где Fp — конечное простое поле. 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 лежит в пределах 2254 < q < 2256.
  • точка P(x_P,\;y_P)\neq0 эллиптической кривой E, являющаяся генератором подгруппы порядка q, или другими словами qP = 0. Здесь qP = P + P + ...(q раз). А 0 - нулевой элемент группы точек эллиптической кривой.
  • h(M) — хэш-функция (ГОСТ Р 34.11-94), которая конечные сообщения M отображет в двоичные вектора длины 256 бит.

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

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

При этом должны выполняться

  • 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. Здесь α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.

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

Блок-схемы:

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

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

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

  1. Вычисление по цифровой подписи ξ чисел r и s, учитывая, что \xi=(\bar{r}|\bar{s}), где r и s — числа, соответствующие векторам \bar{r} и \bar{s}. Если хотя бы одно из неравенств r < q и s < q неверно, то подпись неправильная.
  2. Вычисление хэш-функции от сообщения М: \bar{h} = h(M)
  3. Вычисление e = z(mod q), и если e = 0, положить e = 1. Где z — целое число соотвествующее \bar{h}
  4. Вычисление ν = e − 1(mod q).
  5. Вычисление z1 = sν(mod q) и z2 = − rν(mod q)
  6. Вычисление точки эллиптической кривой C = z1P + z2Q. И определение R = xc(mod q), где xc — координата x кривой C. В случае равенства R = r подпись правильная, иначе — неправильная.

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

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

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

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

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

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

Новый и старый ГОСТы цифровой подписи очень похожи друг на друга. Основное отличие — в старом стандарте часть операций проводится над полем \mathbb{Z}_p, а в новом — над группой точек эллиптической кривой, поэтому требования налагаемые на простое число p в старом стандарте(2509 < p < 2512 или 21020 < p < 21024) более жесткие, чем в новом.

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

Алгоритм проверки подписи отличается только в пункте 6. В старом стандарте в этом пункте вычисляется R = (az1yz2(mod p))(mod q). Если R = r, подпись правильная, иначе неправильная. Где y — открытый ключ для проверки подписи, y = ad(mod p).

Здесь q — простое число, 2254 < q < 2256 и q является делителем p − 1.

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

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

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

[править] Примечания

  1. ↑ 1 2 3 4 Игоничкина Е. В. Анализ алгоритмов электронной цифровой подписи. Проверено 16 ноября 2008.
  2. ↑ Коржев В. Цифровая подпись. Эллиптические кривые. «Открытые системы» № 7-8/2002 (8 августа 2002). Проверено 16 ноября 2008.
  3. ↑ Бондаренко М. Ф., Горбенко И. Д., Качко Е. Г., Свинарев А. В., Григоренко Т. А. Сущность и результаты исследований свойств перспективных стандартов цифровой подписи X9.62-1998 и распределения ключей X9.63-199X на эллиптических кривых. Проверено 16 ноября 2008.
  4. ↑ Popov М., Kurepkin I., Leontiev S. 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 (англ.) (January 2006). — RFC 4357 (глава 5.2, «VKO GOST R 34.10-2001»). Проверено 16 ноября 2008.
  5. ↑ Leontiev S., Shefanovski D. 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 (англ.) (May 2006). — RFC 4491. Проверено 16 ноября 2008.
  6. ↑ Leontiev S., Chudov G. 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) (англ.) (May 2006). — RFC 4490. Проверено 16 ноября 2008.
  7. ↑ Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 12 июня 2009.
  8. ↑ 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 (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 12 июня 2009.
  9. ↑ V.Dolmatov, Ed. Use of GOST signature algorithms in DNSKEY and RRSIG Resource Records for DNSSEC (англ.) (April 2009). — Internet-Drafts, work in progress. Проверено 12 июня 2009.

[править] Ссылки

Программные реализации
  • Верба-W, Верба-OW. — криптографические проекты компании ЗАО «МО ПНИЭИ». Проверено 16 ноября 2008.
  • Патч для OpenSSL. — криптографический проект компании ООО «Криптоком» по добавлению российских криптографических алгоритмов в библиотеку OpenSSL. Проверено 16 ноября 2008.
  • КриптоПро CSP. — криптографический проект компании «Крипто-Про». Проверено 16 ноября 2008.
  • Крипто-КОМ. — криптографический проект компании ЗАО «Сигнал-КОМ». Проверено 16 ноября 2008.
  • LISSICryptoLib. — кроссплатформенная криптографическая билиотека компании ООО «ЛИССИ». Проверено 16 ноября 2008.
  • Крипто-Си. — программная библиотека защиты информации компании ООО «КриптоЭкс». Проверено 16 ноября 2008.
  • Домен-КС2, Домен-КМ. — программные комплексы, средства криптографической защиты информации компании ОАО «ИнфоТеКС». Проверено 03 мая 2009.
Аппаратные реализации
  • Шипка. — программно-аппаратный криптографический комплекс компании ОКБ САПР. Проверено 16 ноября 2008.
Криптографические алгоритмы с парой открытый/закрытый ключ

RSA • DSA • Схема Эль-Гамаля • ГОСТ Р 34.10-2001

 
Источник — «http://ru.wikipedia.org/wiki/%D0%93%D0%9E%D0%A1%D0%A2_%D0%A0_34.10-2001»