Схема Шнорра — протокол идентификации, который является альтернативой протоколам Фиата-Шамира и Гиллу-Кискатра. Надежность алгоритма основывается на сложности вычисления дискретного логарифма. Данный алгоритм позволяет проводить предварительные вычисления, что удобно при малых вычислительных ресурсах. Нужно отметить, что в протоколе передается только три сообщения. Это было сделано специально для уменьшения взаимодействия в сетях с низкой пропускной способностью.

Описание протокола

Выбор параметров системы

• Выбирается простое p и простое q, такое, что (p≈, )
• Выбирается элемент β, такой, что
• Параметры (p,q,β) свободно публикуются
• Выбирается параметр t, (t-уровень секретности)

Выбор параметров доказывающей стороны

• Пусть каждая доказывающая сторона A выбирает секрет a (закрытый ключ), такой, что и вычисляет , где v-открытый ключ

Передаваемые сообщения

• AB :
• AB : e (где )
• AB :

Основные действия

• A выбирает случайное r (), вычисляет и отсылает x стороне B (доказательство)
• Сторона B отсылает случайное e из диапазона (вызов)
• A возвращает B
• B проверяет, действительно ли z=x, где и, если это так, то идентификация считается успешной.

Пример

• Выбирается простое р=48731 и простое q=443 ()
• Вычисляется β из условия , в данном случае β=11444
• Тогда системными параметрами будут (48731,443,11444), a t=8
• Сторона А выбирает закрытый ключ a=357 и вычисляет открытый ключ
• Сторона А случайным образом выбирает доказательство r=274 и отсылает стороне B
• В отсылает A вызов e=129
• A отсылает B
• B вычисляет и идентифицирует A, так как z=x

Модификация для цифровой подписи

Пусть сторона A хочет отправить сообщение М стороне B; причем B должен убедиться в том, что сообщение пришло именно от A. Тогда:

• A выбирает случайное r (), вычисляет
• Пусть имеется однонаправленная хеш-функция H(M). Сторона А объединяет M с x и хеширует результат
• Далее A вычисляет . Значения e и y являются цифровой подписью и отсылаются B.
• B вычисляет . Затем z и полученное сообщение M' пропускаются через хеш-функцию: . Если , то подпись считается верной.

Литература

• A. Menezes, P.van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 с. — ISBN 0-8493-8523-7
• Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4