Cifrado Merkle-Hellman

Cifrado Merkle-Hellman

1. Propusto por Rafael Merkle y Martín Hellman en 1978

2. Se basa en el problema de la mochila

   • El problema de la mochila consiste en amontonar en un bolso, para alcanzar (si es posible) un peso total fijado.

3. Se utiliza para ocultar mensajes y no para preservar la autenticación de la firma.

4. 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 = (w1 , …, wn ) y 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 un 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 = M·W ó C = m1 w1 + … + mn wn.