Схемы Шнорра станут самым большим изменением Биткоина со времен SegWit

Цифровые подписи – это основа онлайн-суверенитета. Появление в 1976 году криптографии с открытым ключом открыло путь к созданию глобального средства коммуникации – интернета – и совершенно новой формы денег, Биткойна. Хотя фундаментальные свойства криптографии с открытым ключом с тех пор не сильно изменились, сегодня криптографам доступны уже десятки различных схем цифровой подписи с открытыми исходниками.

Когда Сатоши Накамото начинал работать над Биткойном, один из ключевых моментов, которые необходимо было учесть, заключался в том, какую из схем подписи следует выбрать для открытой и общедоступной финансовой системы. Требования были ясны: нужно было создать алгоритм, который был бы широко используем, понятен, достаточно безопасен, лёгок и, самое главное, с открытым исходным кодом. Из всех доступных на тот момент опций он выбрал ту, что отвечает этим критериям лучше всего: Elliptic Curve Digital Signature Algorithm (алгоритм цифровой подписи, основанный на эллиптических кривых), или ECDSA.

В то время нативная поддержка ECDSA была предусмотрена в OpenSSL, открытом наборе инструментов шифрования, разработанных шифропанками со стажем с целью повышения конфиденциальности онлайн-коммуникаций. По сравнению с другими популярными схемами, ECDSA обладает такими преимуществами, как меньшая требовательность к вычислительным ресурсам и меньшая длина ключей – это полезные свойства для цифровых денег. В то же время он обеспечивает пропорциональный уровень безопасности для таких схем, как RSA: к примеру, 256-битный ECDSA-ключ обладает равноценным в сравнении с 3072-битным RSA-ключом уровнем безопасности при значительно меньшем размере ключа.

Благодаря тяжёлой работе, проделанной Питером Вуйле с коллегами над улучшенной эллиптической кривой, называемой secp256k1, ECDSA Биткойна стал ещё быстрее и эффективнее. Однако ECDSA по-прежнему присущи и некоторые недостатки, которые могут служить достаточным основанием и для полной его замены. После нескольких лет исследований и экспериментов была установлена новая схема подписи, повышающая конфиденциальность и эффективность транзакций Биткойна: схема цифровой подписи Шнорра.

В этой статье я расскажу в общих чертах о многочисленных имплементациях подписей Шнорра и о преимуществах этих подписей. Затем мы поговорим о MuSig, новом стандарте мультиподписи, который может служить основой для внедрения новых биткойн-технологий, таких как Taproot. Наконец, я расскажу вам, как полная реализация подписей Шнорра может нарушить используемую в блокчейн-аналитике эвристику и в то же время способствовать развитию сильного рынка комиссий на основном слое Биткойна.

История появления подписей Шнорра

Притом, что схема цифровых подписей Шнорра обладает множеством преимуществ по сравнению с ECDSA, она определённо не нова. Она была изобретена ещё в 1980 гг. Клаусом-Петером Шнорром, немецким криптографом и академиком, на тот момент профессором и исследователем Франкфуртского университета. В основание предложенной им схемы подписи легли исследования и работы Дэвида Чаума, Тахера Эль-Гамаля, Амоса Фьята и Ади Шамира. Тем не менее, прежде чем опубликовать новую схему, Клаус Шнорр заполнил множество патентов, которые в течение многих лет препятствовали её прямому использованию.

Интересно, что предшественник ECDSA, алгоритм DSA, представлял собой гибрид схем Эль-Гамаля и Шнорра, созданный исключительно для обхода патентов Клауса Шнорра. На самом деле, всего через два месяца после выдачи американского патента Клаусу Шнорру прародитель DSA, Национальный институт стандартов и технологий США (NIST), также оформил патент для своего решения. После этого Клаус Шнорр стал ещё активнее защищать свои патенты и прямо ответил своим критикам в рассылке Coderpunks (ответвлении оригинальной email-рассылки Cypherpunks). Его ответы можно прочитать здесь и здесь (англ.). А здесь можно найти внутреннюю записку NIST с описанием патентных проблем.

