Criptosistemas de Llave Pública

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