Схема слепой подписи на основе ГОСТ Р 34.10-94

Стандарт ЭЦП ГОСТ Р 34.10−94 рекомендует использование простого числа р, такого что 510 512 бит либо 1022 1024 бит, где — разрядность числа р в двоичном представлении, причем число р-1 содержит большой простой делитель, либо соответственно. Специфицируемые алгоритмы генерации и проверки ЭЦП используют число <�р, такое что и. Вычисление ЭЦП осуществляется следующим образом:

• 1. Генерируется случайное число k, 1< k < q.
• 2. Вычисляется значение R = () mod q, являющееся первой частью подписи.
• 3. По стандарту ГОСТ Р 34.11−94 вычисляется хэш-функция Н от подписываемого сообщения.
• 4. Вычисляется вторая часть подписи: S = kН + zR mod q, где z — секретный ключ. Если S = 0, процедура генерации подписи повторяется. Процедура проверки подлинности ЭЦП:
• 1. Поверяются выполнение условий r< q. Если они не выполняются, то подпись признается недействительной.
• 2. Вычисляется значение:

(*)

3. Сравниваются значения R и. Если R =, то подпись признается действительной.

При построении протокола слепой подписи на основе стандарта ГОСТ Р 34.10−94, приводимого далее, используются два «ослепляющих» множителя, задаваемых в виде у и, которые использовались при построении схемы слепой подписи на основе алгоритма ЭЦП Шнорра. Кроме того, используется два дополнительных «ослепляющих» параметра и, применение которых связано со спецификой проверочного уравнения, регламентируемого стандартом. Протокол слепой подписи на основе указанного стандарта реализуется следующим образом:

1. Подписывающий генерирует случайное число k < q, вычисляет значение:

,

и направляет его пользователю А, который намерен представить некоторое электронное сообщение М, для получения слепой подписи.

2. Пользователь, А генерирует случайные значения, вычисляет Значения:

,, , ,

где — значение хэш-функции от подписываемого документа, вычисленное по стандарту ГОСТ Р 34.11−94 (или по другому специфицированному алгоритму вычисления хэш-функции, значение которой имеет размер не менее 160 бит). Значение R', которое остается неизвестным подписывающему, представляет собой первый элемент формируемой подписи.

• 3. Пользователь, А отправляет подписывающему значения R и H, из которых нельзя вычислить ни, ни, поскольку для любой пары () существует пара значений (,), которые связывают () с полученной парой значений (R, Н).
• 4. Подписывающий вычисляет значение:

,

где z — его секретный ключ, передает вычисленный элемент слепой подписи пользователю А.

5. Пользователь, А вычисляет значение:

,

которое является вторым элементом подписи.

Полученная в соответствии с этим протоколом ЭЦП (R', S') является подлинной, т. е. она вместе с хэш-значением от сообщения М проходит уравнение проверки подписи, регламентируемое стандартом ГОСТ Р 34.10−94. Действительно, корректность описанного протокола доказывается следующим путем.

Доказательство корректности. Элемент слепой подписи S вычисляется на шаге 4 по формуле:

S = kH + zR mod q,

из которой с учетом того, что число имеет порядок q по модулю р, следует справедливость сравнения:

,

из которого имеем:

Учитывая, что:

,

вычислим правую часть проверочного уравнения (*) в случае проверяемой подписи (, S') и значения хэш-функции :

Правая часть проверочного уравнения равна элементу R' проверяемой подписи, следовательно, подпись (, S') к сообщению М является подлинной.

Рассмотренный протокол обеспечивает анонимность пользователя, предоставляющего документ для получения коллективной подписи вслепую, т. е. при предъявлении подписи (R', S') к сообщению М подписавший не может установить пользователя, который предоставлял ему этот документ на подпись, с вероятностью выше значения:

d/N,

где N— количество документов подписанных (данным подписывающим) с помощью протокола слепой подписи; d — число документов, предоставлявшихся данным пользователем. Это требование выполняется, если любая подпись (, S')может быть с равной вероятностью отнесена к каждой из N выполненных процедур протокола слепой подписи (предполагается, что все значения, получаемые подписывающим в процессе протокола, регистрируются им). Описанный протокол удовлетворяет этому требованию.

Действительно, любая четверка значений (, R, S, Н) из множества таких четверок, которые известны подписывающему, может быть ассоциирована с произвольной подлинной подписью (R', S') к произвольному сообщению, представленному значением хэш-функции. Это связано с тем, что четверка (, R, S, Н) и тройка в соответствии с протоколом связаны случайными параметрами, , и .

Для произвольно заданных четверки и тройки, , и значения вычисляются однозначно следующим путем. Вычисляется множитель:

,

значение:

,

(так как значение есть целочисленная степень числа, то указанное значение логарифма существует и является единственным в области L < q). Учитывая, что:

,

получаем следующую систему из трех линейных уравнений с тремя неизвестными, и :

(**)

Вероятность того, что главный определитель этой системы равен нулю, пренебрежимо мала, а именно равна, поэтому практически всегда данная система будет иметь решение. Это означает, что подписывающий может ассоциировать данную тройку с каждой из сохраненных им (в процессе выполнения протокола слепой подписи) четверок (, R, S, Н). При равновероятном случайном выборе значений, и на шаге 2 протокола тройка (R', S', Н'), сформированная по протоколу слепой подписи, с равной вероятностью могла бы быть порождена из любой тройки (, R, S, Н), фигурировавшей в одной из N выполненных процедур слепого подписывания сообщений.