В 2008 году, спустя почти два десятилетия после представления схемы подписи Шнорра, срок действия патента Клауса Шнорра истёк. По совпадению, 2008 стал также годом, когда Сатоши Накамото, представил миру Биткойн. Несмотря на то что подписи Шнорра на тот момент уже можно было использовать, они ещё не были стандартизированными или широко используемыми. Вероятно, поэтому Сатоши и остановил свой выбор на ECDSA. И, хотя криптографы и математики часто характеризуют этот алгори, ECDSA до сих пор довольно широко используется, а на тот момент он был более безопасной опцией для Биткойна.

Магия BLS-подписей

Прежде всего, нужны две новые конструкции – хеширование в кривую и спаривание кривых.

Хеширование в кривую

Обычно в случае подписей ECDSA и Шнорра мы хешируем сообщение и используем этот хеш в алгоритме подписи как число. Для BLS-подписей нужен слегка модифицированный алгоритм, хеширующий непосредственно в эллиптическую кривую. Самый простой способ – хешировать сообщение как обычно и рассматривать результат как x-координату точки. Эллиптические кривые (вроде используемой в Биткойне) обычно имеют порядка 2 точки в 256 степени, и алгоритм хеширования SHA-256 также даёт 256-битный результат. Но для каждой валидной x-координаты есть две точки с положительной и отрицательной y-координатой (потому что если (x,y) находится на кривой y²=x³+ax+b, то (x,-y) также находится на кривой). Это значит, что наш хеш может с вероятностью примерно 50% найти две точки для некоторого x и с вероятностью 50% не найти ни одной.

BLS-подписи: лучшая альтернатива подписям Шнорра

Чтобы найти точку для любого сообщения, можно попытаться хешировать несколько раз, присоединяя к сообщению число и увеличивая его в случае неудачи. Если hash(m||0) не находит точку, мы пробуем hash(m||1), hash(m||2) и т. д., пока не найдём подходящий результат. Затем достаточно выбрать одну из двух соответствующих точек, например с меньшим y.

Спаривание кривых

Нам также нужна особая функция, которая берёт две точки P и Q на кривой (или на двух разных кривых) и сводит их к числу:

От этой функции также требуется одно важное свойство. Если у нас есть некоторое секретное число x и две точки P и Q, то мы должны получить одинаковый результат независимо от того, какую точку умножить на это число:

По сути, мы должны иметь возможность менять местами множители точек между двумя аргументами, не меняя результата. В более общем смысле, все эти перестановки должны давать один и тот же результат:

Я не стану описывать, как именно действует эта функция. Её математическая подоплёка достаточно сложна, и если вы хотите узнать все тонкости, советую прочитать эту статью и содержащиеся в ней ссылки. Если желаете ещё больше углубиться – эта диссертация полностью посвящена спариванию. Мы же пока просто примем как факт, что такие функции существуют и не раскрывают никакой информации о нашем секретном числе x.

Важно заметить, что мы не можем здесь использовать любую эллиптическую кривую (в частности, стандартная кривая Биткойна secp256k1 не подойдёт). Чтобы сделать функцию эффективной и безопасной, нужно использовать особые кривые из «дружественного к спариванию» семейства.

Схема BLS-подписи

Теперь у нас есть всё необходимое для построения BLS-подписи. Наш приватный ключ – это некое секретное число pk, публичный ключ – P = pk×G , а подписываемое сообщение – m.

Чтобы вычислить подпись, мы хешируем наше сообщение в кривую H(m) и умножаем результирующую точку на наш приватный ключ: S = pk×H(m). Вот и всё! Больше ничего – ни случайных чисел, ни дополнительных операций, только хеш умножить на приватный ключ! Наша подпись – это просто одна точка на кривой, занимающая всего 33 байта в сжатом формате сериализации!

BLS-подписи: лучшая альтернатива подписям Шнорра

Чтобы верифицировать эту подпись, можно взять наш публичный ключ P и проверить условие:

Оно истинно благодаря замечательному свойству описанной выше функции спаривания:

BLS-подписи: лучшая альтернатива подписям Шнорра

Данная схема подписи красива и проста, но она также имеет ряд замечательных свойств, особенно для Биткойна.

Агрегирование подписей

Давайте скомбинируем все подписи блока! Представим, что у нас есть блок с 1000 транзакций и каждая транзакция содержит подпись Si, публичный ключ Pi и подписываемое сообщение mi. Зачем хранить все подписи, если их можно объединить? В конце концов, нам важно лишь, чтобы все подписи блока были действительными. Агрегированная подпись будет представлять собой всего лишь сумму всех подписей блока:

S = S1+S2+…+S1000

Чтобы верифицировать блок, нужно проверить, выполняется ли следующее равенство:

Если присмотреться, то можно увидеть, что оно действительно выполняется:

Нам по-прежнему нужно знать все публичные ключи и вычислить 1001 функцию спаривания, но, по крайней мере, все подписи блока занимают всего 33 байта. Агрегирование подписей может выполняться майнером, что сэкономит много места в блоке.

Агрегирование ключей и мультиподпись n-из-n

Если мы используем адреса мультиподписей, то мы подписываем одну и ту же транзакцию разными ключами. В таком случае можно выполнить агрегирование ключей, как в подписях Шнорра, скомбинировав все подписи и ключи в единую пару ключа и подписи. Рассмотрим простую схему мультиподписи 3-из-3 (аналогично можно сделать для любого количества подписантов).

Простой способ их скомбинировать – сложить все подписи и ключи. В результате получим подпись S=S1+S2+S3 и ключ P=P1+P2+P3. Легко увидеть, что действительно всё то же уравнение для верификации:

Как и в случае подписей Шнорра, нужно обезопаситься от атаки фальшивых ключей. Для этого можно либо попросить каждого подписанта доказать, что у него есть приватный ключ, соответствующий публичному (посредством подписи публичных ключей), либо добавить в схему нелинейность, которая сделает атаку фальшивых ключей невозможной. Вместо того чтобы сложить все ключи и подписи, мы умножим их на определённое число и затем сложим:

Здесь коэффициенты подписей и ключей вычисляются детерминистически из публичного ключа подписанта и всех остальных публичных ключей:

Например, это может быть просто конкатенация публичного ключа подписанта и всего множества публичных ключей, используемых для подписи: ai = hash(Pi||P1||P2||P3).

По-прежнему действительно то же уравнение для верификации. В доказательстве будут дополнительные коэффициенты ai, но логика остаётся той же.

В этой схеме замечательно то, что не требуется несколько коммуникационных циклов между устройствами. Достаточно знать, кто другие подписанты. Это намного проще, чем схема мультиподписи из 3 циклов в случае подписей Шнорра. Кроме того, это полностью детерминистический алгоритм подписей, не полагающийся на случайность.

Схема мультиподписи подгруппы (мультиподпись m-из-n)

Часто мы не хотим использовать схему мультиподписи n-из-n, а предпочитаем m-из-n, например 2-из-3. Мы не хотим потерять все деньги только потому, что потеряли один из ключей. Было бы замечательно использовать в таком сценарии агрегирование ключей. В случае подписей Шнорра это возможно с помощью дерева Меркла для публичных ключей. Это не самый эффективный, но действенный способ. К сожалению, при больших значениях m и n размер дерева Меркла растёт экспоненциально.

В случае схемы BLS-подписей существует другой метод. Однако он не такой простой. Потребуется обычная хеш-функция, выдающая число, – hash(x), и хеширование в кривую  – H(x). Также понадобится фаза «настройки», когда мы решаем использовать мультиподпись, но после этого потребности в коммуникации больше нет – нужны лишь подписи для подписания любого количества транзакций.

