Стойкость схемы Шнорра основывается на трудной задаче вычисления дискретных логарифмов.
Для генерации пары ключей сначала выбираются два простых числа, p и q так, чтобы q было
сомножителем p-1. Затем выбирается a, не равное 1, такое что aq = 1 ( mod p). Все эти числа
могут быть свободно опубликованы и использоваться группой пользователей.
Для генерации конкретной пары ключей выбирается случайное число, меньшее q. Оно служит закрытым ключом, s.
Затем вычисляется открытый ключ v = a-s (mod p). Для подписи сообщений используется хэш-функция H(M).
Предварительные вычисления
Пользователь A выбирает случайное число r, меньшее q, и вычисляет x = ar (mod p).
Подпись сообщения M
Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:
объединить M и x и хэшировать результат:
e = H(M,x),
вычислить y = (r + se) ( mod q). Подписью являются значения e и y, их нужно выслать получателю B.
Проверка подписи для сообщения M
Получатель B вычисляет x' = ay ve (mod p). Затем он проверяет,
что хэш-значение для объединения M и x' равно e.
e = H(M,x')
Если это так, то он считает подпись верной.
В своей работе Шнорр приводит следующие свойства своего алгоритма:
Большая часть вычислений, нужных для генерации подписи и независящих от подписываемого сообщения,
может быть выполнена на стадии предварительных вычислений. Следовательно, эти вычисления могут быть
выполнены во время простоя и не влияют на скорость вычисления подписи.
При одинаковом уровне безопасности длина подписей для Schnorr короче, чем для RSA. Например,
при 140-битовом q длина подписей равна всего лишь 212 битам, меньше половины длины подписей RSA.
Подписи Schnorr также намного короче подписей ElGamal.
