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.

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 $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  $α k = 0$ ,
   Sino  $α k = 1$ 
   Disminuímos  c'  en  $w k α 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 = extract-max (w)$ 
       If  $(w k > c')$ 
          then  $α k = 0$ ,
       Else  $α k = 1$ 
           $c' = c' - w k * α 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

↑ Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525–530.
↑ 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

Categorías:

Criptografía
Algoritmos criptográficos

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

Los diccionarios y las enciclopedias sobre el Académico

Merkle-Hellman

Contenido

Descripción

Generación de las claves

Cifrado

Descifrado

Método Matemático

Generación de las claves

Cifrado

Descifrado

Referencias

Mira otros diccionarios:

Compartir el artículo y extractos

Los diccionarios y las enciclopedias sobre el Académico

Wikipedia Español

Merkle-Hellman

Contenido

Descripción

Generación de las claves

Cifrado

Descifrado

Método Matemático

Generación de las claves

Cifrado

Descifrado

Referencias

Mira otros diccionarios:

Compartir el artículo y extractos

Link directo