Схема электронной подписи Шнорра

1. Подписывающий выбирает случайное число к и вычисляет

2. Подписывающий вычисляет где подписываемое сообщение.

3. Подписывающий вычисляет и посылает сообщение с подписью получателю.

4. Получатель вычисляет и проверяет, выполняется ли равенство Если да, то подпись принимается, в противном случае — отвергается.

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

Легко проверить, что для подписи, сгенерированной согласно протоколу, проверка п. 4 всегда будет выполнена.

Стойкость схемы Шнорра в значительной степени зависит от свойств функции Если противник умеет отыскивать коллизии специального вида, т. е. по заданной паре находить другое сообщение такое, что то он может осуществлять экзистенцианальную подделку подписей. Для этого достаточно перехватить сообщение и подпись для него, а также найти коллизию указанного вида. Тогда пара будет также подписью и для сообщения

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

В отличие от протоколов аутентификации, для практических схем электронной подписи не известно методов доказательства стойкости. Стойкие схемы подписи не могут быть доказательствами с нулевым разглашением. Это легко понять, если вспомнить, что определение нулевого разглашения требует существования моделирующей машины, которая, не зная секретного ключа, создает для всех величин, наблюдаемых проверяющим, распределение вероятностей, неотличимое от того, которое возникает при выполнении протокола. Но все, что видит проверяющий (он же — получатель) в процессе выполнения протокола, это — сообщения с подписями. Следовательно, моделирующая машина, если она существует, может подделывать подписи, так как создаваемые ею «подписи» должны быть неотличимы от подлинных, в частности, и для алгоритма проверки подписей.

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

доказательства корректности схем аутентификации применима в данной модели для доказательства стойкости схем подписи против пассивного противника. Этот результат справедлив для широкого класса схем подписи, включающего схему Шнорра. Фактически это означает, что схемы подписи являются стойкими (против указанного выше пассивного противника), если хэш-функция ведет себя, как случайная функция. Это утверждение является по-существу единственным результатом теоретической криптографии, касающимся стойкости практических схем электронной подписи, если не считать работы [8], где то же самое доказано в предположении, что хэш-функция ведет себя, как функция дешифрования стойкой, в некотором смысле, криптосистемы.