Схема подписи Меркла

В криптографии на основе хэша схема подписи Меркла представляет собой схему цифровой подписи, основанную на деревьях Меркла (также называемых хеш-деревьями) и одноразовых подписях, таких как схема подписи Лэмпорта . Он был разработан Ральфом Мерклем в конце 1970-х годов. ^[1] и является альтернативой традиционным цифровым подписям, таким как алгоритм цифровой подписи или RSA . NIST утвердил конкретные варианты схемы подписи Меркла в 2020 году. ^[2]

Преимущество схемы подписи Меркла состоит в том, что она считается устойчивой к атакам квантовых компьютеров . Традиционные алгоритмы с открытым ключом , такие как RSA и Эль-Гамаль, стали бы небезопасными, если бы можно было построить эффективный квантовый компьютер (из-за алгоритма Шора ). Однако схема подписи Меркла зависит только от существования безопасных хеш-функций . Это делает схему подписи Меркла очень гибкой и устойчивой к атакам с использованием квантовых компьютеров. Подпись Меркла — это одноразовая подпись с ограниченным потенциалом подписи. Работа Мони Наора и Моти Юнга и функциям на основе подписи по односторонним перестановкам (а также изобретение универсальных односторонних хеш-функций ) дает возможность расширить подпись, подобную Меркле, до полной схемы подписи. ^[3]

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

Схема подписи Меркла может использоваться для подписи ограниченного количества сообщений одним открытым ключом. ${\text{pub}}$ . Число возможных сообщений должно быть степенью двойки, поэтому мы обозначаем возможное количество сообщений как $N=2^{n}$ .

Первый шаг генерации открытого ключа ${\text{pub}}$ заключается в создании $N$ пары частного/открытого ключей $(X_{i},Y_{i})$ какой-либо схемы одноразовой подписи (например, схемы подписи Лэмпорта). Для каждого $1\leq i\leq 2^{n}$ , хэш-значение открытого ключа $h_{i}=H(Y_{i})$ вычисляется.

С этими хеш-значениями $h_{i}$ строится хеш-дерево путем размещения этих $2^{n}$ хэш-значения в виде листьев и рекурсивное хэширование для формирования двоичного дерева. Позволять $a_{i,j}$ обозначаем узел в дереве высотой $i$ и лево-правое положение $j$ . Затем хеш-значения $h_{i}=a_{0,i}$ это листья. Значением каждого внутреннего узла дерева является хэш конкатенации двух его дочерних узлов. Например, $a_{1,0}=H(a_{0,0}||a_{0,1})$ и $a_{2,0}=H(a_{1,0}||a_{1,1})$ . Таким образом, дерево с $2^{n}$ листья и $2^{n+1}-1$ узлы построены.

Закрытый ключ схемы подписи Меркла представляет собой весь набор $(X_{i},Y_{i})$ пары. Недостатком этой схемы является то, что размер закрытого ключа линейно зависит от количества отправляемых сообщений.

Открытый ключ ${\text{pub}}$ это корень дерева, $a_{n,0}$ . Отдельные открытые ключи $Y_{i}$ могут быть обнародованы без нарушения безопасности. Однако они не нужны в открытом ключе, поэтому их можно хранить в секрете, чтобы минимизировать размер открытого ключа.

Генерация подписи

Чтобы подписать сообщение $M$ при использовании схемы подписи Меркла подписывающее лицо выбирает пару ключей. $(X_{i},Y_{i})$ , подписывает сообщение, используя схему одноразовой подписи, а затем добавляет дополнительную информацию, чтобы доказать, что использованная пара ключей была одной из исходных пар ключей (а не новой, созданной фальсификатором).

Дерево Меркла с путем A и путем аутентификации для i = 2, n = 3

Сначала подписывающая сторона выбирает $(X_{i},Y_{i})$ пара, которая ранее не использовалась для подписи какого-либо другого сообщения, и использует схему одноразовой подписи для подписи сообщения, в результате чего получается подпись ${\text{sig}}'$ и соответствующий открытый ключ $Y_{i}$ . Чтобы доказать верификатору сообщения, что $(X_{i},Y_{i})$ на самом деле была одной из исходных пар ключей, подписывающая сторона просто включает промежуточные узлы дерева Меркла, чтобы проверяющая сторона могла проверить $h_{i}=a_{0,i}$ использовался для вычисления открытого ключа $a_{n,0}$ у корня дерева. Путь в хеш-дереве от $a_{0,i}$ в корень это $n+1$ узлы длинные. Вызов узлов $A_{0},\ldots ,A_{n}$ , с $A_{0}=a_{0,i}=H(Y_{i})$ будучи листом и $A_{n}=a_{n,0}={\text{pub}}$ являющийся корнем.

$A_{i}$ является ребенком $A_{i+1}$ . Чтобы верификатор вычислил следующий узел $A_{i+1}$ учитывая предыдущее, им нужно знать другого ребенка $A_{i+1}$ , родственный узел $A_{i}$ . Мы называем этот узел ${\text{auth}}_{i}$ , так что $A_{i+1}=H(A_{i}||{\text{auth}}_{i})$ . Следовательно, $n$ узлы ${\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}$ необходимы для восстановления $A_{n}=a_{n,0}={\text{pub}}$ от $A_{0}=a_{0,i}$ . Пример пути аутентификации показан на рисунке справа.

Вместе узлы ${\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}$ , $Y_{i}$ и одноразовая подпись ${\text{sig}}'$ представляют собой подпись $M$ используя схему подписи Меркла: ${\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})$ .

Обратите внимание, что при использовании схемы подписи Лэмпорта в качестве схемы одноразовой подписи: ${\text{sig}}'$ содержит часть закрытого ключа $X_{i}$ .

Проверка подписи

Получатель знает открытый ключ ${\text{pub}}$ , сообщение $M$ и подпись ${\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})$ . Сначала получатель проверяет одноразовую подпись. ${\text{sig}}'$ сообщения $M$ с использованием открытого ключа одноразовой подписи $Y_{i}$ . Если ${\text{sig}}'$ является действительной подписью $M$ , приемник вычисляет $A_{0}=H(Y_{i})$ путем хеширования открытого ключа одноразовой подписи. Для $j=1,\ldots ,n-1$ , узлы $A_{j}$ пути вычисляются с помощью $A_{j}=H(A_{j-1}||{\text{auth}}_{j-1})$ . Если $A_{n}$ равен открытому ключу ${\text{pub}}$ схемы подписи Меркла, подпись действительна.

Ссылки

^ Меркл, Ральф (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 частей о подписях на основе хэшей Дэвида Вонга.

[1] Меркл, Ральф (1979). «Системы секретности, аутентификации и открытых ключей» (PDF) . доктор философии Диссертация : 32–61.

[2] «Схемы подписи на основе хэша с сохранением состояния: SP 800-208 | CSRC» . 30 октября 2020 г.

[3] Наор, Мони; Юнг, Моти (1989). «Универсальные односторонние хэш-функции и их криптографические приложения» (PDF) . Симпозиум по теории вычислений : 33–43.

[1]

[2]

[3]