Hispanopedia WikiEn criptografía , el algoritmo de Merkle es una construcción temprana para un criptosistema de clave pública , un protocolo ideado por Ralph Merkle en 1974 y publicado en 1978. Permite que dos partes se pongan de acuerdo sobre un secreto compartido mediante el intercambio de mensajes, incluso si no tienen secretos en común de antemano.
Descripción
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 de dificultad moderada ; Alice debe poder resolverlos con un esfuerzo computacional moderado. Los acertijos están en forma de un mensaje cifrado con una clave desconocida ; la clave debe ser lo suficientemente corta como para permitir un ataque de fuerza bruta . Bob envía todos los acertijos (es decir, los mensajes cifrados) 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é acertijo ha resuelto. Ambas partes ahora tienen una clave común: Alice, porque resolvió un acertijo, y Bob, porque lo envió. Cualquier espía (por ejemplo, Eva) 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 computacionalmente más costoso para Eva que para Alice.
Descripción de alto nivel
- Bob genera 2N 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 para el cifrado simétrico. Por lo tanto, tanto X como Y son únicos para cada mensaje. Todos los mensajes están cifrados de tal manera que un usuario podría realizar un ataque de fuerza bruta contra cada uno, aunque con cierta dificultad. Bob envía todos los mensajes cifrados a Alice.
- Alice recibe todos los mensajes cifrados y elige uno al azar para descifrarlo mediante fuerza bruta. Tras descubrir el identificador X y la clave secreta Y en ese mensaje, cifra el texto sin cifrar con la clave secreta Y y envía ese identificador (en texto plano) junto con el texto cifrado a Bob.
- Bob busca la clave secreta asociada a ese identificador, ya que fue él quien los generó en primer lugar, y descifra el texto cifrado de Alice con esa clave secreta.
Cabe señalar que la espía Eve puede leer el identificador X que Alice envía a Bob (en texto plano), pero, sin descifrar por fuerza bruta la mayoría de los mensajes originales, no tiene forma de relacionarlo con la clave secreta Y que Bob y Alice utilizan actualmente para su comunicación, ya que el valor de X dentro de cada mensaje se generó aleatoriamente.
Análisis de complejidad y seguridad
Los parámetros del juego de rompecabezas pueden elegirse para que resulte considerablemente más difícil para un intruso descifrar el código que para las partes comunicarse, pero los rompecabezas de Merkle no proporcionan las enormes diferencias cualitativas en dificultad que se requieren para (y definen) la seguridad en la criptografía moderna.
Supongamos que Bob envía m acertijos y que tanto Bob como Alice necesitan n pasos de cálculo para resolver uno. En ese caso, ambos pueden deducir una clave de sesión común con una complejidad temporal de O ( m+n ). Eve, en cambio, 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, a la vez que supere las capacidades de Eve.
La complejidad cuadrática generalmente no se considera lo suficientemente segura frente a un atacante (o, en el otro extremo, para valores grandes de m y n, lo suficientemente conveniente para los participantes) para aplicaciones criptográficas prácticas en el mundo real. Sin embargo, este esquema tiene la particularidad de ser uno de los primeros ejemplos de criptografía de clave pública y sirvió de inspiración para el protocolo de intercambio de claves Diffie-Hellman , que tiene una complejidad mucho mayor, ya que se basa en el problema del logaritmo discreto .
En 2008, Boaz Barak y Mohammad Mahmoody-Ghidary demostraron ( "Los rompecabezas de Merkle son óptimos" ) que esta cota cuadrática no se puede mejorar.
Referencias
Enlaces externos
- Ralph Merkle, Comunicaciones seguras sobre canales inseguros (1974) : Historia de la idea y su publicación, con una entrevista del año 1995, editado por Arnd Weber.
- Propuesta de proyecto de Ralph Merkle, 1974, para el curso CS 244 en la Universidad de California en Berkeley.
- Ralph Merkle, 7 de diciembre de 1975, "Comunicación segura a través de canales inseguros"
- Protocolos de acuerdo clave