ФЭНДОМ


ГОСТ Р 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>2^{255}
  • эллиптическая кривая E задается своим инвариантом J(E) или коэффициентами a,b\in F_p, где F_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)\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. Здесь \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.

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

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

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

  1. Вычисление по цифровой подписи \xi чисел 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\pmod{q}, и если e=0, положить e=1. Где z — целое число соотвествующее \bar{h}
  4. Вычисление \nu=e^{-1}\pmod{q}.
  5. Вычисление z_1=s\nu\pmod{q} и z_2=-r\nu\pmod{q}
  6. <span id="verification6" />Вычисление точки эллиптической кривой C=z_1P+z_2Q. И определение R=x_c\pmod{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 (старый стандарт)<span id="oldGost" /> Править

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

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

Алгоритм проверки подписи отличается только в пункте 6. В старом стандарте в этом пункте вычисляется R = (a^{z1}y^{z2}\pmod{p})\pmod{q}. Если R=r, подпись правильная, иначе неправильная. Где y — открытый ключ для проверки подписи, y=a^d\pmod{p}.

Здесь q — простое число, 2^{254}<q<2^{256} и q является делителем p-1.

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

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

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

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

  1. 1,0 1,1 1,2 1,3 Игоничикна Е. В. Анализ алгоритмов электронной цифровой подписиПроверено 16 ноября 2008.
  2. Коржев В. (8 августа 2002) Цифровая подпись. Эллиптические кривые. «Открытые системы» № 7-8/2002.  Проверено 16 ноября 2008.
  3. Бондаренко М. Ф., Горбенко И. Д., Качко Е. Г., Свинарев А. В., Григоренко Т. А. Сущность и результаты исследований свойств перспективных стандартов цифровой подписи X9.62-1998 и распределения ключей X9.63-199X на эллиптических кривыхПроверено 16 ноября 2008.
  4. Popov М., Kurepkin I., Leontiev S. (January 2006) 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 4357 (глава 5.2, «VKO GOST R 34.10-2001»).  Проверено 16 ноября 2008.
  5. Leontiev S., Shefanovski D. (May 2006) 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 4491Проверено 16 ноября 2008.
  6. Leontiev S., Chudov G. (May 2006) 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) (англ.). — RFC 4490Проверено 16 ноября 2008.

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

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

Обнаружено использование расширения AdBlock.


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

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики