Схема подписи Меркла
В криптографии на основе хэша схема подписи Меркла представляет собой схему цифровой подписи, основанную на деревьях Меркла (также называемых хеш-деревьями) и одноразовых подписях, таких как схема подписи Лэмпорта . Он был разработан Ральфом Мерклем в конце 1970-х годов. [1] и является альтернативой традиционным цифровым подписям, таким как алгоритм цифровой подписи или RSA . NIST утвердил конкретные варианты схемы подписи Меркла в 2020 году. [2]
Преимущество схемы подписи Меркла состоит в том, что она считается устойчивой к атакам квантовых компьютеров . Традиционные алгоритмы с открытым ключом , такие как RSA и Эль-Гамаль, стали бы небезопасными, если бы можно было построить эффективный квантовый компьютер (из-за алгоритма Шора ). Однако схема подписи Меркла зависит только от существования безопасных хеш-функций . Это делает схему подписи Меркла очень гибкой и устойчивой к атакам с использованием квантовых компьютеров. Подпись Меркла — это одноразовая подпись с ограниченным потенциалом подписи. Работа Мони Наора и Моти Юнга и функциям на основе подписи по односторонним перестановкам (а также изобретение универсальных односторонних хеш-функций ) дает возможность расширить подпись, подобную Меркле, до полной схемы подписи. [3]
Генерация ключей
[ редактировать ]Схема подписи Меркла может использоваться для подписи ограниченного количества сообщений одним открытым ключом. . Число возможных сообщений должно быть степенью двойки, поэтому мы обозначаем возможное количество сообщений как .
Первый шаг генерации открытого ключа заключается в создании пары частного/открытого ключей какой-либо схемы одноразовой подписи (например, схемы подписи Лэмпорта). Для каждого , хэш-значение открытого ключа вычисляется.
С этими хеш-значениями строится хеш-дерево путем размещения этих хэш-значения в виде листьев и рекурсивное хэширование для формирования двоичного дерева. Позволять обозначаем узел в дереве высотой и лево-правое положение . Затем хеш-значения это листья. Значением каждого внутреннего узла дерева является хэш конкатенации двух его дочерних узлов. Например, и . Таким образом, дерево с листья и узлы построены.
Закрытый ключ схемы подписи Меркла представляет собой весь набор пары. Недостатком этой схемы является то, что размер закрытого ключа линейно зависит от количества отправляемых сообщений.
Открытый ключ это корень дерева, . Отдельные открытые ключи могут быть обнародованы без нарушения безопасности. Однако они не нужны в открытом ключе, поэтому их можно хранить в секрете, чтобы минимизировать размер открытого ключа.
Генерация подписи
[ редактировать ]Чтобы подписать сообщение при использовании схемы подписи Меркла подписывающее лицо выбирает пару ключей. , подписывает сообщение, используя схему одноразовой подписи, а затем добавляет дополнительную информацию, чтобы доказать, что использованная пара ключей была одной из исходных пар ключей (а не новой, созданной фальсификатором).
Сначала подписывающая сторона выбирает пара, которая ранее не использовалась для подписи какого-либо другого сообщения, и использует схему одноразовой подписи для подписи сообщения, в результате чего получается подпись и соответствующий открытый ключ . Чтобы доказать верификатору сообщения, что на самом деле была одной из исходных пар ключей, подписывающая сторона просто включает промежуточные узлы дерева Меркла, чтобы проверяющая сторона могла проверить использовался для вычисления открытого ключа у корня дерева. Путь в хеш-дереве от в корень это узлы длинные. Вызов узлов , с будучи листом и являющийся корнем.
является ребенком . Чтобы верификатор вычислил следующий узел учитывая предыдущее, им нужно знать другого ребенка , родственный узел . Мы называем этот узел , так что . Следовательно, узлы необходимы для восстановления от . Пример пути аутентификации показан на рисунке справа.
Вместе узлы , и одноразовая подпись представляют собой подпись используя схему подписи Меркла: .
Обратите внимание, что при использовании схемы подписи Лэмпорта в качестве схемы одноразовой подписи: содержит часть закрытого ключа .
Проверка подписи
[ редактировать ]Получатель знает открытый ключ , сообщение и подпись . Сначала получатель проверяет одноразовую подпись. сообщения с использованием открытого ключа одноразовой подписи . Если является действительной подписью , приемник вычисляет путем хеширования открытого ключа одноразовой подписи. Для , узлы пути вычисляются с помощью . Если равен открытому ключу схемы подписи Меркла, подпись действительна.
Ссылки
[ редактировать ]- ^ Меркл, Ральф (1979). «Системы секретности, аутентификации и открытых ключей» (PDF) . доктор философии Диссертация : 32–61.
- ^ «Схемы подписи на основе хэша с сохранением состояния: SP 800-208 | CSRC» . 30 октября 2020 г.
- ^ Наор, Мони; Юнг, Моти (1989). «Универсальные односторонние хэш-функции и их криптографические приложения» (PDF) . Симпозиум по теории вычислений : 33–43.
- Э. Дамен, М. Дринг, Э. Клинцевич, Дж. Бухманн, Л. С. Коронадо Гарса. «CMSS — улучшенная схема подписи Меркла». Прогресс в криптологии – Indocrypt 2006, 2006.
- Э. Клинцевич, К. Окейя, К. Вийом, Ж. Бухман, Э. Дамен. «Подписи Меркла с практически неограниченной емкостью подписей». 5-я Международная конференция по прикладной криптографии и сетевой безопасности - ACNS07, 2007 г.
- С. Микали, М. Якобссон, Т. Лейтон, М. Шидло. «Представление и обход фрактального дерева Меркла». РСА-КТ 03, 2003 г.
Внешние ссылки
[ редактировать ]- Эффективное использование деревьев Меркла - объяснение в лабораториях RSA первоначального назначения деревьев Меркла + подписей Лэмпорта как эффективной схемы одноразовой подписи.
- Введение в подписи на основе хеша и подписи Меркла Адама Лэнгли.
- Серия из 4 частей о подписях на основе хэшей Дэвида Вонга.