Содержание
- Историческая справка
- Суть протокола Шнорра
- Схема подписи Шнорра
- Почему подписи Шнорра считаются лучше, чем ECDSA?
Комментарий от автора
Эта статья предназначена для людей, уже знакомых с основами информационной безопасности.
Если слова «Протокол подтверждения знаний» и «Криптосистема с открытым ключом» не означают для вас волшебства, добро пожаловать!
Историческая справка
Схема Шнорра была изобретена в 1980-х годах.Клаус-Петер Шнорр.
Клаус Шнорр — немецкий криптограф, академик, а в то время профессор и исследователь Франкфуртского университета.
Перед публикацией самой схемы Клаус Шнорр запутался с патентами, что затрудняло ее прямое использование до 2008 года.
В 2008 году, в том же году, когда Сатоши Накамото представил миру Биткойн, срок действия патента Клауса Шнорра истек.
Хотя подписи Шнорра уже можно было использовать, Сатоши Накамото выбрал ECDSA для Биткойна.
Это связано с тем, что схема Шнорра еще не была стандартизирована и широко не использовалась.
Хотя криптографы часто считают ECDSA неудачей, он все еще используется сегодня.
Кстати, DSA, предшественник ECDSA, представлял собой гибрид схем Эль-Гамаля и Шнорра, созданный исключительно для обхода патентов Клауса Шнорра Национальным институтом стандартов и технологий США (NIST).
После его появления в рассылке Coderpunks началась, что называется, интеллектуальная борьба, и Клаус Шнорр стал еще активнее защищать свои патенты.
Суть протокола Шнорра
Вообще говоря, схема Шнорра — это один из вариантов протоколов доказательства с нулевым обнаружением.Мы доказываем, что для некоторого открытого ключа h, который является элементом группы с фиксированным порождающим элементом g, известен секрет x такой, что g степени x является нашим открытым ключом h. Также стоит отметить, что протокол является интерактивным, т.е.
подразумевает многораундовый обмен сообщениями между участниками.
Сначала Алиса выбирает случайное число k из подгруппы порядка q; он должен быть уникальным для каждого сеанса.
Затем Алиса считает I и отправляет его Бобу.
Боб также выбирает случайное число из подмножества и отправляет его обратно Алисе.
Алиса вычисляет s и отправляет его Бобу.
Боб проверяет и подтверждает. 
Схема подписи
Эта схема по сути является развитием интерактивного протокола, за исключением того, что r не является случайной величиной, здесь берется вывод случайного оракула.
Стоит отметить, что входом в хеш-функцию является элемент группы и сообщение m (хотя это может быть и элемент группы, но зачастую это просто битовая строка), в этом случае вместо I следует отправить вывод определенной функции, которая преобразует элемент группы в строку битовой строки.
Рассчитываем значение r таким образом (оригинальная схема подписи): 
называется слабая трансформация Фиат-Шамир , это Это не безопасно .
На практике также стоит добавить открытый ключ pk в r. Слабое преобразование Фиата-Шамира использовалось до 2010-х годов, хотя оно используется и сегодня и в нем были обнаружены различные уязвимости, в частности, например, в системе электронного голосования Helios. Здесь открытый ключ (pk) является элементом группы, т.е.
его размер невелик и порядка n (на практике всего 33 байта).
Отсюда следует, что размер подписи также равен 2 числам из группы, т.е.
2n битам (на практике 64 байта).
Те.
По сравнению с предыдущими алгоритмами этот на порядки эффективнее.
Схема подписи Шнорра позволяет подписывать множество документов (учитывая, конечно, уникальность k).
В истории были случаи, когда k совпадало в разных документах и это позволяло открыть ключ.
Таким образом, консоли уже однажды взламывали и перепрошивали, и в истории Биткойна подобные случаи были.
Почему подписи Шнорра считаются лучше, чем ECDSA?
Чтобы ответить на этот вопрос, давайте рассмотрим три основных критерия, по которым мы сравниваем подписи ECDSA и Шнорра.
- Безопасность
- Размер подписи
- Конфиденциальность
Безопасность ECDSA
Вообще говоря, не существует доказательства безопасности ECDSA для задачи дискретного логарифмирования группы точек эллиптической кривой при использовании генератора случайных групп, но на самом деле это не основная причина, по которой многие хотят изменить ECDSA на подписи Шнорра.С 2009 года ECDSA на кривой x. 3 +7 работает достаточно надежно, и если обнаруживалась какая-то критическая уязвимость, о ней знали давно.
То есть, по сути, на данный момент ECDSA и описанной кривой вполне достаточно.
Оказывается, здесь дело немного в другом.
Давайте посмотрим на размер подписи.
Где именно находится это значение? У нас есть транзакция: 
Входные данные транзакции состоят из хеш-значения предыдущей транзакции, выходного индекса предыдущей транзакции, затем поля последовательности и самого поля.
scriptSig — доказательство владения монетами, то есть собственная стоимость подписи, и эта стоимость занимает довольно большую часть входов транзакции.
Выходные данные содержат значение и скриптPubKey - условия траты монет, то есть по сути условия, которые должны быть выполнены для того, чтобы монеты были потрачены.
Если транзакция подписывается одним участником, то размер единого значения подписи плюс-минус одинаков для ECDSA и подписи Шнорра.
А что, если мы используем мультиподпись, т. е.
транзакция подписана несколькими людьми? В ECDSA мультиподпись это просто набор нескольких подписей.
Таким образом, по мере увеличения количества участников, которые должны подписать транзакцию, увеличивается и размер доказательства владения монетами.
Конфиденциальность ECDSA
Фактически, как только транзакция подтверждена, каждый участник сети может точно сказать, какие ключи использовались для ее подписания.Поскольку мультиподпись представляет собой набор значений подписи, каждая подпись формируется с использованием одного секретного ключа, который относится к одному открытому ключу, то есть каждому открытому ключу соответствует определенное значение подписи.
После того как вы проверили транзакцию с несколькими подписями, вы можете точно сказать, какие открытые ключи были использованы, и если вы знаете, какой конкретный объект владеет каким конкретным открытым ключом, вы можете назвать всех лиц, подписавших конкретную транзакцию.
Оказывается, конфиденциальность вообще не гарантируется.
Размер подписи ECDSA
Выделим ключевые поля транзакции: это scriptSig , то есть доказательство владения монетой, и скриптPubKey , то есть условия траты монет. Эти поля занимают наибольшее место во входах и выходах транзакций.Исходная архитектура подразумевала, что каждый конкретный вход должен содержать значения подписи (то есть, когда вы хотите потратить монеты с определенного выхода, вы должны указать значение подписи в качестве входных данных).
Выходные данные транзакции содержат фактический адрес получателя.
То есть, как мы уже рассматривали в ECDSA, могла возникнуть ситуация, что один вход содержал n значений, другой m и т.д. Это огромные объемы данных .
А как насчет подписи Шнорра?
Подпись Шнорра позволяет агрегировать значения ключей и подписей.Что случилось агрегирование ? Пусть у нас есть 4 субъекта и алгоритм мультиподписи; в случае ECDSA каждый из них создает свою подпись, и на выходе получается 4 подписи.
В случае со Шнорром у нас все те же четыре субъекта; они подписывают транзакцию, значения подписи суммируются и мы получаем одно общее значение, равное по размеру обычному значению подписи.
В результате, если мы применим эту модель к транзакции Биткойн, то каждый выход может иметь только одно значение подписи, это значительно уменьшает количество доказательств владения монетой.
Но при этом, когда мы подписываем, мы определяем значение подписи для каждого входа, мы также подписываем всю транзакцию.
Следовательно, можно агрегировать эти значения, то есть в результате одно значение подписи будет охватывать всю транзакцию.
Мы объединяем значение подписей в одно значение, и его можно проверить, объединив значения нашего открытого ключа.
Мы Мы значительно экономим на объеме транзакций соответственно, увеличивается пропускная способность, так как транзакция будет занимать меньше места, а блок останется прежним.
По поводу конфиденциальности в подписи Шнорра.
Что такое общий открытый ключ? В общем, это сумма открытых ключей, это наш агрегированный открытый ключ.
Значение подписи также агрегируется таким же образом, и мы получаем одно общее значение подписи.
Этот открытый ключ соответствует этой подписи.
Когда валидатор проверяет такую транзакцию, у нас есть ровно один открытый ключ на выходе транзакции и ровно одно значение подписи на входе транзакции.
То есть независимо от того, была ли транзакция подписана одним человеком или это была мультиподпись, валидатор не заметит этой разницы.
Это положительно влияет на конфиденциальность.
, потому что невозможно соотнести общий открытый ключ с конкретными субъектами.
В конце концов
Схема Шнорра — одна из наиболее эффективных и теоретически обоснованных схем аутентификации.Она оказалась не очень популярной из-за длительного патента, действовавшего до 2008 года.
С момента создания схема претерпела некоторые изменения, но ее основные идеи остались нетронутыми и высоко ценятся в криптографии.
Источники
- Статья Подписи Шнорра и неизбежность конфиденциальности в Биткойне
- Вики
- Семинар ИТМО по схеме Шнорра
- Лекция о подписях Шнорра в Биткойне
-
Переключатель Блокнота
19 Oct, 24 -
Плагин Для Выделения Последней Строки
19 Oct, 24 -
Simpoll: Опросы И Тесты Для Вашего Сайта
19 Oct, 24
