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

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

История

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

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

Подготовка

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

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

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

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

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

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

За открытый ключ берется корень построенного дерева Меркла: p u b _ k e y = a n {displaystyle pub_key=a_{n}} .

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

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

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

Во-первых, получатель проверяет одноразовую подпись b i {displaystyle b_{i}} на соответствие сообщению d {displaystyle d} . Если проверка прошла успешно, то начинает построение пути от H ( Y i ) {displaystyle H(Y_{i})} до корня дерева. Сначала вычисляется A 0 = H ( Y i ) {displaystyle A_{0}=H(Y_{i})} , потом A 1 = H ( A 0 | | a u t h 0 ) {displaystyle A_{1}=H(A_{0}||auth_{0})} и так далее. Если A n = p u b _ k e y {displaystyle A_{n}=pub_key} , то проверка подписи прошла успешно.

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

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

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

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

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

Недостатки

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

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

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

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