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