Подпись Меркла

Подпись Меркла — алгоритм постквантовой и многоразовой цифровой подписи, основанный на использовании дерева Меркла и какой-либо одноразовой цифровой подписи.

История

Впервые подпись была опубликована Ральфом Мерклом в 1979 в его статье «Secrecy, authentication, and public key systems», как многоразовая цифровая подпись, использующая одноразовую подпись Лэмпорта.

Описание алгоритма

Подготовка

Подпись Меркла базируется на уже существующей одноразовой цифровой подписи, криптостойкость которой должна быть основана на криптостойкой хеш-функции. Примерами таких подписей могут быть Winternitz One-time Signature Scheme или подпись Лэмпорта. Одноразовая цифровая подпись должна состоять из трех основных операций:

• Генерация секретного ключа $X$ и публичного ключа $Y$.
• Генерация подписи $b$ из сообщения $d$ с помощью секретного ключа $X$.
• Проверка подписи $b$ с помощью открытого ключа $Y$.

Также необходимо определиться с криптостойкой хеш-функцией $H:\{0,1\}^{*}\rightarrow \{0,1\}^{s}$, которая позже будет использоваться для вычисления публичного ключа.

Дерево Меркла для восьми ключей

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

Генерируются массивы ключей $X$ и $Y$ длины $N=2^{n}$. Длина выбирается равной степени двойки, так как это необходимо для построения дерева Меркла. Каждая пара $(X_{i},Y_{i})$ используется как пара закрытый-открытый ключ для базовой одноразовой подписи. Массив $X$ — является закрытым ключом подписи Меркла, для генерации открытого ключа строится дерево Меркла:

• Для каждого $Y_{i}$ вычисляем хеш-значение $H(Y_{i})$ — это будет нулевой слой дерева, то есть его листья. Обозначим этот слой $a_{0}$. Всего $a_{0}$ содержит $l_{0}=2^{n}$ элементов. После чего вычисляем следующий $a_{1}$ слой, имеющий размер $l_{1}=2^{n-1}$: каждый $j$-ый элемент слоя $a_{1}$ вычисляется через два элемента с предыдущего слоя $a_{1,j}=H(a_{0,j*2}||a_{0,j*2+1})$, где $||$ — операция конкатенации. Таким образом, каждый следующий $i$-ый слой, имеет длину $l_{i}=2^{n-i}$ и вычисляется через $i-1$-ый слой. В итоге, мы придем к последнему слою дерева $a_{n}$, имеющему длину $l_{n}=1$ и являющемуся корнем дерева.

За открытый ключ берется корень построенного дерева Меркла: $pub\_key=a_{n}$.

Дерево Меркла для восьми ключей с путем аутентификации

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

Для генерации подписи из массивов $X$ и $Y$ выбирается $i$-ая пара ключей $(X_{i},Y_{i})$.Для сообщения $d$ вычисляется одноразовая цифровая подпись $b_{i}$ с помощью закрытого ключа $X_{i}$. Далее рассмотрим путь от корня $a_{0,n}$ дерева Меркла до листа $a_{0,i}$, соответствующему ключу $Y_{i}$. Обозначим вершины, через которые проходит этот путь, как массив $A$ длины $n+1$, где $A_{n}$ — это корень дерева, а $A_{0}$ — это $a_{0,i}$. Значение каждой вершины $A_{j}$, кроме $A_{0}=H(Y_{i})$, вычисляется как $H(A_{j-1}||auth_{j-1})$, где $auth_{j-1}$ и $A_{j-1}$ являются непосредственными потомками $A_{j}$. Таким образом, для того, чтобы вычислить путь от корня дерева достаточно знать $Y_{i}$ и массив вершин $auth_{1},auth_{2},...,auth_{n}$, который будем называть аутентификационным путем. Таким образом, в подпись сообщения $d$ входит: верификационный ключ $Y_{i}$, одноразовая подпись $b_{i}$ и аутентификационный путь для вычисления пути до корня дерева.

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

Во-первых, получатель проверяет одноразовую подпись $b_{i}$ на соответствие сообщению $d$. Если проверка прошла успешно, то начинает построение пути от $H(Y_{i})$ до корня дерева. Сначала вычисляется $A_{0}=H(Y_{i})$, потом $A_{1}=H(A_{0}||auth_{0})$ и так далее. Если $A_{n}=pub\_key$, то проверка подписи прошла успешно.

Преимущества

Постквантовость

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

Многоразовость

Одной из основных проблем цифровых подписей, основанных на криптостойких хеш-функциях, является то, что они, как правило, употребляются в контексте одноразовых цифровых подписей, то есть подписей, в которых одна пара ключей используется для подписи лишь одного сообщения. Однако, существуют способы расширения таких подписей до многоразовых. Одним из таких способов как раз является построение дерева Меркла, использующееся для аутентификации различных одноразовых подписей.

Недостатки

Проблема обхода дерева

Эта проблема связана с нахождением эффективного алгоритма вычисления аутентификационных данных. Тривиальное решение — сохранить все данные в памяти — требует слишком много памяти. С другой стороны, подход вычисления аутентификационного пути в области, где он нужен, будет слишком затратен для некоторых вершин дерева. Если длина массивов X и Y будет больше, чем 2^25, использование подписи Меркла становится непрактичным.

Криптоанализ

Доказано, что алгоритм цифровой подписи Меркла является криптостойким против адаптивной атаки с выбором сообщений, если в нем используется хеш-функция, стойкая к коллизиям второго рода. Однако, для того чтобы взломать подпись Меркла, криптоаналитику необходимо либо восстановить прообраз хеш-функции, либо вычислить коллизию первого рода. Это значит, что с практической точки зрения криптостойкость подписи Меркла базируется на необратимости использующейся хеш-функции и на её стойкости к коллизиям первого рода.

Литература

• Merkle, Ralph Charles. Secrecy, authentication, and public key systems : Technical Report No. 1979-1. — Citeseer, 1979. — doi:10.1.1.637.3952.

• Garcıa, LC Coronado. On the security and the efficiency of the Merkle signature scheme : Technical Report 2005/192. — Cryptology ePrint Archive, 2005.

• Buchmann, Johannes. CMSS–an improved Merkle signature scheme // International Conference on Cryptology in India. — Springer Berlin Heidelberg, 2006. — С. 349—363. — doi:10.1007/11941378_25. (недоступная ссылка)

• Dods, Chris and Smart, Nigel P and Stam, Martijn. Hash based digital signature schemes // IMA International Conference on Cryptography and Coding. — Springer Berlin Heidelberg, 2005. — С. 96—115. — doi:10.1007/11586821_8.

• Szydlo, Michael. Merkle tree traversal in log space and time // International Conference on the Theory and Applications of Cryptographic Techniques. — Springer Berlin Heidelberg, 2004. — С. 541—554. — doi:10.1007/978-3-540-24676-3_32.

• Rohde, Sebastian and Eisenbarth, Thomas and Dahmen, Erik and Buchmann, Johannes and Paar, Christof. Fast hash-based signatures on constrained devices // International Conference on Smart Card Research and Advanced Applications. — Springer Berlin Heidelberg, 2008. — С. 104—117. — doi:10.1007/978-3-540-85893-5_8.