PROBLEMA TIPO MOCHILA

CIFRADOS TIPO MOCHILA
Están basados en el problema NP- completo de la mochila, y se describen como más característicos los siguientes tipos:
1.- MERKLE-HELLMAN (1978) [MEH 78]
Que se utiliza para secreto, y no para preservar la autenticación de la firma.
2.- GRAHAM-SHAMIR (1984) [SHAM 84]
Que al igual que el anterior se utiliza para secreto, y no permite preservar la autenticación.
Los métodos de la mochila, válidos para proveer a la vez secreto y autenticación tienen el inconveniente de que se resuelven en tiempo polinómico [DENN 83].
Este criptosistema ha caído en desuso debido a que la mayoría de sus implementaciones han sido rotas por criptoanálisis [SHAM 84], no obstante aún existen algunos criptosistemas basados en el que aquí se presenta que todavía son seguros, aunque muy poco utilizados.
Definición: El problema de la mochila tramposa o simple o fácil, puede plantearse en los siguientes términos: sea W={w1, w2, ..., wn } un conjunto finito dado de números enteros, y sea s = wi1 + ... + wit , con i1<...< it, una subsuma de elementos de W. Se trata de determinar el subconjunto {wi1, ..., wit } de W, conocido W y s. El nombre de mochila asignado al problema se debe a que s puede pensarse como la capacidad de una mochila, y los elementos de W como los tamaños de diferentes objetos; se trata entonces de saber si la mochila se puede llenar con un número exacto de objetos y determinar qué objetos son éstos.
Dado que W es finito, también lo es el número de posibles subconjuntos; por tanto el problema se puede resolver, aunque la dificultad estriba en hacerlo de forma eficiente. Conviene señalar que puede haber dos subconjuntos de W con la misma suma, y que para determinados conjuntos W es muy sencillo encontrar la solución. Por ejemplo, si W=(1, 2, 22, 23, ...,2k,...) entonces basta con calcular la expresión de s en base binaria.
Definición: Una sucesión de números enteros w1 < w2 < ... < wk < ... se dice supercreciente o una sucesión de crecimiento rápido, si se verifica que wi+1 > w1 + ...+ wi , para todo i. Si W = {w1, ..., wn } es una parte de una sucesión supercreciente y se conoce la suma s de un subconjunto de W, es fácil determinar dicho subconjunto. Basta considerar el mayor elemento de W menor que s, wit , luego el mayor elementos de W menor que s - wit , wi(t-1) , y así sucesivamente. Es claro que para el problema de la mochila 0 < w1.


ALGORITMO DE MERKLE-HELLMAN (M-H) Y SU SEGURIDAD

a) Algoritmo de Merkle - Hellman
Este método se basa en el problema NP-completo de la mochila de tipo 0-1 o problema de la mochila fácil, y el mayor atractivo que tiene es su fácil implementación en un programa y su gran rapidez, unas 100 veces más rápido que el RSA. También hay que decir que para cifrar bloques de 200 bits (n = 200) en la mochila, almacenar el vector mochila W = (w1 , ..., wn ) requiere del orden de 80 Kb, si consideramos que cada wi es , de media, de 400 bits, mientras que con el RSA necesitaríamos, solamente, 1 Kb para almacenar su clave.
Dado C entero positivo, W = (w1, ..., wn ) un vector con componentes wi enteros positivos para todo i. Se trata de encontrar M = (m1 , ..., mn), mi = 0 ó 1, 1< i < n, Tal que C = W.M ó C = w1 m1 + ... + wn mn
EJEMPLO:
Sea n = 5, C = 14 y W = (l, l0, 5, 22, 3), entonces M = (1,1,0,0,1).
Este problema es NP-completo y se resuelve en un tiempo de magnitud 0(2n/2) que es un tiempo exponencial y crece mucho cuando n se hace grande, lo que lo hace altamente ineficaz de resolver.