Опять же, я буду использовать простой пример, где мы хотим построить схему мультиподписи 2-из-3 с помощью ключей, хранящихся на 3 разных устройствах, но то же самое применимо для любых значений m и n.

Фаза настройки

Каждое из наших устройств имеет номер подписанта i = 1,2,3, обозначающий его место во множестве, приватный ключ pki и соответствующий публичный ключ Pi = pki×G. Мы рассчитываем агрегированный публичный ключ точно так же, как раньше:

Теперь каждое устройство должно с помощью подписи подтвердить, что номер i входит в наш агрегированный публичный ключ (для каждого i), подписи должны быть агрегированы и результат сохранён на соответствующем устройстве:

Эту подпись мы будем называть «ключом участия», и она будет использоваться позже. Каждый ключ участия – это действенная подпись n-из-n сообщения H(P,i). Это значит, что:

Запомните это уравнение, позже оно нам понадобится. Оно будет использоваться, чтобы доказать, что мы действительные участники схемы мультиподписи.

Подпись

Допустим теперь, что мы хотим подписать транзакцию только ключами pk1 и pk3. Генерируем две подписи S1 и S3:

и слагаем их, чтобы получить одну подпись и ключ:

Я пишу здесь P’ и S’, чтобы подчеркнуть, что эти ключ и подпись подписаны только подмножеством подписантов и это не тот же агрегированный ключ P для всех подписантов. Чтобы верифицировать эту подпись 2-из-3, нужно проверить условие:

Мы помним, что ключи участия MK1 и MK3 – это действительные подписи для сообщений H(P, 1) и H(P, 3), подписанных агрегированным ключом P, поэтому:

Вот и всё. Чуть сложнее, чем n-из-n, но всё же понятно.

Возможная реализация

Для того чтобы реализовать эту схему мультиподписи, нам необходимо отправить деньги на адрес, соответствующий агрегированному публичному ключу P, и сказать, что нам нужны как минимум две подписи. На языке сценариев Биткойна сценарий блокировки может выглядеть следующим образом:

Здесь OP_2 говорит, что требуется два ключа для подписи сообщения. Мы нигде не говорим, что всего есть 3 подписанта, так что никто не может сказать, идёт ли речь о мультиподписи 2-из-3 или 2-из-100. Позже мы также не раскрываем эту информацию.

Чтобы расходовать этот выход, необходимо предоставить ключ P’, подпись S’ и индексы участвующих подписантов – в нашем случае числа 1 и 3. Сценарий разблокировки может выглядеть так:

Комбинация этих сценариев даёт нам всю необходимую информацию. OP_1 и OP_3 говорят нам, что нужно вычислить хеши H(P, 1) и H(P, 3), после чего у нас есть всё необходимое, чтобы верифицировать транзакцию.

Следовательно, для любых m и n достаточно:

  • одного агрегированного публичного ключа P в сценарии блокировки,
  • одного агрегированного публичного ключа участвующих подписантов P’,
  • одной агрегированной подписи S’,
  • m чисел с индексами подписантов.

Очень компактно и красиво!

Лишь одно мне здесь не нравится… Обычно мы используем адреса лишь единожды – мы генерируем новые приватные ключи и адреса с помощью таких методов, как BIP32. Но для каждого нового множества приватных ключей также нужно множество новых ключей участия. Один способ реализовать это без повторения каждый раз фазы настройки – это сгенерировать большое количество ключей, например 1000, и получить соответствующие ключи участия. В конце концов, их длина всего 32 байта. Тогда нам придётся повторить фазу настройки только после использования всей 1000 адресов.

Подписи Шнорра в Биткойне

Пропустим на быстрой перемотке ещё одно десятилетие и перенесёмся в сегодняшний день. Схема подписей Шнорра теперь выглядит намного менее эзотерично и её стандартизированные реализации – такие как ed25519 – становятся популярной опцией для некоторых альткойнов. Неформальные разговоры о потенциальной реализации подписей Шнорра в сети Биткойна восходят к этой ветке форума BitcoinTalk, датируемой 2014 годом, но предложение было формализовано только после нескольких лет исследований и экспериментов, когда Питер Вуйле написал Schnorr BIP (Bitcoin Improvement Proposal, «предложение по улучшению Биткойна»). В этом черновике предложения описывается спецификации и технические аспекты потенциальной реализации подписей Шнорра, которые будут обладать следующими преимуществами по сравнению с ECDSA:

  • Доказательство безопасности:
    Безопасность подписей Шнорра легко доказывается при использовании в достаточной мере случайной хеш-функции (модель случайных оракулов) и достаточной сложности задачи дискретного логарифмирования в группе точек эллиптической кривой (elliptic curve discrete logarithm problem, ECDLP). Для ECDSA такого доказательства не существует.
  • Негибкость:
    ECDSA-подписи по своей природе являются гибкими, что может позволить третьей стороне, не имеющей доступа к секретному ключу, изменить существующую действительную подпись и расходовать средства дважды. Официально эта проблема обсуждалась в BIP62. Для сравнения, подписи Шнорра являются доказуемо негибкими.
  • Линейность:
    Подписи Шнорра обладают замечательным свойством: несколько сторон могут совместно создать подпись, действительную для суммы их открытых ключей. Это может служить конструкционным блоком для различных конструкций более высокого уровня, повышающих эффективность и приватность – таких как мультиподписи и прочие смарт-контракты.

Доказательства безопасности подписей Шнорра, а также гарантия их негибкости, дают им явные преимущества над ECDSA. Уже эти два преимущества могут служить достаточным основанием для софт-форка. Но особенно впечатляющим свойством подписей Шнорра является их линейность. В частности, это позволяет нескольким подписантам транзакции с мультиподписью объединять свои открытые ключи в один агрегированный ключ, представляющий всю группу – это свойство называется агрегированием ключей.

Хотя возможность объединения ключей в один может прозвучать несколько тривиально, преимуществ этого не следует недооценивать. Поскольку в ECDSA нет нативной поддержки мультиподписей, в Биткойне их пришлось реализовывать через стандартизированный смарт-контракт (да-да, в Биткойне тоже есть смарт-контракты), называемый Pay-to-ScriptHash (P2SH). Он позволяет пользователям добавлять условия расходования, называемые обременениями, чтобы указать, как могут быть потрачены средства – например, «разблокировать баланс только если сообщение подпишут Боб и Алиса».

Первая проблема с P2SH заключается в том, что он требует знания открытых ключей всех участников мультиподписи, что не является эффективной системой. Агрегирование этих ключей позволило бы оптимизировать проверку, поскольку сети понадобилось бы верифицировать лишь один ключ, а не несколько. Это также подразумевает меньший след в блокчейне, меньшую стоимость транзакции и улучшение пропускной способности сети.

Вторая проблема с P2SH заключается в том, что он предлагает очень небольшие гарантии конфиденциальности. Как указывалось в BIP13, для P2SH-транзакций необходимо, чтобы адреса начинались с цифры 3. Это позволяет блокчейн-аналитикам не только распознавать все P2SH-транзакции в сети, но и точно определять адреса, участвующие в мультиподписи:


Блокчейн-аналитик: «Определённо, мультиподпись». – Не хорошо.

В примере выше сеть будет знать (1) о существовании транзакции с мультиподписью, (2) о том, сколько адресов участвуют в мультиподписи и (3) о том, кто именно подписал транзакцию. Не здорово для операционной безопасности, особенно для таких вариантов использования, как 2FA. Это плохо с точки зрения конфиденциальности.

Агрегирование ключей, с другой стороны, сохраняет анонимность участников мультиподписи и не компрометирует операционную безопасность через раскрытие ключей, необходимых для разблокирования баланса. Самое главное, агрегирование ключей позволяет сделать транзакции с мультиподписью неотличимыми от обычных транзакций:


Блокчейн-аналитик: «Это может быть мультиподписью… Невозможно сказать наверняка…» – Теперь хорошо.

