Русская Википедия:Подпись Меркла
Подпись Меркла — алгоритм постквантовой и многоразовой цифровой подписи, основанный на использовании дерева Меркла и какой-либо одноразовой цифровой подписи.Шаблон:Sfn
История
Впервые подпись была опубликована Ральфом Мерклом в 1979 в его статье «Secrecy, authentication, and public key systems»Шаблон:Sfn, как многоразовая цифровая подпись, использующая одноразовую подпись Лэмпорта.Шаблон:Sfn
Описание алгоритма
Подготовка
Подпись Меркла базируется на уже существующей одноразовой цифровой подписи, криптостойкость которой должна быть основана на криптостойкой хеш-функции. Примерами таких подписей могут быть Winternitz One-time Signature Scheme или подпись Лэмпорта.Шаблон:Sfn Одноразовая цифровая подпись должна состоять из трех основных операций:Шаблон:Sfn
- Генерация секретного ключа <math>X</math> и публичного ключа <math>Y</math>.
- Генерация подписи <math>b</math> из сообщения <math>d</math> с помощью секретного ключа <math>X</math>.
- Проверка подписи <math>b</math> с помощью открытого ключа <math>Y</math>.
Также необходимо определиться с криптостойкой хеш-функцией <math>H:\{0,1\}^* \rightarrow \{0,1\}^s</math>, которая позже будет использоваться для вычисления публичного ключа.Шаблон:Sfn
Генерация ключей
Генерируются массивы ключей <math>X</math> и <math>Y</math> длины <math>N = 2^n</math>. Длина выбирается равной степени двойки, так как это необходимо для построения дерева Меркла. Каждая пара <math>(X_i, Y_i)</math> используется как пара закрытый-открытый ключ для базовой одноразовой подписи. Массив <math>X</math> — является закрытым ключом подписи Меркла, для генерации открытого ключа строится дерево Меркла:
- Для каждого <math>Y_i</math> вычисляем хеш-значение <math>H(Y_i)</math> — это будет нулевой слой дерева, то есть его листья. Обозначим этот слой <math>a_0</math>. Всего <math>a_0</math> содержит <math>l_0 = 2^n</math> элементов. После чего вычисляем следующий <math>a_1</math> слой, имеющий размер <math>l_1 = 2^{n-1}</math>: каждый <math>j</math>-ый элемент слоя <math>a_1</math> вычисляется через два элемента с предыдущего слоя <math>a_{1,j} = H(a_{0,j*2} || a_{0,j*2 + 1})</math>, где <math>||</math> — операция конкатенации. Таким образом, каждый следующий <math>i</math>-ый слой, имеет длину <math>l_i = 2^{n-i}</math> и вычисляется через <math>i-1</math>-ый слой. В итоге, мы придем к последнему слою дерева <math>a_n</math>, имеющему длину <math>l_n = 1</math> и являющемуся корнем дерева.
За открытый ключ берется корень построенного дерева Меркла: <math>pub\_key = a_n</math>.Шаблон:Sfn
Генерация подписи
Для генерации подписи из массивов <math>X</math> и <math>Y</math> выбирается <math>i</math>-ая пара ключей <math>(X_i, Y_i)</math>.Для сообщения <math>d</math> вычисляется одноразовая цифровая подпись <math>b_i</math> с помощью закрытого ключа <math>X_i</math>. Далее рассмотрим путь от корня <math>a_{0,n}</math> дерева Меркла до листа <math>a_{0,i}</math>, соответствующему ключу <math>Y_i</math>. Обозначим вершины, через которые проходит этот путь, как массив <math>A</math> длины <math>n + 1</math>, где <math>A_n</math> — это корень дерева, а <math>A_0</math> — это <math>a_{0,i}</math>. Значение каждой вершины <math>A_j</math>, кроме <math>A_0 = H(Y_i)</math>, вычисляется как <math>H(A_{j-1} || auth_{j-1})</math>, где <math>auth_{j-1}</math> и <math>A_{j-1}</math> являются непосредственными потомками <math>A_{j}</math>. Таким образом, для того, чтобы вычислить путь от корня дерева достаточно знать <math>Y_i</math> и массив вершин <math>auth_1, auth_2, ..., auth_n</math>, который будем называть аутентификационным путем. Таким образом, в подпись сообщения <math>d</math> входит: верификационный ключ <math>Y_i</math>, одноразовая подпись <math>b_i</math> и аутентификационный путь для вычисления пути до корня дерева.Шаблон:Sfn
Проверка подписи
Во-первых, получатель проверяет одноразовую подпись <math>b_i</math> на соответствие сообщению <math>d</math>. Если проверка прошла успешно, то начинает построение пути от <math>H(Y_i)</math> до корня дерева. Сначала вычисляется <math>A_0 = H(Y_i)</math>, потом <math>A_{1} = H(A_0 || auth_0)</math> и так далее. Если <math>A_n = pub\_key</math>, то проверка подписи прошла успешно.Шаблон:Sfn
Преимущества
Постквантовость
В часто используемых алгоритмах цифровой подписи, таких как RSA и DSA, используется сложность факторизации чисел и сложность вычисления дискретного логарифма. Однако, используя алгоритм Шора и квантовый компьютер, эти подписи могут быть взломаны за полиномиальное время. В отличие от них подпись Меркла является постквантовой, так как её криптографическая стойкость основана на стойкости криптографической хеш-функции и стойкости одноразовой цифровой подписи.Шаблон:Sfn
Многоразовость
Одной из основных проблем цифровых подписей, основанных на криптостойких хеш-функциях, является то, что они, как правило, употребляются в контексте одноразовых цифровых подписей, то есть подписей, в которых одна пара ключей используется для подписи лишь одного сообщения. Однако, существуют способы расширения таких подписей до многоразовых. Одним из таких способов как раз является построение дерева Меркла, использующееся для аутентификации различных одноразовых подписей.Шаблон:Sfn
Недостатки
Проблема обхода дерева
Эта проблема связана с нахождением эффективного алгоритма вычисления аутентификационных данных. Тривиальное решение — сохранить все данные в памяти — требует слишком много памяти. С другой стороны, подход вычисления аутентификационного пути в области, где он нужен, будет слишком затратен для некоторых вершин дерева.Шаблон:Sfn Если длина массивов X и Y будет больше, чем 2^25, использование подписи Меркла становится непрактичным.Шаблон:Sfn
Криптоанализ
Доказано, что алгоритм цифровой подписи Меркла является криптостойким против адаптивной атаки с выбором сообщений, если в нем используется хеш-функция, стойкая к коллизиям второго рода.Шаблон:SfnШаблон:Sfn Однако, для того чтобы взломать подпись Меркла, криптоаналитику необходимо либо восстановить прообраз хеш-функции, либо вычислить коллизию первого рода. Это значит, что с практической точки зрения криптостойкость подписи Меркла базируется на необратимости использующейся хеш-функции и на её стойкости к коллизиям первого рода.Шаблон:Sfn
Примечания
Литература
