En criptografía , los acertijos de Merkle son una construcción temprana de un criptosistema de clave pública, un protocolo ideado por Ralph Merkle en 1974 y publicado en 1978. Permite que dos partes acuerden un secreto compartido intercambiando mensajes, incluso si no tienen secretos en común de antemano.
Descripción
Suponga que Alice y Bob desean comunicarse. Bob puede enviar un mensaje a Alice de la siguiente manera: primero crea una gran cantidad de rompecabezas, cada uno de una dificultad moderada; debe ser posible que Alice resuelva el rompecabezas con una cantidad moderada de esfuerzo informático. Los acertijos tienen la forma de un mensaje encriptado con una clave desconocida ; la clave debe ser lo suficientemente corta para permitir un ataque de fuerza bruta . Bob envía todos los acertijos (es decir, mensajes encriptados) a Alice, quien elige uno al azar y lo resuelve. La solución descifrada contiene un identificador y una clave de sesión, por lo que Alice puede comunicarle a Bob qué rompecabezas ha resuelto. Ambas partes tienen ahora una clave común; Alice, porque resolvió un rompecabezas, y Bob, porque él envió el rompecabezas. Cualquier espía (por ejemplo, Eve) tiene una tarea más difícil: no sabe qué acertijo resolvió Alice. Su mejor estrategia es resolver todos los acertijos, pero como hay tantos, esto es más costoso computacionalmente para Eve que para Alice.
Descripción de alto nivel
- Bob genera 2 N mensajes que contienen, "Este es el mensaje X. Esta es la clave simétrica Y", donde X es un identificador generado aleatoriamente e Y es una clave secreta generada aleatoriamente destinada al cifrado simétrico. Por tanto, tanto X como Y son únicos para cada mensaje. Todos los mensajes están encriptados de tal manera que un usuario puede realizar un ataque de fuerza bruta en cada mensaje con cierta dificultad. Bob envía todos los mensajes cifrados a Alice.
- Alice recibe todos los mensajes encriptados y elige aleatoriamente un solo mensaje por fuerza bruta. Después de que Alice descubre tanto el identificador X como la clave secreta Y dentro de ese mensaje, encripta su texto sin cifrar con la clave secreta Y, y envía ese identificador (en texto sin cifrar) con su texto cifrado a Bob.
- Bob busca la clave secreta emparejada con ese identificador, ya que él es quien los generó en primer lugar, y descifra el texto cifrado de Alice con esa clave secreta.
Tenga en cuenta que la espía Eve puede leer el identificador X enviado de vuelta (en texto sin cifrar) de Alice a Bob, pero no tiene forma de asignarlo a la clave secreta Y que Bob y Alice están usando ahora para su comunicación en curso, porque el valor de X dentro de cada mensaje se generó aleatoriamente.
Complejidad
Suponga que el número de acertijos enviados por Bob es m , y que tanto Bob como Alice necesitan n pasos de cálculo para resolver un acertijo. Entonces, ambos pueden deducir una clave de sesión común dentro de una complejidad de tiempo de O ( m + n ). Eve, por el contrario, debe resolver todos los acertijos, lo que le toma O ( mn ) de tiempo. Si m ≈ n , el esfuerzo de Eve tiene una complejidad aproximadamente cuadrática en comparación con Alice y Bob. Por lo tanto, n debe seleccionarse de manera que el cálculo sea todavía factible para Alice y Bob mientras supere las capacidades de Eve.
Por lo general, la complejidad cuadrática no se considera lo suficientemente segura contra un atacante (o en el otro extremo, para m, n grandes, lo suficientemente conveniente para los participantes) para aplicaciones criptográficas prácticas del mundo real. Sin embargo, este esquema tiene la distinción de ser uno de los primeros ejemplos de criptografía de clave pública y fue una inspiración para el protocolo de intercambio de claves Diffie-Hellman , que tiene una complejidad mucho mayor, basándose en el problema del logaritmo discreto .
En 2008, Boaz Barak y Mohammad Mahmoody-Ghidary demostraron ( "Los rompecabezas de Merkle son óptimos" ) que este límite cuadrático no se puede mejorar.
Referencias
- Merkle, RC (abril de 1978). "Comunicaciones seguras a través de canales inseguros". Comunicaciones de la ACM . 21 (4): 294–299. CiteSeerX 10.1.1.364.5157 . doi : 10.1145 / 359460.359473 . [pdf ]
enlaces externos
- Ralph Merkle, Secure Communications over Insecure Channels (1974) : Una historia de la idea y su publicación, con una entrevista del año 1995, Editado por Arnd Weber
- Ralph Merkle, propuesta de proyecto de 1974 para CS 244 en UC Berkeley.
- Ralph Merkle, 7 de diciembre de 1975, "Comunicación segura a través de canales inseguros"