En la criptografía basada en hash , el esquema de firma de Merkle es un esquema de firma digital basado en árboles de hash (también llamados árboles de Merkle) y firmas de una sola vez, como el esquema de firma de Lamport . Fue desarrollado por Ralph Merkle a fines de la década de 1970 y es una alternativa a las firmas digitales tradicionales, como el algoritmo de firma digital o RSA .
La ventaja del esquema de firma de Merkle es que se cree que es resistente a los algoritmos de la computadora cuántica . Los algoritmos tradicionales de clave pública, como RSA y ElGamal, se volverían inseguros en caso de que se pudiera construir una computadora cuántica efectiva (debido al algoritmo de Shor ). Sin embargo, el esquema de firma de Merkle solo depende de la existencia de funciones hash seguras . Esto hace que el esquema de firma de Merkle sea muy ajustable y resistente a la computación cuántica. Tenga en cuenta que la firma Merkle es una firma única con un potencial de firma finito; el trabajo de Moni Naor y Moti Yung sobre la firma basada en permutaciones y funciones unidireccionales (y la invención defunción hash unidireccional universal ) dan una forma de extender una firma similar a Merkle a un esquema de firma completo. [ cita requerida ]
Generación de claves
El esquema de firma de 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.
El primer paso para generar la clave pública es generar pares de claves privadas / públicas de algún esquema de firma de una sola vez (como el esquema de firma de Lamport). Para cada, un valor hash de la clave pública se calcula.
Con estos valores hash se construye un árbol de hachís , colocando estosvalores hash como hojas y hash recursivamente para formar un árbol binario. Dejar denotar el nodo en el árbol con altura y posición izquierda-derecha . Entonces, los valores hashson 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, un árbol con hojas y se construyen los nodos.
La clave privada del esquema de firma Merkle es el conjunto completo de pares. Uno de los principales problemas del esquema es que el tamaño de la clave privada se escala linealmente con la cantidad de mensajes que se enviarán.
La clave pública es la raíz del árbol, . Las claves públicas individualespuede hacerse público sin violar la seguridad. Sin embargo, como no se necesitan en la clave pública, es más práctico mantenerlos en secreto para minimizar su tamaño.
Generación de firmas
Para firmar un mensaje con el esquema de la firma Merkle, el firmante elige un par de claves , firma utilizando el esquema de firma de una sola vez, y luego agrega información adicional para demostrar que efectivamente era uno de los pares de claves originales (en lugar de uno recién generado por un falsificador).
Primero, el firmante elige un par que no se había utilizado anteriormente para firmar ningún otro mensaje, y utiliza el esquema de firma de una sola vez para firmar el mensaje, lo que da como resultado una firma y la clave pública correspondiente . Para demostrarle al verificador de mensajes que era de hecho uno de los pares de claves originales, el firmante simplemente incluye nodos intermedios del árbol Merkle para que el verificador pueda verificar se utilizó para calcular la clave pública en la raíz del árbol. El camino en el árbol de hachís desde a la raíz sea nodos, llámalos , con siendo una hoja y siendo la raíz.
Lo sabemos es hijo de . Para permitir que el verificador calcule el siguiente nodo dado lo anterior, necesitan conocer al otro hijo de , el nodo hermano de . Llamamos a este nodo, así que eso . Por eso, nodos son necesarios para reconstruir de . En la figura de la derecha se ilustra un ejemplo de una ruta de autenticación.
Estos nodos , la y la firma de una sola vez , juntos constituyen una firma de usando el esquema de la firma Merkle: .
Tenga en cuenta que al utilizar el esquema de firma de Lamport para firmar, el contiene una parte de la clave privada .
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 usando la clave pública de firma de un solo uso . Si es una firma válida de , el receptor calcula Haciendo hash de la clave pública de la firma de un solo uso. Para, los nodos de de la ruta se calculan con . Si es igual a la clave pública del esquema de la firma Merkle, la firma es válida.
Referencias
- E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, LC Coronado Garca. "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". Quinta Conferencia Internacional sobre Criptografía Aplicada y Seguridad de Redes - ACNS07, 2007.
- Ralph Merkle. "Secreto, autenticación y sistemas de clave pública / Una firma digital certificada". Doctor. disertación, Departamento de Ingeniería Eléctrica, Universidad de Stanford, 1979. [1]
- Moni Naor, Moti Yung: Funciones hash unidireccionales universales y sus aplicaciones criptográficas. STOC 1989: 33-43
- S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Representación y recorrido del árbol de merkle fractal". RSA-CT 03 de 2003
enlaces externos
- Uso eficiente de los árboles Merkle : explicación de RSA Labs del propósito original de los árboles Merkle + firmas de Lamport, como un esquema eficiente de firma de una sola vez.
- Una introducción a las firmas basadas en hash y firmas Merkle por Adam Langley.
- Una serie de 4 partes sobre firmas basadas en hash de David Wong.