Sin embargo, existe el problema de la mochila simple que se resuelve en un tiempo lineal de complejidad 0(n), en el cual los wi son supercrecientes. Lo que implica que mn = 1 si y sólo si C > wn . Y para i = n-l, n-2, ..., l se verifica que:
EJEMPLO:
Sea W = (1, 3, 5, 10, 22). La solución que se obtiene fácilmente es (1,1,0,1,0), para C = 14 del anterior ejemplo.
Un problema de la mochila simple o fácil se puede convertir en una función trampa difícil de resolver sin la información adicional, para ello:
1) Se escoge un vector del problema simple W' = (w1', ..., wn'). Esto permite una solución sencilla de: C'= W'.M .
2) Se elige un entero u tal que: u > 2.wn' > w1' + ... + w n' .
3) Se elige un entero v tal que MCD (u, v) = 1 y el inverso multiplicativo del mismo número v-1 mod u se obtiene de v.v-1 mod u = 1.
4) El vector W' se transforma en el. W = v W' mod u, donde, wi = wi' mod u.
Así, resolver C = W .M es difícil, pero si se conoce la información adicional v -1 y u el problema es más sencillo, pues se puede convertir el problema C = W .M en el C' = W' .M, fácil de resolver. Ya que:
C' = v -1. C mod u
= v -1. W .M. mod u
= v -1. (v. W') . M mod u
= W' .M mod u
= W' . M
El procedimiento de cifrado sería el siguiente:
Sea EA el algoritmo cifrado que utiliza la clave pública A, y DAV el algoritmo de descifrado que utiliza (W', u , v -1 ) la clave privada.
El mensaje inicial se trocea en bloques de n bits (cardinal de W) M = (m1, ..., mn ) y cada bloque se cifra según: C = EAB (M) = W .M .
El mensaje C se descifra calculando: DAV (C) = Algoritmo Simple (v-1 . C mod u, W') = M.

EJEMPLO:
Sea W = (1, 2, 5, 9), u = 20 y v = 7. Entonces v -1 = 3 el vector W se convierte en el W' = v.W ó wi '= v. wi mod u. La clave privada es ((1, 2, 5, 9), 3, 20).
W' = (7.l mod 20, 7.2 mod 20, 7.5 mod 20, 7.9 mod 20) = (7, 14, l 5, 3), esto es la clave pública.
Sea C = 13, el mensaje, que corresponde al vector binario M = (1,1,0,1).
Entonces:
C' = EAB (M) = 7 +14 +3 = 24
DAV (C') = DAV (24)
= Algoritmo Simple (3.24 mod 20, W')
= Algoritmo Simple (12, W')
= 1 + 2 + 9 = 13
EJEMPLO (Otra forma del criptosistema de la mochila):
Sea el conjunto:
{w1 = 20111, w2 = 10201, w3 = 10412, w4 = 20801, w5 = 11611, w6 = 13221}

donde los números wi forman el conjunto de objetos con los cuales llenar la mochila. Estos números han sido tomados de forma que en su posición cuarta y tercera, contadas a partir de la derecha, contienen diferentes potencias de dos (1, 2, 4, 16, 32), mientras que en la primera y segunda contienen dígitos cuya suma, extendida a todos los elementos wi , es menor que 100.
Este conjunto de números puede ser utilizado como clave de un sistema de cifrado de la forma que sigue:
Supongamos que el mensaje a transmitir es M = 101101.
El mensaje cifrado será la suma de los números wi de forma que la posición i-esima del mensaje a transmitir contenga un 1. Es decir, C' = E(m)= w1 + w3 + w4 + w6 = 64545.
Obsérvese que en las columnas cuarta y tercera se encuentra el número 45, que tiene como expansión binaria a 101101, el cual coincide con el mensaje que queríamos transmitir.
Este algoritmo, sin más precauciones, sería roto fácilmente, por eso hay que hablar de la seguridad del criptosistema de la mochila que como veremos no es tan maravillosa como se podría esperar en un principio.
EJEMPLO (Otra forma del criptosistema de la mochila):
Sea {2, 3, 7, 15, 31, 62, ...} una sucesión supercreciente. Dado que vamos a utilizar el alfabeto de 26 letras (La "ñ" no se suele contar) codificado con 0-25 y como 24 = 16 < 26 < 32 = 25, el conjunto W tendrá sólo cinco elementos, pues las letras en base binaria tendrán, como máximo, cinco bits. Así pues, W = {2, 3, 7, 15, 31} es suficiente. Por otra parte, 2 + 3 + 7 + 15 + 31 = 58, y podemos considerar u = 61 > 58. Si elegimos v = 17, primo con 61, su inverso módulo 61 es v-1 = 18. La clave pública del usuario B, por ejemplo, será W' = v .W = {34, 51, 58, 11, 39}, mientras que su clave privada es v-1 = 18, junto con v = 17, u = 61 y W.
Supongamos que el usuario A quiere mandar el mensaje "HOLA" al usuario B. A codifica el mensaje y luego lo encripta de la siguiente manera:
H: 7=1+2.3=1+2(1+2)=1+2+22 =(00111)2. -> 34 + 51 + 58 = 143,
O : 14= 2.7 = 2(1 + 2 + 22) = 2 + 22 + 23 = (01110)2. -> 51 + 58 + 11=120,
L: 11 = 1 + 2.5 = 1 + 2(1 + 22) = 1 + 2 + 23 = (01011) 2 . -> 34 + 51 + 11 = 96,
A : 0 = 0 = (00000) 2 . -> 0.
Por tanto, el mensaje a enviar a B es:
C' = (143, 120, 96, 0) mod 61 = (21, 59, 35, 0).
Para recuperar el mensaje recibido, B utiliza la sucesión supercreciente W el inverso v-1 = 18 y lleva a cabo las siguientes operaciones:
v-1.C' = (12, 25, 20, 0)
12 = 7 + 3 + 2 ~ (00111) 2 = 1 + 2 + 22 = 7 : H
25 = 15 + 7 + 3 ~ (01110) 2 = 2 + 22 + 23 = 14 : O
20 = 15 + 3 + 2 ~ (01011) 2 = 1 + 2 + 23 = 11: L
0 = 0 ~ (00000) 2 = 0 : A


b) Seguridad del Algoritmo M-H
Los autores sugieren que la longitud de n sea 100 dígitos. Schroeppel y Shamir [SCHR 79] han desarrollado un algoritmo para resolver problemas de la mochila de este tamaño con ordenes de complejidad en tiempo y espacio:
T = 0(2n/2) y S = 0(2n/4)
Para n = 100, un procesador hallaría la solución en 11.574 días y 1000 procesadores en 12 días aproximadamente.
Si n = 200, el algoritmo es ineficaz.
Los autores aconsejan que se tomen varios pares de (u, v) e iterarlos en la transformación W' = v. W mod u para que el sistema no sea vulnerable cuando se conoce u (*), pero al parecer este método también es inseguro.
Pohling [POHL78] ha demostrado que si el problema de la mochila tiene subconjuntos parcialmente ordenados (simples), puede ser factible encontrar una solución en un tiempo menor. La probabilidad de que esto ocurra no parece muy alta.
En 1983, este esquema de iteraciones del sistema de Merkle-Hellman (*) sufrió un ataque de Adleman [ADL 83] que proporcionó la evidencia de su inseguridad. Luego, Lagarias y Odlyzko [LA0 83] demostraron que cualquier criptosistema basado en una mochila de baja densidad (mochila (w1, w2, ..., wn ) tal que el número n/log2 (wn ) es pequeño), se puede romper en tiempo polinomial, en particular, este resultado se puede aplicar al sistema de Merkle-Hellman. La idea de su ataque se basa en la reconstrucción de los vectores de la mochila fácil a partir de los vectores de mochila difícil, rompiendo así el sistema.
A partir de la misma idea que sirvió como base al sistema de Merkle-Hellman, se han creado nuevas variantes, conocida con el nombre de sistemas de la mochila.
En 1982, Shamir [SHA 82] diseñó un algoritmo que resuelve en tiempo polinomial el tipo de problema de la mochila que se presenta en el sistema de Merkle-Hellman.
El ataque de Shamir procede analizando los números w1 ,w2 , ..., wn , que forman la clave de cifrado de este sistema para intentar encontrar un par de números enteros N y M tales que el conjunto { M .wi mod N } constituya una mochila fácil cuya suma sea menor que N. Para ello, es necesario suponer que el orden de los coeficientes wi corresponde al orden creciente de los coeficientes de la mochila fácil original, y hay que calcular una serie de intervalos cada vez más pequeños, donde se sabe que están cada uno de los números wi.
El procedimiento es válido siempre que la longitud de los números de la mochila fácil no sea mayor de l00 bits, pues en ese caso la consecución de los intervalos y su posterior reducción se hace infactible.
Otro punto débil del ataque está en la suposición de que el orden de los { wi }i corresponde al de la mochila fácil, pues éste es un dato que no se suele tener, y si no se tiene hay que probar todas las posibles combinaciones.
En general, el cálculo de los subintervalos se realiza resolviendo una serie de inecuaciones que son resolubles en tiempo polinomial. Una vez obtenido el intervalo final [e1 , e2 ], hay que encontrar una solución a otro problema de programación entera, consistente en obtener la fracción M/N tal que ei < M/N <= e2 Knuth ha desarrollado en [KNU 69] algunos algoritmos eficientes que resuelven este problema. A partir de estos cocientes se obtienen algunos pares (M, N) de los que se descartan aquellos tales que { M .ai mod N } no es una mochila fácil.
Muchos de estos sistemas han sido criptoanalizados utilizando herramientas del área de la aproximación diofántica [BRO 88]. Sin embargo, no todos estos sistemas han caído. Existen todavía unos pocos que resisten los ataques, como los sistemas iterados y el sistema de Chor-Rivest.
La búsqueda de sistemas de la mochila seguros continúa hoy en día por dos motivos fundamentales: se obtienen grandes velocidades de los cifrados y descifrados, y representan una alternativa elegante a los sistemas simétricos y al propio RSA. Ambas características se deben a la simplicidad de su diseño.


ALGORITMO DE GRAHAM - SHAMIR.
Este algoritmo presenta la ventaja frente al de M-H en que se disminuye el tamaño del vector en la función trampa tipo mochila a costa de aumentar el tamaño de cada componente de dicho vector.
El vector del problema simple es A' = (a'1,..., a'n ) donde cada a'j = (R j, I j, S j).
Siendo a su vez: R j y S j cadenas aleatorias de bits e I j una cadena de n bits tal que el bit j = 1 y los n-l restantes son cero. Cada cadena aleatoria S j tiene log 2 n ceros en las cifras de mayor orden, de tal forma que no se produce desbordamiento en el área de las I j 's , al operar para el cálculo de C'.
Entonces, C'= A' .M tiene representación binaria de la forma C' = (R, M, S) donde:
;
El vector de cadenas de bits ((In , Sn ), ..., (I1, S1 )), es decir, los elementos a'j listados en sentido contrario, sin las Rj's, es un vector del problema simple. Las Rj's se añaden para ocultar esta simplicidad.
Este problema tipo mochila es más simple que el de M-H, Ya que M puede extraerse directamente de la representación binaria de C'.
El vector A' del problema simple se convierte en el vector A del problema difícil al igual que en el M-H, es decir, tomando u y w y calculando A = w A' mod u , de igual forma:
C = EAB (M) = A . M.
C se descifra resolviendo
C' = w -1 . C mod u
y extrayendo de C' los bits que representan M.
Shamir y Zippel [SHAM 8O] consideran esta variante más segura, más rápida y simple de implantar que el esquema de M-H.
Ejemplo:
Sea n=5 A' se define por:

Sea M=(0, 1, 0, 0, 1) Entonces:
C' = A'. M = a'2 + a'5 = (R2 + R5 , I2 + I5 , S2 + S5 ) = (001111, 01001, 000011).
Siendo 01001 el mensaje M.

CRIPTOANALISIS DE M-H
Se ha dicho antes que el criptosistema de la mochila se puede romper facilmente (en tiempo polinomial), algunos de estos criptoanálisis fueron presentado por Shamir [SHAM 82], por Lagarias y Odlyzko [LAGA 85] y por Brickell [BRIC 83].
Cada uno de ellos es suficiente para romper el criptosistema de la mochila tipo M-H.

Ataque de Shamir
La clave pública del criptosistema de M-H es un conjunto de n números W = {w1 , ..., wn} un mensaje m = m1 , ..., mn es cifrado por C = m1 w1 + ... + mn wn . Supongamos que un atacante conoce el conjunto W y también C, cosa que no es difícil pues W es la clave pública y C puede ser interceptado pues el canal es inseguro.
El ataque de Shamir analizará los números de W e intentará encontar un par N y M tales que el conjunto {M wi mod N}i sea una sucesión supercreciente y que tenga suma total menor que N (+). Una vez que hemos encontrado ese par de números puede ocurrir que no sea el par original de la clave secreta, entonces ese par de números sería suficiente para encontrar los verdaderos pares y resolver el problema de la mochila en tiempo polinomial, así pues sólo necesitamos que exista un par de números que verifiquen (+), pero esto está garantizado pues es la base del M-H.
Expliquemos el ataque con un ejemplo.
W = {467, 355, 131, 318, 113, 21, 135, 215} esta es la clave pública.
Nosotros queremos encontrar un par de numeros N y M que cumplan (+), es decir, tales que el conjunto {M wi mod N}i sea una sucesión supercreciente y que tenga suma total menor que N.
Supongamos, que hemos descubierto, por el método que sea, un par de números M y N de posibles valores de la transformación de la clave secreta a la pública, entonces podemos encontrar los verdaderos valores de la clave secreta, veamos como.
Si encontramos M, N entonces M w 1' mod N tiene que ser menor que 2-7 N, pues la sucesión de la clave secreta es una sucesión supercreciente, (wi+1 > w 1 + ... + w i , entonces, N> w 1 + ... + w n > w1 + ... + w n-1 + (w 1 + ... + w n-1) = 2 (w 1 + ... + w n-1 ) > ... ...> 2n-1 w 1 ).
Sea y = f(m) = 467 M mod N, (estamos buscando w1).
Los ceros de esta función son: M = N/467, 2 N/467, ..., 466 N/467.

Además, para el valor de y > 2-7 N no puede darse ningún w 1, lo que implica que M pertenece al subintervalo I1 = [N/467, N/467 + 2-7 N/467] luego tenemos una familia de 466 subintervalos pequeños de [0, N] de la forma:
Ip = [p N/467, p N/467 + 2-7 N/467] y M pertenece a Ip para algún p con 1 < p < 466.
Tomamos, ahora w2' = 355 y razonamos del mismo modo, entonces
M w2' = M 355 mod N < 2-6 N, (estamos buscando w2).
Y encontramos otros intervalos Iq = [q N/355, q N/355 + 2-6 N/355] y también se verifica que M pertenece a Iq para algún q entre 1 y 354.
Luego M pertenece a las interseccciones posibles de los Ip con los Iq.
Ahora se tomaría w3', ... y se razonaría de la misma manera dando al final unos intervalos para cada una de los elementos de W' y verificandose que M pertenece a la intersección de ellos.
Si lo hacemos hasta w4' tenemos sólo dos subintervalos (las otras posibles conbinaciones se hacen el vacio), que dividiendolos por N son:
[0.053533190578, 0.053565140845]
[0.107066381156, 0.107086267606]
y en estos subintervalos es donde está la verdadera M/N de la transformación de la clave secreta a la pública, como además N <= 2 max wi', sólo tenemos un número pequeños de números para probar (para este ejemplo hay 21 pares), sólo pongo unos cuantos:

se toman cada uno de estos pares y se comprueba que verifican (+).

Por ejemplo:
Para (25,467) la sucesión es: 0, 2, 6, 11, 23, 58, 106, 238; no es supercreciente.
Para (50,467) la sucesión es: 0, 4, 12, 22, 46, 116, 212, 9; no es supercreciente.
Para (53,990) la sucesión es: 1, 5, 13, 24, 49, 123, 225, 505 que sí es supercreciente.
De hecho sólo los pares (28, 523) y (53, 990) dan sucesiones supercrecientes para el problema de la mochila.
Con lo cual sólo tenemos dos posibles mensajes en claro y discernir entre uno de ellos es factible.

Bibliografia

CRIPTOSISTEMA DE LA MOCHILA, Lázaro A. Escudero Ferrer
http://www.tierradelazaro.com/cripto/mochila.htm

Referencia.
departamentos.unican.es/macc/ personal/profesores/castillo/Libro/Chap2.pdf