Esquema de firma Merkle

En criptografía basada en hash , el esquema de firma Merkle es un esquema de firma digital basado en árboles Merkle (también llamados árboles hash) y firmas únicas como el esquema de firma Lamport . Fue desarrollado por Ralph Merkle a finales de los años 1970 ^[1] y es una alternativa a las firmas digitales tradicionales como el Algoritmo de Firma Digital o RSA . NIST aprobó variantes específicas del esquema de firma Merkle en 2020. ^[2]

Una ventaja del esquema de firma Merkle es que se cree que es resistente a ataques de computadoras cuánticas . Los algoritmos tradicionales de clave pública , como RSA y ElGamal , se volverían inseguros si se pudiera construir una computadora cuántica efectiva (debido al algoritmo de Shor ). El esquema de firma Merkle, sin embargo, sólo depende de la existencia de funciones hash seguras . Esto hace que el esquema de firma de Merkle sea muy ajustable y resistente a los ataques informáticos cuánticos. La firma Merkle es una firma única con un potencial de firma finito. El trabajo de Moni Naor y Moti Yung sobre permutaciones y funciones unidireccionales basadas en firmas (y la invención de funciones hash unidireccionales universales ) ofrece una manera de extender una firma tipo Merkle a un esquema de firma completo. ^[3]

Generación de claves

El esquema de firma Merkle se puede utilizar para firmar un número limitado de mensajes con una clave pública . El número de mensajes posibles debe ser una potencia de dos, por lo que denotamos el número posible de mensajes como . ${\displaystyle {\text{pub}}}$ ${\displaystyle N=2^{n}}$

El primer paso para generar la clave pública es generar pares de claves pública y privada de algún esquema de firma única (como el esquema de firma Lamport). Para cada uno , se calcula un valor hash de la clave pública . ${\displaystyle {\text{pub}}}$ ${\displaystyle N}$ ${\displaystyle (X_{i},Y_{i})}$ ${\displaystyle 1\leq i\leq 2^{n}}$ ${\displaystyle h_{i}=H(Y_{i})}$

Merkle Árbol con 8 hojas

Con estos valores hash se construye un árbol hash , colocando estos valores hash como hojas y aplicando hash recursivamente para formar un árbol binario. Denotemos el nodo en el árbol con altura y posición izquierda-derecha . Entonces, los valores hash son las hojas. El valor de cada nodo interno del árbol es el hash de la concatenación de sus dos hijos. Por ejemplo, y . De esta forma se construye un árbol con hojas y nudos. ${\displaystyle h_{i}}$ ${\displaystyle 2^{n}}$ ${\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^{n}}$ ${\displaystyle 2^{n+1}-1}$

La clave privada del esquema de firma Merkle es el conjunto completo de pares. Una deficiencia del esquema es que el tamaño de la clave privada aumenta linealmente con la cantidad de mensajes que se enviarán. ${\displaystyle (X_{i},Y_{i})}$

La clave pública es la raíz del árbol . Las claves públicas individuales se pueden hacer públicas sin violar la seguridad. Sin embargo, no son necesarios en la clave pública, por lo que pueden mantenerse en secreto para minimizar el tamaño de la clave pública. ${\displaystyle {\text{pub}}}$ ${\displaystyle a_{n,0}}$ ${\displaystyle Y_{i}}$

Generación de firma

Para firmar un mensaje con el esquema de firma Merkle, el firmante elige un par de claves , firma el mensaje usando el esquema de firma única y luego agrega información adicional para demostrar que el par de claves utilizado fue uno de los pares de claves originales (en lugar de uno recién generado por un falsificador). ${\displaystyle M}$ ${\displaystyle (X_{i},Y_{i})}$

Árbol Merkle con ruta A y ruta de autenticación para i = 2, n = 3

En primer lugar, el firmante elige un par que no se había utilizado previamente para firmar ningún otro mensaje y utiliza el esquema de firma única para firmar el mensaje, lo que da como resultado una firma y la clave pública correspondiente . Para demostrarle al verificador de mensajes que en realidad era uno de los pares de claves originales, el firmante simplemente incluye nodos intermedios del árbol Merkle para que el verificador pueda verificar que se utilizó para calcular la clave pública en la raíz del árbol. La ruta en el árbol hash desde la raíz tiene una longitud de nodos. Llama a los nodos , siendo hoja y siendo raíz. ${\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}}$es hijo de . Para permitir que el verificador calcule el siguiente nodo dado el anterior, necesita conocer el otro hijo de , el nodo hermano de . Llamamos a este nodo , para que . Por lo tanto, se necesitan nodos para reconstruir a partir de . En la figura de la derecha se ilustra un ejemplo de una ruta de autenticación. ${\displaystyle A_{i+1}}$ ${\displaystyle A_{i+1}}$ ${\displaystyle A_{i+1}}$ ${\displaystyle A_{i}}$ ${\displaystyle {\text{auth}}_{i}}$ ${\displaystyle A_{i+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}}$

Juntos, los nodos , y la firma única constituyen una firma que utiliza el esquema de firma Merkle: . ${\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})}$

Tenga en cuenta que cuando se utiliza el esquema de firma Lamport como esquema de firma única, contiene una parte de la clave privada . ${\displaystyle {\text{sig}}'}$ ${\displaystyle X_{i}}$

Verificación de firma

El receptor conoce la clave pública , el mensaje y la firma . Primero, el receptor verifica la firma única del mensaje utilizando la clave pública de firma única . Si es una firma válida de , el receptor la calcula aplicando hash a la clave pública de la firma única. Para , los nodos de la ruta se calculan con . Si es igual a la clave pública del esquema de firma Merkle, la firma es válida. ${\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 ,n-1}$ ${\displaystyle A_{j}}$ ${\displaystyle A_{j}=H(A_{j-1}||{\text{auth}}_{j-1})}$ ${\displaystyle A_{n}}$ ${\displaystyle {\text{pub}}}$

Referencias

1. Merkle, Ralph (1979). «Sistemas de secreto, autenticación y clave pública» (PDF) . Doctor. Disertación : 32–61.
2. "Esquemas de firma basados ​​en hash con estado: SP 800-208 | CSRC". 30 de octubre de 2020.
3. Naor, Moni; Yung, Moti (1989). "Funciones hash unidireccionales universales y sus aplicaciones criptográficas" (PDF) . Simposio sobre teoría de la informática : 33–43.

• E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, LC Coronado García. "CMSS: un esquema de firma merkle mejorado". Progreso en criptología - Indocrypt 2006, 2006.
• E. Klintsevich, K. Okeya, C. Vuillaume, J. Buchmann, E. Dahmen. "Firmas Merkle con capacidad de firma prácticamente ilimitada". 5ta Conferencia Internacional sobre Criptografía Aplicada y Seguridad de Redes - ACNS07, 2007.
• S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Representación y recorrido del árbol fractal merkle". RSA-CT 03, 2003

enlaces externos

• Uso eficiente de los árboles Merkle: explicación de los laboratorios RSA del propósito original de los árboles Merkle + firmas Lamport, como un esquema eficiente de firma única.
• Una introducción a las firmas basadas en hash y las firmas Merkle por Adam Langley.
• Una serie de 4 partes sobre firmas basadas en hash de David Wong.