Los criptosistemas de la mochila están basados en el problema NP-completo de la mochila y se describen los siguientes tipos como los más característicos:

1. MERKLE-HELLMAN (1978) [MEH 78] Que se utiliza para ocultar mensajes y no para preservar la autenticación de la firma.
2. GRAHAM-SHAMIR (1984) [SHAM 84] Al igual que el anterior se utiliza para ocultar mensajes y no permite preservar la autenticación.

Los sistemas criptográficos basados en el problema de la mochila y válidos para ocultar el mensajes y proveer a la vez de 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 mochila simple o mochila fácil, puede plantearse en los siguientes términos: sea W={w₁, w₂, …, w_n } un conjunto finito dado de números enteros, y sea s = w_i1 + … + w_it , con i1<…< it, una subsuma de elementos de W. Se trata de determinar el subconjunto U={w_i1, …, w_it } 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 en tiempo finito, aunque la dificultad estriba en hacerlo de forma eficiente, es decir, en un tiempo razonable.

Ejemplo: Si tenemos que W={1, 3, 4, 5, 7, 10, 12, 15, 21, 26} y un subconjunto de él U={3, 4, 7, 10, 21, 26} cuya suma es s=71, conocido W y s resulta complicado determinar U.

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, 2², 2³, …,2^k,…) entonces basta con calcular la expresión de s en base binaria.

Ejemplo: Si tenemos que W={1, 2, 4, 8, 16} y s=12, como 12 en base 2 es 01100, concluimos que el subconjunto que buscamos es {4, 8}.

Definición: Una sucesión de números enteros w₁ < w₂ < … < w_k < … se dice supercreciente o una sucesión de crecimiento rápido, si se verifica que w_i+1 > w1 + …+ w_i , para todo i. Si W = {w₁, …, w_n } 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, w_it , luego el mayor elementos de W menor que s – w_it , w_i(t-1) , y así sucesivamente. Es claro que para el problema de la mochila 0 < w₁.

Ejemplo: W={1, 2, 3, 6, 12, 25, 53}, se puede comprobar que w_i+1 > w1 + …+ w_i , para todo i y por tanto la serie es supercreciente, elegimos el subconjunto U={2, 6, 12, 53} que tiene por suma s=73. Aplicamos el resultado anterior y tenemos que 73 – 53 = 20 > 0, por tanto el 53 es parte del subconjunto, 20 – 25 = -5 < 0, por tanto 25 no es parte de U, 20 – 12 = 8 > 0, por tanto 12 es parte del subconjunto, 8 – 6 = 2 > 0, por tanto 6 es parte de U y por último 2 también es parte del subconjunto. Hemos determinado el subconjunto U={2, 6, 12, 53} fácilmente gracias a la propiedad de supercrecimiento.

Algoritmo de Merkle-Hellman (M-H) y su seguridad

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 su mayor atractivo 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 el sistema de la mochila se tiene que almacenar el vector mochila W = (w₁ , …, w_n ) y requiere del orden de 80 Kb, si consideramos que cada w_i es, de media, de 400 bits, mientras que con el RSA necesitaríamos, solamente, 1 Kb para almacenar su clave.

Dado C un entero positivo, W = (w₁, …, w_n ) un vector con componentes w_i enteros positivos para todo i. Se trata de encontrar M = (m₁ , …, m_n), m_i = 0 ó 1, 1< i < n, Tal que C = M·W ó C = m₁ w₁ + … + m_n w_n.

Ejemplo:
Sea n = 5, C = 14 y W = (l, 10, 5, 22, 3), entonces M = (1,1,0,0,1).

Este problema es NP-completo y se resuelve en un tiempo de magnitud 0(2^n/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 w_i son supercrecientes. Lo que implica que m_n = 1 si y sólo si C > w_n . 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 según hemos visto en el anterior ejemplo. Fíjense que el vector W lo hemos reordenado y de esta forma una serie supercreciente.

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’ = (w₁‘, …, w_n‘). Esto permite una solución sencilla de: C’= M·W’ .
2) Se elige un entero u tal que: u > 2 w_n‘ > w₁‘ + … + 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, w_i = w_i‘ mod u.

Así, resolver C = M·W 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 = M·W en el C’ = M·W’, fácil de resolver. Ya que:

C’ = v^-1 ·C mod u
= v^-1· M·W mod u
= v^-1· M·(v· W’) mod u
= M ·v^-1(v· W’) mod u
= M ·W’ mod u
= M ·W’

El algoritmo de cifrado sería el siguiente:
Sea E el algoritmo cifrado que utiliza la clave pública W’, y D el algoritmo de descifrado que utiliza (W, u, v^-1 ) la clave privada.

