En criptografía , los acertijos de Merkle son una de las primeras construcciones 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 mediante el intercambio de mensajes, incluso si no tienen secretos en secreto. común de antemano.
Supongamos que Alice y Bob desean comunicarse. Bob puede enviar un mensaje a Alice de la siguiente manera: primero, crea una gran cantidad de acertijos, cada uno con una dificultad moderada; debe ser posible que Alice resuelva el acertijo 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 ahora tienen una clave común; Alice, porque resolvió un acertijo, y Bob, porque envió el acertijo. Cualquier espía (Eva, digamos) tiene una tarea más difícil: no sabe qué rompecabezas resolvió Alice. Su mejor estrategia es resolver todos los acertijos, pero dado que hay tantos, esto es más costoso computacionalmente para Eve que para Alice.
Tenga en cuenta que Eve, quien escucha a escondidas, puede leer el identificador X enviado (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.
Los parámetros del juego de rompecabezas se pueden elegir para que sea considerablemente más difícil para un intruso descifrar el código que para que las partes se comuniquen, pero los rompecabezas de Merkle no brindan las enormes diferencias cualitativas en dificultad que se requieren para (y definen) la seguridad. en la criptografía moderna.
Suponga que el número de acertijos enviados por Bob es m , y 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 lleva O( mn ) de tiempo. Si m ≈ n , el esfuerzo de Eve tiene una complejidad aproximadamente cuadrática en comparación con Alice y Bob, es decir, su tiempo de cálculo es del orden del cuadrado del de ellos. Por lo tanto, n debe seleccionarse lo suficientemente grande como para que el cálculo siga siendo factible para Alice y Bob mientras supera las capacidades de Eve.
La complejidad cuadrática generalmente no se considera lo suficientemente segura contra un atacante (o en el otro extremo, para m,n grande, 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 y se basa en el problema del logaritmo discreto .