Criptosistema de Merkle-Hellman

[1]​ Aunque sus ideas eran elegantes, y mucho más simples que RSA, no tuvo el mismo éxito que este último, debido a que MH ya fue roto,[2]​ y además no ofrece funcionalidades para firmar.Otra diferencia con RSA, es que sirve solo para cifrado, es decir, la llave pública es usada solo para cifrar (no para verificar firma) y la llave privada es usada solo para descifrar (no para firmar).En general, es sabido que este problema es de clase NP-completo.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.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.Elegir un número q (preferiblemente al azar), tal que 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.r debe ser coprimo con q puesto que de otra forma podría no tener inverso enLa existencia del inverso de r es necesaria para que se pueda realizar el descifrado.A continuación, se calcula la secuencia: La clave pública estales que satisfacen Este problema sería difícil de resolver si losfueron elegidos de forma que el descifrado sea fácil si la clave privadaPara 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: 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: Por tanto Ya queEste problema es fácil debido a que la secuencia w es supercreciente.El algoritmo avaro para resolver esto consiste en lo siguiente: El pseudo código para este algoritmo sería: 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.