Отечественный стандарт цифровой подписи ГОСТ 3410

В отечественном стандарте ГОСТ 3410, принятом в 1994 году, используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ElGamal.

В стандарте ГОСТ 3410 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q:

1. р должно быть простым числом в диапазоне

1. q должно быть простым числом в диапазоне

q также должно быть делителем (р-1).

Аналогично выбирается и параметр g. При этом требуется, чтобы g^q (mod p) = 1.

В соответствии с теоремой Ферма это эквивалентно условию в DSS, что g = h^(p-1)/q mod p.

Закрытым ключом является произвольное число х

Открытым ключом является число y

Для создания подписи выбирается случайное число k

Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:

Еще раз обратим внимание на отличия DSS и ГОСТ 3410.

1. Используются разные хэш-функции: в ГОСТ 3410 применяется отечественный стандарт на хэш-функции ГОСТ 3411, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 3410 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.
2. По-разному вычисляется компонента s подписи. В ГОСТ 3410 компонента s вычисляется по формуле

В DSS компонента s вычисляется по формуле

Последнее отличие приводит к соответствующим отличиям в формулах для проверки подписи.

Получатель вычисляет

Структура обоих алгоритмов довольно интересна. Заметим, что значение r совсем не зависит от сообщения. Вместо этого r есть функция от k и трех общих компонент открытого ключа. Мультипликативная инверсия k (mod p) (в случае DSS) или само значение k (в случае ГОСТ 3410) подается в функцию, которая, кроме того, в качестве входа имеет хэш-код сообщения и закрытый ключ пользователя. Эта функция такова, что получатель может вычислить r, используя входное сообщение, подпись, открытый ключ пользователя и общий открытый ключ.

В силу сложности вычисления дискретных логарифмов нарушитель не может восстановить k из r или х из s.

Другое важное замечание заключается в том, что экспоненциальные вычисления при создании подписи необходимы только для g^k mod p. Так как это значение от подписываемого сообщения не зависит, оно может быть вычислено заранее. Пользователь может заранее просчитать некоторое количество значений r и использовать их по мере необходимости для подписи документов. Еще одна задача состоит в определении мультипликативной инверсии k^-1 (в случае DSS). Эти значения также могут быть вычислены заранее.

Подписи, созданные с использованием стандартов ГОСТ 3410 или DSS, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (r,s), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.

11. Лекция: Криптография с использованием эллиптических кривых: Рассматривается криптография с использованием эллиптических кривых. Описаны математические понятия, связанные с эллиптическими кривыми, в частности задача дискретного логарифмирования на эллиптической кривой. Дано описание аналога алгоритма Диффи-Хеллмана на эллиптических кривых, алгоритма цифровой подписи на эллиптических кривых и алгоритма шифрования с открытым ключом получателя на эллиптических кривых.

Поиск по сайту: