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

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 valor, el cual es la suma de un subconjunto de estos números, determinar cual es el subconjunto correspondiente. En general, es sabido que este problema es de clase NP-completo. Sin embargo, si la secuencia de números que pueden ser elegidos es supercreciente -- esto es, que 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, combinado 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, una subsecuencia de la secuencia difícil es elegida a partir de una secuencia de bits(el texto claro), del mismo largo que la llave, y haciendo que cada término en la llave pública que corresponde a 1 en el texto claro sea parte de la subsecuencia, y por el contrario dejando fuera de esta subsecuencia a cada término en la llave pública que corresponde a 0 en el texto claro. Luego suman los elementos de la subsecuencia, y resultado de esto es el texto cifrado.

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 encriptar 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}^{n}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ían 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 ${\pmod {q}}$. La existencia del inverso de r es necesaria para que se puedea realizar el descifrado.

Cálculo de la secuencia pública

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

La clave pública es $\beta$ , 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 $\alpha _{i}$ tales que satisfacen

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

Este problema sería difícil de resolver si los $\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 $\beta _{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 euclidiano 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}rs\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 supercreciente.

El algoritmo aváro para resolver esto consiste en lo siguiente:

Tomar el elemento más grande en $w$, digamos $w_{k}$.

Si $w_{k}>c'$, luego $\alpha _{k}=0$,

Sino $\alpha _{k}=1$

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