Criptosistema de Merkle-Hellman

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Merkle-Hellman (MH) fue uno de los primeros criptosistemas de llave pública y fue inventado por Ralph Merkle y Martin Hellman en 1978.[1] Aunque sus ideas eran elegantes, y mucho más simples que RSA, no tuvo el mismo éxito que éste último, debido a que MH ya fue roto,[2] y además no ofrece funcionalidades para firmar.

Descripción[editar]

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.

Generación de las claves[editar]

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[editar]

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.

Descifrado[editar]

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.

Método Matemático[editar]

Generación de las claves[editar]

Para cifrar un mensaje de n-bits, elegir una secuencia supercreciente :

 w =(w_1, w_2, ..., w_n)  \mbox{ tal que } w_{i+1} > \sum_{j=1}^i w_j

de n números naturales (distintos de cero). Elegir un número q (preferiblemente al azar), tal que

 q > \sum_{i = 1}^n w_i

y otro número entero, r tal que mcd(r,q) = 1.

q es escogido de esta forma para asegurar la unicidad del texto cifrado. Si fuera menor, podría haber varios textos claros que resultarían en el mismo texto cifrado. r debe ser coprimo con q puesto que de otra forma podría no tener inverso en \pmod{q}. La existencia del inverso de r es necesaria para que se pueda realizar el descifrado.

A continuación, se calcula la secuencia:

 \mathbf \beta =(\beta_1, \beta_2, ..., \beta_n)  \mbox{ tal que } \beta_i = rw_i \pmod{q}

La clave pública es \beta , mientras que la llave privada es  (w, q, r) .

Cifrado[editar]

Para cifrar un mensaje de n-bits

 \mathbf \alpha =(\alpha_1, \alpha_2, ..., \alpha_n)

donde \mathbf\alpha_i es el i-ésimo bit del mensaje y  \mathbf \alpha_i \in \{0, 1\} , calcular

c = \sum_{i = 1}^n  \alpha_i \beta_i.

El criptograma o texto cifrado es c.

Descifrado[editar]

Para descifrar el criptograma c, el receptor tiene que encontrar los bits del mensaje \alpha_i tales que satisfacen

c = \sum_{i = 1}^n  \alpha_i \beta_i.

Este problema sería difícil de resolver si los \beta_i fueran valores aleatorios, debido a que el receptor tendría que resolver una instancia del problema de la mochila, el cual se sabe que es NP-hard. Sin embargo, los valores \beta_i fueron elegidos de forma que el descifrado sea fácil si la clave privada (w , q , r) es conocida.

Para el descifrado se debe encontrar un entero s tal que es el inverso de r módulo q. Esto es, s satisface la ecuación :

  rs \equiv  1 \pmod{q}

o equivalentemente, existe un entero k tal que sr = kq + 1. Dado que r fue escogido como un coprimo de q es posible encontrar s y k usando el Algoritmo de Euclides extendido. Luego el receptor del criptograma c calcula:

c'\equiv cs \pmod{q}.

Por tanto

c' \equiv cs \equiv  \sum_{i = 1}^n  \alpha_i \beta_i s \pmod{q}.

Ya que   rs \equiv  1 \pmod{q} y  \mathbf \beta_i \equiv rw_i \pmod{q} entonces

\beta_i s\equiv w_i r s\equiv w_i\pmod{q}.

Con esto

c' \equiv \sum_{i = 1}^n  \alpha_i w_i\pmod{q}.

La suma de todos los valores w_i es menor que q y por ende \sum_{i = 1}^n  \alpha_i w_i\,\bmod\, q también está en el intervalo \mathbf [0,q-1].

De este modo el receptor tiene que resolver el siguiente problema de la mochila.

c' = \sum_{i = 1}^n  \alpha_i w_i.


Este problema es fácil debido a que la secuencia w es supercreciente.

El algoritmo avaro para resolver esto consiste en lo siguiente:

   Tomar el elemento más grande en  w, digamos w_k. 
   Si w_k > c' , luego \alpha_k = 0,
   Sino \alpha_k = 1
   Disminuímos  c'  en w_k \alpha_k 
   y repetimos estos pasos hasta que se haya alcanzado c'.

El pseudo código para este algoritmo sería:

   While ( c' > 0 ){
        w_k=\mbox{ extract-max } (w) 
       If   (w_k > c') 
          then   \alpha_k = 0 ,
       Else  \alpha_k = 1
           c' = c' -w_k * \alpha_k
   }

Este algoritmo no se puede usar para firmar puesto que el criptograma es un número (c) y no un texto, de este modo no se puede descifrar un mensaje claro y por ende no se puede firmar.

Referencias[editar]

  1. Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525–530.
  2. Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279–288. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF