El criptosistema de mochila Merkle-Hellman fue uno de los primeros criptosistemas de clave pública . Fue publicado por Ralph Merkle y Martin Hellman en 1978. Adi Shamir publicó un ataque de tiempo polinomial en 1984. Como resultado, el criptosistema ahora se considera inseguro. [1] : 465 [2] : 190
Historia
El concepto de criptografía de clave pública fue introducido por Whitfield Diffie y Martin Hellman en 1976. [3] En ese momento solo propusieron el concepto general de una "función de trampilla", una función que es computacionalmente imposible de calcular sin alguna "trampilla" secreta información, pero aún no habían encontrado un ejemplo práctico de tal función. Luego, otros investigadores propusieron varios criptosistemas específicos de clave pública durante los próximos años, como RSA en 1977 y Merkle-Hellman en 1978. [4]
Descripción
Merkle-Hellman es un criptosistema de clave pública, lo que significa que se utilizan dos claves, una clave pública para el cifrado y una clave privada para el descifrado. Se basa en el problema de la suma de subconjuntos (un caso especial del problema de la mochila ). [5] El problema es el siguiente: dado un conjunto de números enteros y un entero , encuentra un subconjunto de que suma a . En general, se sabe que este problema es NP-completo . Sin embargo, sies supercreciente , lo que significa que cada elemento del conjunto es mayor que la suma de todos los números del conjunto menor que él, el problema es "fácil" y se puede resolver en tiempo polinomial con un algoritmo codicioso simple .
En Merkle-Hellman, descifrar un mensaje requiere resolver un problema de mochila aparentemente "difícil". La clave privada contiene una lista de números cada vez mayor, y la clave pública contiene una lista de números que no aumenta demasiado , que en realidad es una versión "disfrazada" de . La clave privada también contiene información "trampa" que se puede utilizar para transformar un problema de mochila dura utilizando en un sencillo problema de mochila usando .
A diferencia de otros criptosistemas de clave pública como RSA , las dos claves de Merkle-Hellman no son intercambiables; la clave privada no se puede utilizar para el cifrado. Por lo tanto, Merkle-Hellman no se puede usar directamente para la autenticación mediante firma criptográfica , aunque Shamir publicó una variante que se puede usar para firmar. [6]
Generación de claves
1. Elija un tamaño de bloque . Enteros hasta Los bits de longitud se pueden cifrar con esta clave.
2. Elija una secuencia aleatoria de superincremento de enteros positivos
- El requisito de superincremento significa que , por .
3. Elija un número entero aleatorio tal que
4. Elija un número entero aleatorio tal que (es decir, y son coprime ).
5. Calcula la secuencia
- dónde .
La clave pública es y la clave privada es .
Cifrado
Dejar frijol -mensaje de bits que consta de bits , con el bit de mayor orden. Seleccione cada para cual es distinto de cero y súmalos. Equivalentemente, calcule
- .
El texto cifrado es .
Descifrado
Para descifrar un texto cifrado , debemos encontrar el subconjunto de que suma a . Hacemos esto transformando el problema en uno de encontrar un subconjunto de. Ese problema se puede resolver en tiempo polinomial ya que es supercreciente.
1. Calcule el inverso modular de modulo utilizando el algoritmo euclidiano extendido . La inversa existirá ya que es coprime a .
- El cálculo de es independiente del mensaje y se puede hacer solo una vez cuando se genera la clave privada.
2. Calcular
3. Resuelva el problema de la suma del subconjunto para usando la secuencia de superincremento , por el simple algoritmo codicioso que se describe a continuación. Dejar ser la lista resultante de índices de los elementos de cual suma a . (Es decir,.)
4. Construye el mensaje con un 1 en cada uno posición de bit y un 0 en todas las demás posiciones de bit:
Resolver el problema de la suma de subconjuntos
Este simple algoritmo codicioso encuentra el subconjunto de una secuencia supercreciente que suma a , en tiempo polinomial:
- 1. Inicializar a una lista vacía.
- 2. Encuentra el elemento más grande en que es menor o igual a , decir .
- 3. Restar: .
- 4. Adjuntar a la lista .
- 5. Si es mayor que cero, vuelva al paso 2.
Ejemplo
Generación de claves
Cree una clave para cifrar números de 8 bits mediante la creación de una secuencia supercreciente aleatoria de 8 valores:
La suma de estos es 706, así que seleccione un valor mayor para :
- .
Escoger ser coprime a :
- .
Construye la clave pública multiplicando cada elemento en por modulo :
Por eso .
Cifrado
Deje que el mensaje de 8 bits sea . Multiplicamos cada bit por el número correspondiente en y agregue los resultados:
0 * 295+ 1 * 592+ 1 * 301+ 0 * 14+ 0 * 28+ 0 * 353+ 0 * 120+ 1 * 236 = 1129
El texto cifrado es 1129.
Descifrado
Para descifrar 1129, primero use el algoritmo euclidiano extendido para encontrar el inverso modular de modificación :
- .
Calcular .
Utilice el algoritmo codicioso para descomponer 372 en una suma de valores:
Por lo tanto , y la lista de índices es . El mensaje ahora se puede calcular como
- .
Criptoanálisis
En 1984 Adi Shamir publicó un ataque al criptosistema Merkle-Hellman que puede descifrar mensajes cifrados en tiempo polinomial sin utilizar la clave privada. [7] El ataque analiza la clave pública. y busca un par de números y tal que es una secuencia supercreciente. La El par encontrado por el ataque puede no ser igual a en la clave privada, pero al igual que ese par, se puede usar para transformar un problema de mochila dura usando en un problema fácil usando una secuencia de superincremento. El ataque opera únicamente en la clave pública; no es necesario el acceso a los mensajes cifrados.
Referencias
- ^ Schneier, Bruce (1996). Criptografía aplicada . Nueva York: John Wiley & Sons. ISBN 0-471-12845-7.
- ^ Stinson, Douglas R. (1995). Criptografía: teoría y práctica . Boca Ratón: CRC Press. ISBN 0-8493-8521-0.
- ^ Whitfield Diffie; Martin Hellman (1976). "Nuevas direcciones en criptografía". Transacciones IEEE sobre teoría de la información . 22 (6): 644. CiteSeerX 10.1.1.37.9720 . doi : 10.1109 / TIT.1976.1055638 .
- ^ Merkle, Ralph; Hellman, Martin (1978). "Ocultar información y firmas en mochilas de trampilla". Transacciones IEEE sobre teoría de la información . 24 (5): 525–530. doi : 10.1109 / TIT.1978.1055927 .
- ^ Cherowitzo, William (2 de marzo de 2002). "Criptosistema de mochila Merkle-Hellman" . Math 5410 - Criptología moderna . Consultado el 18 de agosto de 2019 .
- ^ Shamir, Adi (julio de 1978). "Un plan de firmas rápido". Memorando Técnico del Laboratorio de Informática del MIT . 79 (MIT / LCS / TM – 107): 15240. Código Bibliográfico : 1978STIN ... 7915240S .
- ^ Shamir, Adi (1984). "Un algoritmo de tiempo polinomial para romper el criptosistema básico Merkle - Hellman". Transacciones IEEE sobre teoría de la información . 30 (5): 699–704. doi : 10.1109 / SFCS.1982.5 .