Criptosistema de llave publica

Fue uno de los primeros criptosistemas de llave pública y fue inventado por Ralph Merkle y Martin Hellman en 1978. 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, y además no ofrece funcionalidades para firmar.


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.


primero una curiosidad, el nombre de las mochilas, viene porque se puede utilizar para decidir que meter en una mochila, teniendo en cuenta el peso que podemos llevar dentro de la mochila, y el peso de los objetos que queremos meter dentro, asignadoles a estos unos valores de utilidad, que decidimos, segun su utilidad en el cometido que se va a realizar. (maldita sea, nose si me he liado describiendo esto, espero que sea entendible)


Se trata de un sistema asimétrico, cifra y descifra, con claves distintas, es decir usa una clave privada y otra publica.


Bueno al ajo:


1- Se parte de una clave, o mochila secreta (Vector de valores)


(S1, S2, S3, … ,Sn) = MSEC


2- Se escoge una aritmetica modular finita, donde p > Sumatorio de los valores de MSEC


3- El receptor, crea la clave o mochila publica, multiplicando mod p cada valor de la mochila secreta.


(aS1, aS2, …, aSn) = MPUB


la adebe tener un inverso multiplicativo, en la aritmética modular p a* (a)-1 = 1 modp


4- Un emisor, envia M = (1001 … 01), y lo mútiplica por su mochila publica:


C = M * MPUB = (S’1 + S’2 + … + S’n)


5- El receptor descifra con (a)-1; M = C * (a)-1, compara con MSEC y saca M


NOTA: (a)-1 es a elevado a la menos uno.