Criptosistema de mochila Merkle-Hellman

El criptosistema de mochila Merkle-Hellman fue uno de los primeros criptosistemas de clave pública . Fue publicado por Ralph Merkle y Martin Hellman en 1978. Adi Shamir publicó un ataque de tiempo polinomial en 1984. Como resultado, el criptosistema ahora se considera inseguro. ^{[1] : 465  [2] : 190}

Historia

El concepto de criptografía de clave pública fue introducido por Whitfield Diffie y Martin Hellman en 1976. ^[3] En ese momento propusieron el concepto general de una "función unidireccional de puerta trampa", una función cuya inversa es computacionalmente inviable de calcular sin alguna "información de puerta trampa" secreta; pero aún no habían encontrado un ejemplo práctico de tal función. Luego, otros investigadores propusieron varios criptosistemas de clave pública específicos en los años siguientes, como RSA en 1977 y Merkle-Hellman en 1978. ^[4]

Descripción

Merkle–Hellman es un criptosistema de clave pública, lo que significa que se utilizan dos claves, una clave pública para el cifrado y una clave privada para el descifrado. Se basa en el problema de la suma de subconjuntos (un caso especial del problema de la mochila ). ^[5] El problema es el siguiente: dado un conjunto de números enteros y un número entero , encuentre un subconjunto de cuya suma sea . En general, se sabe que este problema es NP-completo . Sin embargo, si es supercreciente , lo que significa que cada elemento del conjunto es mayor que la suma de todos los números del conjunto menores que él, el problema es "fácil" y solucionable en tiempo polinomial con un algoritmo voraz simple . ${\displaystyle A}$ ${\displaystyle c}$ ${\displaystyle A}$ ${\displaystyle c}$ ${\displaystyle A}$

En Merkle–Hellman, descifrar un mensaje requiere resolver un problema de mochila aparentemente "difícil". La clave privada contiene una lista supercreciente de números , y la clave pública contiene una lista no supercreciente de números , que en realidad es una versión "disfrazada" de . La clave privada también contiene información de "trampa" que se puede utilizar para transformar un problema de mochila difícil usando en un problema de mochila fácil usando . ${\displaystyle W}$ ${\displaystyle B}$ ${\displaystyle W}$ ${\displaystyle B}$ ${\displaystyle W}$

A diferencia de otros criptosistemas de clave pública como RSA , las dos claves de Merkle-Hellman no son intercambiables; la clave privada no se puede utilizar para el cifrado. Por lo tanto, Merkle-Hellman no se puede utilizar directamente para la autenticación mediante firma criptográfica , aunque Shamir publicó una variante que sí se puede utilizar para la firma. ^[6]

Generación de claves

1. Elija un tamaño de bloque . Con esta clave se pueden cifrar números enteros de hasta bits de longitud. ${\displaystyle n}$ ${\displaystyle n}$

2. Elija una secuencia aleatoria supercreciente de números enteros positivos ${\displaystyle n}$

${\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}$

El requisito de superincremento significa que , para . ${\displaystyle w_{k}>\sum _{i=1}^{k-1}w_{i}}$ ${\displaystyle 1<k\leq n}$

3. Elija un número entero aleatorio tal que ${\displaystyle q}$

${\displaystyle q>\sum _{i=1}^{n}w_{i}}$

4. Elija un número entero aleatorio tal que (es decir, y son coprimos ). ${\displaystyle r}$ ${\displaystyle \gcd(r,q)=1}$ ${\displaystyle r}$ ${\displaystyle q}$

5. Calcular la secuencia

${\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}$

dónde . ${\displaystyle b_{i}=rw_{i}{\bmod {q}}}$

La clave pública es y la clave privada es . ${\displaystyle B}$ ${\displaystyle (W,q,r)}$

Encriptación

Sea un mensaje de -bit que consta de bits , con el bit de orden más alto. Seleccione cada uno para el cual sea distinto de cero y súmelos. De manera equivalente, calcule ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m_{1}m_{2}\dots m_{n}}$ ${\displaystyle m_{1}}$ ${\displaystyle b_{i}}$ ${\displaystyle m_{i}}$

