El primero cryptosyst a clave pública, que fue propuesto por Rafael Merkle (fotografía de izquierda) y Martin Hellman en 1978, se basa en el problema de la mochila (Knapsack problem en inglés). No se utiliza actualmente ya puesto que esta cifra, así como de numerosas alternativas, se rompió a principios de los años 80 por Adi Shamir.
El problema de la mochila
consiste en amontonar objetos en un bolso, para alcanzar (si es posible) un
peso total fijado. Más formalmente, 'danse de los pesos enteros P1..., Pn y y
un objetivo T, se trata de encontrar b1..., bn, valiendo 0 o 1, como
T = b1P1 + b2P2+... + bnPn
Si la consecuencia de los pesos
Pk es supercroiss (cada peso es estrictamente superior a la suma de todos los
precedentes), entonces existe un método de Resolución simple (algoritmo
glouton):
Algoritmo glouton
Para I = n a 1 hace
Si
bi = 1
si no
bi = 0
Si T = 0 entonces {b1..., bn} es solución si no, no hay solución.
Compruebe que con la consecuencia
de peso supercroiss P1= 2, P2= 3, P3= 6, P4= 12 y T=15 obtiene la solución b1=
0, b2= 1, b3= 0, b4= 1.
Al contrario, si la consecuencia
de los pesos no es supercroiss, el único algoritmo conocido consiste en
intentar sucesivamente todas las soluciones (b1, b2..., bn) posibles. Si la
consecuencia es suficientemente larga, es un algoritmo impracticable.
La cifra de Merkle-Hellman
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:
T Tx7 b1, b2, b3
0 0 0, 0,.0
1 7 1, 0,.0
3 9 0, 1,.0
4 4 1, 1,.0
6 6 0, 0,.1
7 1 1, 0,.1
9 3 0, 1,.1
10 10 1, 1,.1
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.
Primer 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.
Segundo ejemplo de
codificación/déchifrement
Al utilizar 5 bites, se pueden
cifrar 25 = 32 caracteres. Supongamos que se utiliza la tabla de los 30 caracteres
siguientes (este cuadro les recuerda quizá el alfabeto bilit de Bacon):
La clave privada de Bob es [3, 4,
9, 19, 38, 77], con p = 27 y m = 155. Puede ahora calcular la clave pública con
la cual Alice calculará su mensaje: [ 3x27 (mod 155), 4x27 (mod 155), 9x27 (mod
155), 19x27 (mod 155), 38x27 (mod 155), 77x27 (mod 155) ], lo que da [81, 108,
88, 48, 96, 64].
Alice quiere transmitir la
palabra "niño" a Bob. Deberá pues, refiriéndose a la tabla aquí
arriba, calcular la cadena 00001.00000.00001 11000. como la clave pública de
Bob implica 6 números, ella deberá a continuación agrupar estos bites por
paquetes de 6, y si es preciso añadir bites aleatorios para obtener un número
de bites múltiple el 6: 000010.000000.001110.001101
El primer bloque de 6 bites se
calculará: 81x0 + 108x0 + 88x0 + 48x0 + 96x1 + 64x0 = 96.
El segundo bloque de 6 bites se
calculará: 81x0 + 108x0 + 88x0 + 48x0 + 96x0 + 64x0 = 0.
El tercer bloque de 6 bites se
calculará: 81x0 + 108x0 + 88x1 + 48x1 + 96x1 + 64x0 = 232.
El cuarto bloque de 6 bites se
calculará: 81x0 + 108x0 + 88x1 + 48x1 + 96x0 + 64x1 = 200.
El mensaje codificado es pues: [
96,.0,.232,.200 ]
Para descifrar, Bob calcula en
primer lugarel revés módulo 155 27, que vale 23. Utiliza a continuación su
clave privada y aplica el algoritmo glouton. Obtiene entonces:
96x23 (módulo 155) = 2208 (módulo
155) = 38 = 000010.
0x23 (módulo 155) = 0 (módulo
155) = 0 = 000000.
232x23 (módulo 155) = 5336
(módulo 155) = 66 = 9 + 19 + 38 = 001110.
200x23 (módulo 155) = 4600
(módulo 155) = 105 = 9 + 19 + 77 = 001101.
El mensaje descifrado es pues [
000010,.000000,.001110,.001101 ], lo que es el mensaje bien que había enviado
Alice.
Para encontrar la palabra, Bob no
tiene ya que a agrupar los bites por paquetes de 5 y consultar el cuadro de
conversión.
Es importante que el número de
bites por paquete sea diferente de la longitud de la clave. En efecto, si no
era el caso, se podría impugnar el texto calculado por un análisis de las
frecuencias, ya que cada carta sería calculada por el mismo número.
Queda claro que más la clave es
larga más, el mensaje será difícil de descifrar. En la práctica, se utilizan al
menos 250 números en la clave y se elige el módulo m para para tener una
longitud incluida entre 100 y 200 bites.
Obtenido de: http://www.tierradelazaro.com/cripto/mochila.htm
http://serdis.dis.ulpgc.es/~ii-cript/FICHEROS%20WEB/criptografia%20moderna/cifra%20Merkle-Hellman_files/voila_data_002/voila_data_002/voila_002.htm
Obtenido de: http://www.tierradelazaro.com/cripto/mochila.htm
http://serdis.dis.ulpgc.es/~ii-cript/FICHEROS%20WEB/criptografia%20moderna/cifra%20Merkle-Hellman_files/voila_data_002/voila_data_002/voila_002.htm
No hay comentarios.:
Publicar un comentario