Схема Шнорра

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

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

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

• Выбирается простое p и простое q, такое, что $q|p-1$ (p≈$2^{1024}$, $q\ge2^{160}$)
• Выбирается элемент β, такой, что $\beta^q=1 \pmod p$
• Параметры (p,q,β) свободно публикуются
• Выбирается параметр t, $t \ge 40 , 2^t < q$ (t-уровень секретности)

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

• Пусть каждая доказывающая сторона A выбирает секрет a (закрытый ключ), такой, что $1 \le a \le q-1$ и вычисляет $v=\beta^{-a}\pmod p$, где v-открытый ключ

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

• A$\Rightarrow$B : $x=\beta^r \pmod p$
• A$\Leftarrow$B : e (где $1\le e \le 2^t <q$)
• A$\Rightarrow$B : $y=(a*e+r)\pmod q$

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

• A выбирает случайное r ($1 \le r \le q-1$), вычисляет $x=\beta^r \pmod p$ и отсылает x стороне B (доказательство)
• Сторона B отсылает случайное e из диапазона $[1,q-1]$ (вызов)
• A возвращает B $y=(a*e+r)\pmod q$
• B проверяет, действительно ли z=x, где $z=\beta^y*v^e \pmod p$ и, если это так, то идентификация считается успешной.

Пример

• Выбирается простое р=48731 и простое q=443 ($q|p-1$)
• Вычисляется β из условия $\beta^q=1 \pmod p$, в данном случае β=11444
• Тогда системными параметрами будут (48731,443,11444), a t=8
• Сторона А выбирает закрытый ключ a=357 и вычисляет открытый ключ $v=\beta^{-a}\pmod p=7355$
• Сторона А случайным образом выбирает доказательство r=274 и отсылает $x=\beta^r \pmod p=37123$ стороне B
• В отсылает A вызов e=129
• A отсылает B $y=(a*e+r)\pmod q=255$
• B вычисляет $z=\beta^y*v^e \pmod p=37123$ и идентифицирует A, так как z=x

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

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

• A выбирает случайное r ($1 \le r \le q-1$), вычисляет $x=\beta^r \pmod p$
• Пусть имеется однонаправленная хеш-функция H(M). Сторона А объединяет M с x и хеширует результат $e=H(M,x)$
• Далее A вычисляет $y=(ae+r)\pmod q$. Значения e и y являются цифровой подписью и отсылаются B.
• B вычисляет $z=\beta^y*v^e \pmod p$. Затем z и полученное сообщение M' пропускаются через хеш-функцию: $e'=H(M',z)$. Если $e=e'$, то подпись считается верной.

Литература

• 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