${\displaystyle c=\sum _{i=1}^{n}m_{i}b_{i}}$.

El texto cifrado es . ${\displaystyle c}$

Descifrado

Para descifrar un texto cifrado , debemos encontrar el subconjunto de cuya suma sea . Para ello, transformamos el problema en uno de búsqueda de un subconjunto de . Ese problema se puede resolver en tiempo polinómico, ya que es supercreciente. ${\displaystyle c}$ ${\displaystyle B}$ ${\displaystyle c}$ ${\displaystyle W}$ ${\displaystyle W}$

1. Calcular la inversa modular de módulo utilizando el algoritmo euclidiano extendido . La inversa existirá ya que es coprimo de . ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle q}$

${\displaystyle r':=r^{-1}{\pmod {q}}}$

El cálculo es independiente del mensaje y puede realizarse solo una vez cuando se genera la clave privada. ${\displaystyle r'}$

2. Calcular

${\displaystyle c':=cr'{\bmod {q}}}$

3. Resuelva el problema de suma de subconjuntos utilizando la secuencia supercreciente , mediante el algoritmo voraz simple que se describe a continuación. Sea la lista resultante de índices de los elementos cuya suma es . (Es decir, .) ${\displaystyle c'}$ ${\displaystyle W}$ ${\displaystyle X=(x_{1},x_{2},\dots ,x_{k})}$ ${\displaystyle W}$ ${\displaystyle c'}$ ${\displaystyle c'=\sum _{i=1}^{k}w_{x_{i}}}$

4. Construya el mensaje con un 1 en cada posición de bit y un 0 en todas las demás posiciones de bit: ${\displaystyle m}$ ${\displaystyle x_{i}}$

${\displaystyle m=\sum _{i=1}^{k}2^{n-x_{i}}}$

Solución del problema de la suma de subconjuntos

Este sencillo algoritmo codicioso encuentra el subconjunto de una secuencia supercreciente que suma , en tiempo polinomial: ${\displaystyle W}$ ${\displaystyle c'}$

1. Inicializar en una lista vacía. ${\displaystyle X}$

2. Encuentra el elemento más grande en el que es menor o igual a , digamos . ${\displaystyle W}$ ${\displaystyle c'}$ ${\displaystyle w_{j}}$

3. Restar: . ${\displaystyle c':=c'-w_{j}}$

4. Añadir a la lista . ${\displaystyle j}$ ${\displaystyle X}$

5. Si es mayor que cero, vuelva al paso 2. ${\displaystyle c'}$

Ejemplo

Generación de claves

Cree una clave para cifrar números de 8 bits creando una secuencia supercreciente aleatoria de 8 valores:

${\displaystyle W=(2,7,11,21,42,89,180,354)}$

La suma de estos es 706, así que seleccione un valor mayor para : ${\displaystyle q}$

${\displaystyle q=881}$.

Elige ser coprimo de : ${\displaystyle r}$ ${\displaystyle q}$

${\displaystyle r=588}$.

Construya la clave pública multiplicando cada elemento por módulo : ${\displaystyle B}$ ${\displaystyle W}$ ${\displaystyle r}$ ${\displaystyle q}$

${\displaystyle {\begin{aligned}&(2*588){\bmod {8}}81=295\\&(7*588){\bmod {8}}81=592\\&(11*588){\bmod {8}}81=301\\&(21*588){\bmod {8}}81=14\\&(42*588){\bmod {8}}81=28\\&(89*588){\bmod {8}}81=353\\&(180*588){\bmod {8}}81=120\\&(354*588){\bmod {8}}81=236\end{aligned}}}$

Por eso . ${\displaystyle B=(295,592,301,14,28,353,120,236)}$

Encriptación

Sea 8 bits el mensaje . Multiplicamos cada bit por el número correspondiente en y sumamos los resultados: ${\displaystyle m=97=01100001_{2}}$ ${\displaystyle B}$

 0 * 295+ 1 * 592+ 1 * 301+ 0 * 14+ 0 * 28+ 0 * 353+ 0 * 120+ 1 * 236 = 1129

El texto cifrado es 1129. ${\displaystyle c}$

Descifrado

Para descifrar 1129, primero use el algoritmo euclidiano extendido para encontrar el inverso modular de mod : ${\displaystyle r}$ ${\displaystyle q}$

${\displaystyle r'=r^{-1}{\bmod {q}}=588^{-1}{\bmod {8}}81=442}$.

Calcular . ${\displaystyle c'=cr'{\bmod {q}}=1129*442{\bmod {8}}81=372}$

Utilice el algoritmo voraz para descomponer 372 en una suma de valores: ${\displaystyle w_{i}}$

${\displaystyle {\begin{aligned}c'&=372\\&w_{8}=354\leq 372\\c'&=372-354=18\\&w_{3}=11\leq 18\\c'&=18-11=7\\&w_{2}=7\leq 7\\c'&=7-7=0\end{aligned}}}$

Por lo tanto , la lista de índices es . El mensaje ahora se puede calcular como ${\displaystyle 372=354+11+7=w_{8}+w_{3}+w_{2}}$ ${\displaystyle X=(8,3,2)}$

${\displaystyle m=\sum _{i=1}^{3}2^{n-x_{i}}=2^{8-8}+2^{8-3}+2^{8-2}=1+32+64=97}$.

Criptoanálisis

En 1984, Adi Shamir publicó un ataque al criptosistema Merkle-Hellman que puede descifrar mensajes cifrados en tiempo polinomial sin utilizar la clave privada. ^[7] El ataque analiza la clave pública y busca un par de números y tal que sea una secuencia supercreciente. El par encontrado por el ataque puede no ser igual a la clave privada, pero al igual que ese par puede usarse para transformar un problema de mochila difícil en un problema fácil utilizando una secuencia supercreciente. El ataque opera únicamente sobre la clave pública; no es necesario acceder a los mensajes cifrados. ${\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}$ ${\displaystyle u}$ ${\displaystyle m}$ ${\displaystyle (ub_{i}{\bmod {m}})}$ ${\displaystyle (u,m)}$ ${\displaystyle (r',q)}$ ${\displaystyle B}$

El ataque de Shamir al criptosistema Merkle-Hellman funciona en tiempo polinomial incluso si los números en la clave pública se mezclan aleatoriamente, un paso que normalmente no se incluye en la descripción del criptosistema, pero que puede ser útil contra algunos ataques más primitivos.

Referencias

1. Schneier, Bruce (1996). Criptografía aplicada . Nueva York: John Wiley & Sons. ISBN 0-471-12845-7.
2. Stinson, Douglas R. (1995). Criptografía: teoría y práctica . Boca Raton: CRC Press. ISBN 0-8493-8521-0.
3. Whitfield Diffie; Martin Hellman (1976). "Nuevas direcciones en criptografía". IEEE Transactions on Information Theory . 22 (6): 644. CiteSeerX 10.1.1.37.9720 . doi :10.1109/TIT.1976.1055638. 
4. Merkle, Ralph; Hellman, Martin (1978). "Ocultar información y firmas en mochilas con trampilla". IEEE Transactions on Information Theory . 24 (5): 525–530. doi :10.1109/TIT.1978.1055927.
5. Cherowitzo, William (2002-03-02). "Criptograma de mochila Merkle-Hellman". Matemáticas 5410 - Criptología moderna . Consultado el 18 de agosto de 2019 .
6. Shamir, Adi (julio de 1978). "Un esquema de firma rápido". Memorándum técnico del Laboratorio de Ciencias de la Computación del MIT . 79 (MIT/LCS/TM–107): 15240. Código Bibliográfico :1978STIN...7915240S.
7. Shamir, Adi (1984). "Un algoritmo de tiempo polinomial para romper el criptosistema básico de Merkle-Hellman". IEEE Transactions on Information Theory . 30 (5): 699–704. doi :10.1109/SFCS.1982.5.