El mensaje inicial se trocea en bloques de n bits que es el cardinal de W y de W’ y cada bloque M = (m₁, …, m_n ) se cifra según: C = E (M) = M·W’ .

El mensaje C se descifra calculando: D (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 ó w_i ‘= v. w_i mod u. W’ = (7·l mod 20, 7·2 mod 20, 7·5 mod 20, 7·9 mod 20) = (7, 14, 15, 3), ésto es la clave pública.

La clave privada es ((1, 2, 5, 9), 20, 3).
Sea el bloque del mensaje que queremos ocultar M = (1,0,1,1). Para cifrarlo hacemos C = E (M)= M·W’ =(1,0,1,1)·(7, 14, 15, 3) = 7 + 15 + 3 = 25. Y 25 es el número que transmitimos por el canal inseguro.

Para descifrarlo hacemos:

D (C’) = D (25)
= Algoritmo Simple (3·25 mod 20, W)
= Algoritmo Simple (15, (1, 2, 5, 9))

Que es fácil de determinar pues 15 = 1 + 5 + 9, que corresponde a M = (1,0,1,1).

Ejemplo (Otra forma del criptosistema de la mochila):
Sea el conjunto: {w₁ = 20111, w₂ = 10201, w₃ = 10412, w₄ = 20801, w₅ = 11611, w₆ = 13221} donde los números w_i forman el conjunto de objetos con los cuales llenar la mochila. Estos números han sido tomados de forma que en su posición tercera y cuarta, contadas a partir de la derecha, contienen diferentes potencias de dos (01, 02, 04, 16, 32), mientras que en la primera y segunda contienen dígitos cuya suma, extendida a todos los elementos w_i , es menor que 100. 11 + 01 + 12 + 01 + 11 + 21 = 57 < 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 w_i de forma que la posición i-esima del mensaje a transmitir contenga un 1. Es decir, C’ = E(M)= w₁ + w₃ + w₄ + w₆ = 64545.

Obsérvese que en las columnas tercera y cuarta desde la derecha se encuentra el número 45, que tiene como expresió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 los números del 0 al 25 y como 2⁴ = 16 < 26 < 32 = 2⁵, 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 como base del módulo de la clave privada. Si elegimos v = 17, primo con 61, su inverso módulo 61 es v^-1 = 18. La clave pública del usuario B, será W’ = v ·W = {34, 51, 58, 11, 39}, mientras que su clave privada es (W, u, v^-1) = ({2, 3, 7, 15, 31}, 61, 18).

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+2² =(00111)₂. -> 34 + 51 + 58 = 143,

O : 14= 2·7 = 2(1 + 2 + 2²) = 2 + 2² + 2³ = (01110)₂. -> 51 + 58 + 11 = 120,

L: 11 = 1 + 2·5 = 1 + 2(1 + 2²) = 1 + 2 + 2³ = (01011)₂ . -> 34 + 51 + 11 = 96,

A : 0 = 0 = (00000)₂ . -> 0.

Por tanto, el mensaje a enviar por A a través de un canal inseguro a B es:

C’ = (143, 120, 96, 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)₂ = 1 + 2 + 2² = 7 -> H

25 = 15 + 7 + 3 ~ (01110)₂ = 2 + 2² + 2³ = 14 -> O

20 = 15 + 3 + 2 ~ (01011)₂ = 1 + 2 + 23 = 11-> L

0 = 0 ~ (00000)₂ = 0 -> A

De modo que B recibe el mensaje “HOLA”.
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(2^n/2) y S = 0(2^n/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 (w₁, w₂, …, w_n ) tal que el número n/log₂ (w_n ) 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 w₁ ,w₂ , …, w_n , 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 .w_i mod N } constituya una mochila fácil cuya suma sea menor que N. Para ello, es necesario suponer que el orden de los coeficientes w_i 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 w_i.

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 { w_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 [e₁ , e₂ ], hay que encontrar una solución a otro problema de programación entera, consistente en obtener la fracción M/N tal que e_i < M/N <= e₂ . 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 .a_i 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’₁,…, 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₂ 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 ((I_n , S_n ), …, (I₁, S₁ )), es decir, los elementos a’_j listados en sentido contrario, sin las R_j‘s, es un vector del problema simple. Las R_j‘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 = E (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’₂ + a’₅ = (R₂ + R₅ , I₂ + I₅ , S₂ + S₅ ) = (001111, 01001, 000011).

Siendo 01001 el mensaje M.

Criptoanálisis 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 = {w₁ , …, w_n} un mensaje m = m₁ , …, m_n es cifrado por C = m₁ w₁ + … + m_n w_n . 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· w_i 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 ésto 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 números N y M que cumplan (+), es decir, tales que el conjunto {M· w_i 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₁‘ mod N tiene que ser menor que 2^-7 N, pues la sucesión de la clave secreta es una sucesión supercreciente, (w_i+1 > w₁ + … + w_i , entonces, N > w₁ + … + w_n > w₁ + … + w_n-1 + (w₁ + … + w_n-1) = 2 (w₁ + … + w_n-1 ) > … … > 2^n-1 w₁ ).

Sea y = f(m) = 467· M mod N, (estamos buscando w₁).

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₁, lo que implica que M pertenece al subintervalo I₁ = [N/467, N/467 + 2^-7 N/467] luego tenemos una familia de 466 subintervalos pequeños de [0, N] de la forma:

I_p = [p N/467, p N/467 + 2^-7 N/467] y M pertenece a I_p para algún p con 1 < p < 466.

Tomamos, ahora w₂‘ = 355 y razonamos del mismo modo, entonces

M w₂‘ = M· 355 mod N < 2^-6 N, (estamos buscando w₂).

Y encontramos otros intervalos I_q = [q N/355, q N/355 + 2^-6 N/355] y también se verifica que M pertenece a I_q para algún q entre 1 y 354.

Luego M pertenece a las intersecciones posibles de los I_p con los I_q.

Ahora se tomaría w₃‘, … y se razonaría de la misma manera dando al final unos intervalos para cada una de los elementos de W’ y verificándose que M pertenece a la intersección de ellos.

Si lo hacemos hasta w₄‘ tenemos sólo dos subintervalos (las otras posibles combinaciones se hacen el vacío), que dividiéndolos 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 w_i‘, 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.

APENDICE: Algunos Algoritmos y programas.

Algoritmo de la mochila fácil.
Paso 1. Hacer W = N y j = n.

Paso 2. Hacer e_i = 0 para todo i en orden decreciente hasta encontrar el primer i = i₀ tal que e_i0 <= W, entonces hacer e_i0 = 1.

Paso 3. Dejar de considerar el item e_i reemplazando W por W-e_i0 y hacer j = i₀.

Si W = 0 PARAR, la solución viene dada por los items tales que e_i = 1.
Si W>0 y alguno de los e_i restantes es menor que W, volver al paso 2.
Si W>0 y todos los e_i restantes son mayores que W, entonces PARAR, no existe solución.
Algoritmo de cifrado tipo M-H
Paso 1. Elegir W un vector de elemento de una sucesión supercreciente.

Elegir u > 2· w_n y v tal que (u, v) = 1.

Calcular la inversa de v mod u, v^-1

Crear la clave privada (W, u, v^-1).

Paso 2. Crear la clave pública:

Calcular W’ = W· v mod u, ésto es un vector de n elementos.

Esta clave (W’) se manda a todos los usuarios.
Cifrar un mensaje
Paso 1. Elegir el mensaje para mandar cifrado, M.

Paso 2. Poner el mensaje en bloques de n bits, un bloque sería M = m₁ + … +m_n .

Paso 3. Calcular C = m₁ w₁‘ + … + m_n w_n ‘ para cada uno de los bloques.

Paso 4. Mandar C.
Descifrar un mensaje
Resolver el problema fácil de la mochila para v^-1· C mod u y W. Esto nos da un vector M. El mensaje original será m₁ ·w₁ + … + m_n ·w_n .

BIBLIOGRAFIA

[DENN 83] = Denning, D.E.R. «Cryptography and data security» Addison-Wesley, 1883.

[SCHR 79] = Schroeppel, R and Shamir, A «A TS2=O(2r) Time space trade off for certain NP. Complete problems» Proc. IEEE 20 Annual symposium 1979.

[POHL 78] = S. C. Pohling and M. E. Hellman ,»An improved algoritm for computing logarithms in GF(p) and its cryptographics significance», IEEE trans on inform 1978.

[SHAM 80] = Shamir A., Zippel R. E. «On the security of the Merkle-Hellman cryptographic Scheme» IEEE trans on inform 1980.

[SHAM 84] = Shamir A. «A polynomial time algoritm for breaking the basic Merckle-Hellman cryptosystems» IEEE trans on inform 1984.

[MEH 78] = R. C. MERKLE, M.E. HELLMAN. Hiding information and signatures in trapdoor knapsacks. IEEE trans on inform 1978.

[ADL 83] = N. ALEXANDRIS, M. BURMSTER, V. CHRISSIKOPOULOS, Y. DESMEDT. A secure key distribution system. Proc 3 symposium on state and progress of research in cryptography, Romo, italia, 1993.

[LA0 83] = J.C. LAGARIAS, A.M. ODLYZKO. Solving low-density subset sum problems. Processdings of the 24 IEEE symposium on foundations of computer science, 1983.

[BRO 88] = E.F. BRICKELL, A.M. ODLYZKO. Cryptanalysis: a survey of recent results. IEEE, 1988.