Протокол цифровой подписи

Алгоритм Schnorr также можно использовать и в качестве протокола цифровой подписи сообщения М. Пара ключей используется та же самая, но добавляется однонаправленная хэш-функция ЩМ).

(1) Алиса выбирает случайное число г, меньшее q, и вычисляет х — a mod р. Это стадия предварительных вычислений.

(2) Алиса объединяет М и х и хэширует результат: е = ЩМ,х)

(3) Алиса вычисляет у — (г + se) mod q. Подписью являются значения е и у, она посылает их Бобу.

(4) Боб вычисляет х' = arV mod/;. Затем он проверяет, что хэш-значение для объединения М и х' равно е. е = #(М,х')

Если это так, то он считает подпись верной. В своей работе Шнорр приводит следующие новые свойства своего алгоритма:

Большая часть вычислений, нужных для генерации подписи и независящих от подписываемого сообщения, может быть выполнена на стадии предварительных вычислений. Следовательно, эти вычисления могут быть выполнены во время про­стоя и не влияют на скорость подписания. Вскрытие, направленное против стадии предварительных вычислений, рассматр и-вается в [475], я не думаю, что оно имеет практическую ценность.

При одинаковом уровне безопасности длина подписей для Schnorr короче, чем для RSA. Например, при 140-битовом q длина подписей равна всего лишь 212 битам, меньше половины длины подписей RSA. Подписи Schnorr также намного коро­че подписей EIGamal.

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

Модификация, выполненная Эрни Брикеллом (Ernie Brickell) и Кевином МакКерли (Kevin McCurley), повы­сила безопасность этого алгоритма [265].