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

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

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

• 1 Генерация ключей
• 2 Генерация подписи
• 3 Проверка подписи
• 4 ссылки
• 5 Внешние ссылки

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

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

Дерево Меркла с 8 листьями

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

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

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

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

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

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

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

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

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

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

• Э. Дахмен, М. Дринг, Э. Клинцевич, Дж. Бухманн, LC Coronado Garca. «CMSS - улучшенная схема подписи Меркла». Прогресс в криптологии - Indocrypt 2006, 2006.
• Э. Клинцевич, К. Окея, К. Вийом, Я. Бухманн, Э. Дахмен. «Подписи Меркла с практически неограниченной емкостью подписи». 5-я Международная конференция по прикладной криптографии и сетевой безопасности - ACNS07, 2007.
• Ральф Меркл. «Системы секретности, аутентификации и открытого ключа / Сертифицированная цифровая подпись». Кандидат наук. докторская диссертация, кафедра электротехники, Стэнфордский университет, 1979. [1]
• Мони Наор, Моти Юнг: Универсальные односторонние хеш-функции и их криптографические приложения. STOC 1989: 33-43
• С. Микали, М. Якобссон, Т. Лейтон, М. Шидло. «Фрактальное представление дерева Меркла и его обход». RSA-CT 03, 2003 г.

• Эффективное использование деревьев Меркла - RSA labs объясняет первоначальную цель деревьев Меркла + подписи Лампорта как эффективной схемы одноразовой подписи.
• Введение в подписи на основе хешей и подписи Меркла от Адама Лэнгли.
• Серия из 4 частей Дэвида Вонга о подписях на основе хешей.