Схема Шнорра

Схема Шнорра — это протокол аутентификации и цифровой подписи, основанный на сложности задачи дискретного логарифмирования. Разработана немецким криптографом Клаусом Шнорром в 1989 году и запатентована в США в 1990 году (патент истёк в 2008 году). Схема является одним из наиболее эффективных протоколов с нулевым разглашением (Zero-Knowledge Proof), позволяющим доказывающей стороне (проверяющему) убедить верификатора в знании секретного ключа без раскрытия самого ключа. На основе схемы Шнорра построены многие современные криптографические системы, включая протоколы блокчейна и криптовалюты.

История

Протокол был предложен Клаусом Шнорром в 1989 году как альтернатива схемам цифровой подписи RSA и DSA. Основная цель разработки — повышение вычислительной эффективности и снижение размера подписи. В 1990 году Шнорр получил патент США № 4 995 082 на «Метод идентификации пользователей и подписи сообщений». Патент принадлежал компании «Certicom», что ограничивало использование схемы в открытых стандартах. После истечения срока действия патента в 2008 году схема Шнорра стала активно применяться в криптовалютах (например, в проектах Bitcoin и Monero) и протоколах конфиденциальности.

Математические основы

Схема Шнорра опирается на задачу дискретного логарифмирования в циклической группе простого порядка. Пусть \( G \) — циклическая группа порядка \( q \), где \( q \) — большое простое число, а \( g \) — генератор этой группы. Секретный ключ \( x \) — случайное число из интервала \( [0, q-1] \), а открытый ключ \( y = g^x \mod p \) (где \( p \) — простое число, такое что \( q \) делит \( p-1 \)).

Протокол аутентификации (доказательство знания)

Протокол состоит из трёх шагов:

1. Инициализация (Commitment): Доказывающая сторона (Алиса) выбирает случайное число \( r \) (nonce) из \( [0, q-1] \) и вычисляет \( t = g^r \mod p \). Значение \( t \) отправляется верификатору (Бобу).
2. Вызов (Challenge): Боб выбирает случайное число \( e \) (вызов) из \( [0, 2^k-1] \), где \( k \) — параметр безопасности (обычно 128 или 256 бит), и отправляет его Алисе.
3. Ответ (Response): Алиса вычисляет \( s = r + e \cdot x \mod q \) и отправляет \( s \) Бобу. Боб проверяет равенство \( g^s = t \cdot y^e \mod p \). Если равенство выполняется, доказательство считается успешным.

Схема является протоколом с нулевым разглашением: Боб узнаёт только факт знания \( x \), но не сам \( x \). Для имитации протокола без знания \( x \) злоумышленнику пришлось бы решить задачу дискретного логарифмирования.

Цифровая подпись Шнорра

Схема Шнорра может быть преобразована в алгоритм цифровой подписи (Schnorr Signature) с помощью хеш-функции. Подпись сообщения \( m \) выполняется следующим образом:

1. Выбирается случайное число \( r \) из \( [0, q-1] \).
2. Вычисляется \( t = g^r \mod p \).
3. Вычисляется хеш \( e = H(t \parallel m) \), где \( H \) — криптографическая хеш-функция (например, SHA-256).
4. Вычисляется \( s = r + e \cdot x \mod q \).
5. Подпись — пара \( (e, s) \) или \( (t, s) \).

Верификация подписи:

• Вычисляется \( t' = g^s \cdot y^{-e} \mod p \).
• Проверяется \( e = H(t' \parallel m) \).

Размер подписи Шнорра обычно меньше, чем у схемы ECDSA (для эллиптических кривых — около 64 байт против 72 байт для ECDSA). Это преимущество используется в блокчейн-системах для уменьшения объёма транзакций.

Преимущества и недостатки

Преимущества

• Эффективность: Схема Шнорра требует меньше вычислительных операций, чем RSA или DSA, особенно при использовании эллиптических кривых.
• Компактность: Размер подписи (например, для кривой secp256k1 — 64 байта) меньше, чем у ECDSA (72 байта).
• Возможность агрегации: Подписи Шнорра могут быть объединены в одну (агрегированная подпись), что позволяет проверять множество подписей за одну операцию. Это свойство используется в протоколах мультиподписей.
• Доказуемая безопасность: Схема безопасна в модели случайного оракула (Random Oracle Model) при условии сложности задачи дискретного логарифмирования.

Недостатки

• Патентные ограничения: До 2008 года использование схемы было ограничено патентом, что замедлило её внедрение в открытые стандарты.
• Чувствительность к качеству случайных чисел: Если nonce \( r \) повторяется или предсказуем, секретный ключ может быть восстановлен (аналогично уязвимости в ECDSA).
• Необходимость идеального хеширования: Для доказательства безопасности требуется криптографически стойкая хеш-функция.

Применение

Криптовалюты и блокчейн

Схема Шнорра активно используется в криптовалютах для реализации мультиподписей и повышения конфиденциальности:

• Bitcoin: Предложение BIP-340 (Schnorr Signatures) было принято в 2021 году для сети Bitcoin. Оно позволяет объединять несколько подписей в одну, уменьшая размер транзакций и улучшая приватность (например, в протоколе Taproot).
• Monero: Использует схему Шнорра для кольцевых подписей (Ring Signatures), обеспечивающих анонимность транзакций.
• Zcash: Применяет схему Шнорра в протоколах zk-SNARKs для доказательств с нулевым разглашением.

Аутентификация

Протокол Шнорра применяется в системах аутентификации, где требуется доказательство знания пароля или секретного ключа без его передачи (например, в протоколах SSH и TLS).

Криптографические протоколы

Схема используется в протоколах:

• Слепая подпись (Blind Signature): Позволяет подписывать сообщение, не зная его содержимого (применяется в электронных деньгах).
• Доказательства с нулевым разглашением: Является базой для многих современных протоколов (например, Bulletproofs).

Критика

Основная критика схемы Шнорра связана с её патентной защитой, которая препятствовала широкому внедрению в течение почти 20 лет. Кроме того, некоторые исследователи отмечают, что схема уязвима к атакам по сторонним каналам (например, по времени выполнения операций), если не реализована с защитой от таких атак. Однако современные реализации (например, в Bitcoin) используют константное время выполнения для предотвращения подобных уязвимостей.

Интересные факты

• В 1993 году Клаус Шнорр подал в суд на компанию «Certicom» за нарушение патента, но дело было урегулировано во внесудебном порядке.
• Схема Шнорра является одним из немногих криптографических протоколов, которые одновременно обладают свойством нулевого разглашения и могут быть преобразованы в цифровую подпись без потери безопасности.
• В 2021 году внедрение схемы Шнорра в Bitcoin (обновление Taproot) считается одним из самых значительных изменений протокола со времён SegWit.

Источники

• Schnorr, C. P. (1989). Efficient Identification and Signatures for Smart Cards. Advances in Cryptology — CRYPTO’89.
• Schnorr, C. P. (1991). Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3), 161–174.
• BIP-340: Schnorr Signatures for secp256k1. Bitcoin Improvement Proposal.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press.
• Goldwasser, S., Bellare, M. (2008). Lecture Notes on Cryptography. MIT Press.