Протокол проверки подлинности

(1) Пегги выбирает случайное число r, меньшее q, и вычисляет x= a^rmod p. Эти вычисления являются предварительными и могут быть выполнены задолго до появления Виктора.

(2) Пегги посылает xВиктору.

(3) Виктор посылает Пегги случайное число e, из диапазона от 0 до 2^t-1. (Что такое t, я объясню чуть позже.)

(4) Пегги вычисляет y = (r + se) mod q и посылает y to Виктору.

(5) Виктор проверяет, что x= a^yv^emod p.

Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна 2^t. Шнорр советует использовать pоколо 512 битов, q- около 140 битов и t- 72.

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

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

(1) Алиса выбирает случайное число r, меньшее q, и вычисляет x= a^rmod p. Это стадия предварительных вычислений.

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

e= H(M,x)

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

(4) Боб вычисляет x'= a^yv^emod p. Затем он проверяет, что хэш-значение для объединения Mи x' равно e.

e= H(M,x')

Если это так, то он считает подпись верной.

В своей работе Шнорр приводит следующие новые свойства своего алгоритма:

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

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

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

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

Патенты

Schnorr запатентован в Соединенных Штатах [1398] и многих других странах. В 1993 году PKP приобрело обще мировые права на этот патент(см. раздел 25.5). Срок действия патента США истекает 19 февраля 2008 года.