Первая итерация подписей Шнорра в Биткойне упразднит семейство опкодов OP_CHECKSIG и OP_CHECKMULTISIG, используемых в настоящее время с ECDSA, в пользу нового класса опкодов, называемого OP_CHECKDLS. Если не слишком вдаваться в подробности, DLS означает Discrete Log Signature (подпись с дискретным логарифмированием), и это позволяет верифицировать подписи эффективнее и с меньшим количеством опкодов.

Ещё в начале 2020 года Грегори Максвелл, Эндрю Поэлстра, Янник Сеурин и Питер Вуйле опубликовали уайтпэйпер новой, основанной на подписи Шнорра схемы мультиподписи, под названием MuSig. После этой публикации они много работали над переводом предлагаемой схемы мультиподписи в пригодный для использования код.

Одним из самых интересных моментов в MuSig в контексте агрегирования ключей является возможность создания приватных смарт-контрактов вне блокчейна. По сути, MuSig позволяет участникам мультиподписи применять обременения к агрегированным ключам офчейн, не разглашая этих условий и совершенно отдельно от правил консенсуса Биткойна.

В декабре 2020 года Энтони Таунс стал первым разработчиком Bitcoin Core, подготовившим полуформализованное предложение по активации подписей Шнорра, которое было представлено в рассылке для разработчиков Биткойна. Я ожидаю, что в ближайшие месяцы количество разговоров о потенциальном софт-форке возрастёт.

Подводя итог сказанному, первая итерация MuSig в Биткойне будет обладать поддержкой агрегирования ключей, что может немедленно (1) улучшить конфиденциальность мультиподписей, (2) повысить эффективность проверки транзакций, (3) повысить безопасность за счёт устранения проблем, присущих ECDSA, и (4) обеспечить возможность для интеграции таких смарт-контрактов, как Taproot, о котором мы поговорим в следующем разделе.

И это только начало.

Преимущества подписей Schnorr

  • Улучшенная масштабируемость.

Благодаря экономии данных через агрегирование нескольких подписей размер транзакции становится меньше. Это оставляет больше места в блоке для добавления дополнительных транзакций, тем самым увеличивая емкость сети. Кроме того, это экономия для тех, кто проводит транзакцию, потому что комиссия высчитывается за байт.

  • Повышенная конфиденциальность.

В отношении транзакций с мультиподписью агрегированная подпись повышает безопасность лиц, участвующих в транзакции, поскольку их собственная подпись не требуется. Кроме того, в сочетании с CoinJoin, методом сжатия транзакций Bitcoin, также может быть улучшена конфиденциальность отдельного участника.

  • Спам-атаки.

Мемпул биткоина спамят, и часто это акции, связанные со взглядами на развитие сети. Например, чтобы указать на недостаточную масштабируемость.

Один из методов заспамить сеть — включить в транзакции десятки подписей, постоянно отправляя транзакции из многих источников. Пример можно увидеть своими глазами в обозревателе блоков по ссылке: https://www.blockchain.com/ru/btc/block/00000000000000000182aabc399d2daec86b50d510701a5fd098793a4eadead4

Подписи Schnorr борятся с подобным спамом. Если есть только одна подпись на транзакцию, больше транзакций будет попадать в блоки, и спамеру нужно будет отправлять гораздо больше транзакций и, следовательно, тратить больше денег.

Генерация ключейправить

Генерация ключей для схемы подписи Шнорра происходит так же, как и генерация ключей для DSA, кроме того, что не существует никаких ограничений по размерам Заметим также, что модуль p может быть вычислен автономно

  1. Выбирается простое число p , которое по длине обычно равняется 1024 битам
  2. Выбирается другое простое число q таким, чтобы оно было множителем числа p − 1 Или другими словами должно выполняться p − 1 ≡ 0 mod q Размер для числа q принято выбирать равным 160 битам
  3. Выбирается число g , отличное от 1 , такое, что g q ≡ 1 mod p equiv 1
  4. Пегги выбирает случайное целое число w меньшее q
  5. Пегги вычисляет y = g − w mod p
  6. Общедоступный ключ Пегги — p , q , g , y , секретный ключ Пегги — w

