Merkle-Hellman

Merkle-Hellman

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.

Contenido

Descripción

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 polinomial con un simple algoritmo voraz.

Generación de las 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 polinomial.

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.

Descifrado

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

Generación de las claves

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 (mod 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 β , mientras que la llave privada es (w,q,r).

Cifrado

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

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

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

Este problema sería difícil de resolver si los β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 β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 wi 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 wk. 
   Si wk > c', luego αk = 0,
   Sino αk = 1
   Disminuímos  c'  en wkαk 
   y repetimos estos pasos hasta que se haya alcanzado c'.

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

   While (c' > 0){
       wk =  extract-max (w)
       If (wk > c')
          then αk = 0,
       Else αk = 1
          c' = c' − wk * α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

  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

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Merkle-Hellman — (MH) was one of the earliest public key cryptosystems and was invented by Ralph Merkle and Martin Hellman in 1978. [Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory , 24(5),… …   Wikipedia

  • Merkle-Hellman — Das Merkle Hellman Kryptosystem (MH) ist ein asymmetrisches Kryptosystem, basierend auf dem Subset Sum Entscheidungsproblem (einem Spezialfall des Rucksackproblems). Inhaltsverzeichnis 1 Anwendung 1.1 B möchte an A eine verschlüsselte Nachricht… …   Deutsch Wikipedia

  • Merkle-Hellman-Kryptosystem — Das Merkle Hellman Kryptosystem (MH) ist ein asymmetrisches Verschlüsselungsverfahren, das auf dem Rucksackproblem basiert. Inhaltsverzeichnis 1 Beschreibung 1.1 Schlüsselerzeugung 1.2 Verschlüsselung …   Deutsch Wikipedia

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

  • Cryptosystème de Merkle-Hellman — Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, défini par Ralph Merkle et Martin Hellman en 1978[1]. Bien que l idée soit élégante, et bien plus simple que RSA, il a été démontré comme vulnérable par Adi Shamir[2]. Sommaire …   Wikipédia en Français

  • Cryptosysteme de Merkle-Hellman — Cryptosystème de Merkle Hellman Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, défini par Ralph Merkle et Martin Hellman en 1978.[1] Bien que l idée soit élégante, et bien plus simple que RSA, il a été démontré comme… …   Wikipédia en Français

  • Cryptosystème De Merkle-Hellman — Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, défini par Ralph Merkle et Martin Hellman en 1978.[1] Bien que l idée soit élégante, et bien plus simple que RSA, il a été démontré comme vulnérable par Adi Shamir.[2] Sommaire …   Wikipédia en Français

  • Cryptosystème de merkle-hellman — Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, défini par Ralph Merkle et Martin Hellman en 1978.[1] Bien que l idée soit élégante, et bien plus simple que RSA, il a été démontré comme vulnérable par Adi Shamir.[2] Sommaire …   Wikipédia en Français

  • Merkle — can refer to any of the following: Merkle, a pioneer motorcycle manufacturer Merkle–Damgård construction – A method to build cryptographic hash functions. Merkle–Hellman knapsack cryptosystem Merkle s Puzzles Surnames This page or section lists… …   Wikipedia

  • Hellman — is the surname of: * Danny Hellman (born 1964), American illustrator and cartoonist nicknamed Dirty Danny * Frances Hellman, physicist at University of California, Berkeley * Jakob Hellman (born 1965), Swedish pop singer * Lillian Hellman… …   Wikipedia

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”