- Схема Шнорра
-
Схема Шнорра — протокол идентификации, который является альтернативой протоколам Фиата-Шамира и Гиллу-Кискатра. Надежность алгоритма основывается на сложности вычисления дискретного логарифма. Данный алгоритм позволяет проводить предварительные вычисления, что удобно при малых вычислительных ресурсах. Нужно отметить, что в протоколе передается только три сообщения. Это было сделано специально для уменьшения взаимодействия в сетях с низкой пропускной способностью.
Содержание
Описание протокола
Выбор параметров системы
- Выбирается простое p и простое q, такое, что
(p≈
, 
) - Выбирается элемент β, такой, что
- Параметры (p,q,β) свободно публикуются
- Выбирается параметр t,
(t-уровень секретности)
Выбор параметров доказывающей стороны
- Пусть каждая доказывающая сторона A выбирает секрет a (закрытый ключ), такой, что
и вычисляет 
, где v-открытый ключ
Передаваемые сообщения
- A
B : 
- A
B : e (где 
) - AB :
Основные действия
- A выбирает случайное r (
), вычисляет и отсылает x стороне B (доказательство) - Сторона B отсылает случайное e из диапазона
![[1,q-1]](eda8dfc2844cf7d1960b2fc447fdfad7.png)
(вызов) - 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
Криптосистемы с открытым ключом RSA • DSA • DSS • NTRUEncrypt • Эль-Гамаля • Меркля — Хеллмана • Шнорра • Эллиптические • ГОСТ Р 34.10-2001 • ДСТУ 4145-2002
Категория:- Криптография
- Выбирается простое p и простое q, такое, что
Wikimedia Foundation. 2010.