Протокол проверки подлинности

Алгоритм работы протокола

  1. Предварительная обработка
    . Алиса выбирает случайное число r, меньшее q, и вычисляет x= g^r pmod p. Эти вычисления являются предварительными и могут быть выполнены задолго до появления Боба.
  2. Инициирование.
    Алиса посылает x Бобу.
  3. Боб выбирает случайное число e из диапазона от 0 до 2^t-1 и отправляет его Алисе.
  4. Алиса вычисляет s=r+we pmod q и посылает s Бобу.
  5. Подтверждение.
    Боб проверяет что x=g^sy^e pmod p

Безопасность алгоритма зависит от параметра t

. Сложность вскрытия алгоритма примерно равна 2^t. Шнорр советует использовать
t
около
72
битов, для p ge 2^{512} и q ge 2^{140}. Для решения задачи дискретного логарифма, в этом случае, требуется по крайней мере 2^{72} шагов известных алгоритмов.



Пример

Генерация ключей:

  • Выбирается простое p=48731 и простое q=443 ( q|p-1)
  • Вычисляется g из условия g^q=1 pmod p, в данном случае g=11444
  • Алиса выбирает секретный ключ w=357 и вычисляет открытыйy=g^{w}pmod p=7355 ключ
  • Открытый ключ (48731,443,11444, 7355), закрытый — 357

Проверка подлинности:

  • Алиса выбирает случайное число r=274 и отсылает x=g^r pmod p=37123 Бобу.
  • Боб отсылает Алисе число e = 129
  • Алиса считает s=(r+w*e)pmod q=255 и отправляет s Бобу.
  • Боб вычисляет z=g^s*y^e pmod p=37123 и идентифицирует Алису, так как z=x.

Атаки на Схему

Пассивный противник

Если в схеме Шнорра предположить, что Алиса является противником, то на шаге 1 она может выбрать x случайным, но эффективным способом. Пусть x — это переданное Алисой число. Предположим, что можно найти два случайных числа e_1 и e_2 такие, что e_1 neq e_2 и для каждого из них Алиса может найти соответствующие s_1 и s_2, для которых подтверждение даст положительный результат. Получаем:

x=g^{s_1}y^{e_1} bmod p x=g^{s_2}y^{e_2} bmod p.

Отсюда g^{s_1}y^{e_1} = g^{s_2}y^{e_2} pmod p или же y^{e_1-e_2} = g^{s_2-s_1} pmod p. Так как e_1 neq e_2, то существует (e_2-e_1)^{-1} bmod q и, следовательно, (s_1-s_2)(e_2-e_1)^{-1} = w bmod q, то есть дискретный логарифм y. Таким образом, либо e_1, e_2, e_1 neq e_2 такие, что Алиса может ответить надлежащим образом на оба из них (при одном и том же x) на шаге 3 протокола, встречаются редко, что означает, что атака Алисы успешна лишь с пренебрежимо малой вероятностью. Либо такие значения попадаются часто, и тогда тот алгоритм, который применяет Алиса, можно использовать для вычисления дискретных логарифмов. Иными словами, доказано, что в предположении трудности задачи дискретного логарифмирования схема аутентификации Шнорра является стойкой против пассивного противника, то есть корректной.

Активный противник

Активный противник может провести некоторое количество сеансов выполнения протокола в качестве проверяющего с честным доказывающим (или подслушать такие выполнения) и после этого попытаться атаковать схему аутентификации. Для стойкости против активного противника достаточно, чтобы протокол аутентификации был доказательством с нулевым разглашением. Однако свойство нулевого разглашения для схемы Шнорра до сих пор никому доказать не удалось.


Понравилась статья? Поделиться с друзьями:
Добавить комментарий