Cifradores de mochila de Markle-Hellman
Historia
Merkle-Hellman,
fue uno de los primeros criptosistemas de llave pública y fue inventado por
Ralph Merkle y Martin Hellman en 1978.
Que es?
Merkle-Hellman es un
criptosistema asimétrico, esto significa que para la comunicación, se necesitan
dos llaves: una llave pública y una privada. Otra diferencia con RSA, es que
sirve sólo para cifrado, es decir, la llave pública es usada sólo para cifrar
(no para verificar firma) y la llave privada es usada sólo para descifrar (no
para firmar). De este modo, no se puede usar para tareas de autentificación por
firma electrónica.
El algoritmo de Merkle-Hellman
está basado en el problema de la mochila de decisión (un caso especial del problema de la mochila de
optimización): dados una secuencia de números y un número, determinar si existe
un subconjunto de la secuencia cuya suma dé dicho número. En general, es sabido
que este problema es de clase NP-completo. Sin embargo, si la secuencia de números es
supercreciente, esto es, si cada elemento de la secuencia es mayor que la suma
de todos los anteriores, el problema es "fácil", y es posible resolverlo
en tiempo polinómico con un simple algoritmo voraz.
Generacion de claves
En Merkle-Hellman, las claves
están compuestas por secuencias. La clave pública es una secuencia
"difícil", y la clave privada es una "fácil", o secuencia
de valores supercrecientes, junto con dos números adicionales, un multiplicador
y un módulo, los cuales son usados para convertir la secuencia supercreciente
en una secuencia difícil. Estos mismos números son usados para transformar la
suma de la subsecuencia de la secuencia "difícil" en la suma de la
subsecuencia de la secuencia "fácil", la cual se puede solucionar en
tiempo polinómico.
Cifrado
Para cifrar un mensaje, el
cual debe ser una secuencia de bits de la misma longitud de la secuencia
difícil, se eligen los elementos de la secuencia difícil que correspondan a
bits en 1 del mensaje (mientras que los elementos correspondientes a bits en 0
son descartados). Luego se suman los elementos así elegidos, y el resultado de
esto es el texto cifrado.
En caso que el mensaje no sea
de la misma longitud de la llave, se subdivide en secuencias que tengan esta
longitud y se aplica el mismo procedimiento.
Desifrado
El
descifrado es posible, porque el multiplicador y el módulo usados para
transformar la secuencia supercreciente (la llave privada) y por tanto
"fácil" en la secuencia general (la llave pública) y por tanto
difícil, también pueden ser usados para transformar el texto cifrado
(representado por un número) en la suma de los elementos que conforman la
subsecuencia supercreciente (una subsecuencia de una secuencia supercreciente,
también es supercreciente). Luego, usando un algoritmo voraz, el problema
"fácil" de la mochila puede ser resuelto usando O(n) operaciones, con
lo cual se logra descifrar el mensaje.
Ejemplo:
Es
una cifra a clave pública, basada en la dificultad solucionar el problema de la
mochila con una consecuencia de peso no supercroiss. Se va de la siguiente
observación:
·
El
problema de la mochila es homogéneo: no cambia las soluciones multiplicando (o
dividiendo) todos los pesos Pi y el objetivo T por una misma totalidad p.
Las multiplicaciones pueden efectuarse
módulo una totalidad el Sr. Entonces, aunque la consecuencia de peso inicial es
supercroiss, la nueva consecuencia así obtenida no lo será en general. En la
práctica, se elige m superior a la suma de los pesos iniciales.
Ejemplo.
Va de la consecuencia supercroiss 1,.3,.6. Se hacen todos los cálculos módulo
12. Al multiplicar todos los pesos por 7 se obtiene la consecuencia no
supercroiss 7,.9,.6. Gracias a la propiedad de homogeneidad, se ven que la
misma solución (b1, b2, b3) permite realizar el objetivo T con los pesos
1,.3,.6 y el objetivo Tx7 con los pesos 7,.9, 6. El cuadro siguiente da la
correspondencia entre los objetivos y las soluciones:
Para
calcular un bloque de k bites, se calcula simplemente el peso T resultando del
bolso. Para garantizar que el descifrado con la misma clave es imposible, se
calcula con la consecuencia no supercroiss.
Para
descifrar, se deben determinar los pesos cuya suma realiza el objetivo T. la
idea consiste en corresponder a la consecuencia supercroiss inicial, sin
cambiar la solución. Basta para eso con dividir todos los pesos y el objetivo T
por p.
La
consecuencia no supercroiss constituye la clave pública. La consecuencia
supercroiss inicial, con p y m, forman la clave privada.
Ejemplo de codificación/descifrado
La
clave privada de Bob es [1, 3, 6], con p = 7 y m = 12.
Con
la clave pública [7,.9,.6] proporcionada por Bob, Alice calcula así la cadena
101: T = 7x1 + 9x0 + 6x1 = 13 envía pues el mensaje "13" a Bob.
Para
descifrar el mensaje, Bob utiliza su clave privada (tienen en cuenta que 7 son
su propio opuesto módulo 12), y aplica el algoritmo glouton. Obtiene:
13x7-1
(mod 12) = 91 (mod 12) = 7 (mod 12) = 1x1 + 3x0 + 6x1. El mensaje claro es pues
101.
Más
generalmente, para que p sea inversible módulo m, basta con elegirlo primero
con m.
Es
importante tener en cuenta que un texto calculado con la clave privada no podrá
descifrarse con la clave pública, puesto que no es supercroiss: las dos claves
de la cifra de Merkle-Hellman no pueden permutarse.
No hay comentarios:
Publicar un comentario