Criptosistema de Merkle-Hellman

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 polinómico.

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 de 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.

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.

Para cifrar un mensaje de n-bits, elegir una secuencia supercreciente :

${\displaystyle 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

${\displaystyle 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 ${\displaystyle {\pmod {q}}}$. La existencia del inverso de r es necesaria para que se pueda realizar el descifrado.

A continuación, se calcula la secuencia:

${\displaystyle \mathbf {\beta } =(\beta _{1},\beta _{2},...,\beta _{n}){\mbox{ tal que }}\beta _{i}=rw_{i}{\pmod {q}}}$

La clave pública es ${\displaystyle \beta }$ , mientras que la llave privada es ${\displaystyle (w,q,r)}$.

Para cifrar un mensaje de n-bits

${\displaystyle \mathbf {\alpha } =(\alpha _{1},\alpha _{2},...,\alpha _{n})}$

donde ${\displaystyle \mathbf {\alpha } _{i}}$ es el i-ésimo bit del mensaje y ${\displaystyle \mathbf {\alpha } _{i}\in \{0,1\}}$, calcular

${\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}}$.

El criptograma o texto cifrado es c.

Para descifrar el criptograma c, el receptor tiene que encontrar los bits del mensaje ${\displaystyle \alpha _{i}}$ tales que satisfacen

${\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}}$.

Este problema sería difícil de resolver si los ${\displaystyle \beta _{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 ${\displaystyle \beta _{i}}$ fueron elegidos de forma que el descifrado sea fácil si la clave privada ${\displaystyle (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 :

${\displaystyle 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:

${\displaystyle c'\equiv cs{\pmod {q}}.}$

Por tanto

${\displaystyle c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.}$

Ya que ${\displaystyle rs\equiv 1{\pmod {q}}}$ y ${\displaystyle \mathbf {\beta } _{i}\equiv rw_{i}{\pmod {q}}}$ entonces

${\displaystyle \beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.}$

Con esto

${\displaystyle c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.}$

La suma de todos los valores ${\displaystyle w_{i}}$ es menor que q y por ende ${\displaystyle \sum _{i=1}^{n}\alpha _{i}w_{i}\,{\bmod {\,}}q}$ también está en el intervalo ${\displaystyle \mathbf {[} 0,q-1]}$.

De este modo el receptor tiene que resolver el siguiente problema de la mochila.

${\displaystyle 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 ${\displaystyle w}$, digamos ${\displaystyle w_{k}}$. 
   Si ${\displaystyle w_{k}>c'}$, luego ${\displaystyle \alpha _{k}=0}$,
   Sino ${\displaystyle \alpha _{k}=1}$
   Disminuímos  c'  en ${\displaystyle w_{k}\alpha _{k}}$ 
   y repetimos estos pasos hasta que se haya alcanzado c'.

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

   While ${\displaystyle (c'>0)}${
       ${\displaystyle w_{k}={\mbox{ extract-max }}(w)}$
       If ${\displaystyle (w_{k}>c')}$
          then ${\displaystyle \alpha _{k}=0}$,
       Else ${\displaystyle \alpha _{k}=1}$
          ${\displaystyle c'=c'-w_{k}*\alpha _{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.