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 polinómico 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 trampilla", una función cuya inversa es computacionalmente inviable de calcular sin alguna "información secreta"; pero aún no habían encontrado un ejemplo práctico de tal función. Otros investigadores propusieron varios criptosistemas de clave pública específicos durante 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 , encontrar un subconjunto 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 menor que él, el problema es "fácil" y se puede resolver en tiempo polinómico con un algoritmo codicioso 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 de números supercreciente , y la clave pública contiene una lista de números no supercreciente , que en realidad es una versión "disfrazada" de . La clave privada también contiene información de "trampilla" que se puede utilizar para transformar un problema de mochila difícil en un problema de mochila fácil . ${\displaystyle W}$ ${\displaystyle B}$ ${\displaystyle W}$ ${\displaystyle B}$ ${\displaystyle W}$

A diferencia de otros criptosistemas de clave pública como RSA , las dos claves en Merkle-Hellman no son intercambiables; la clave privada no se puede utilizar para el cifrado. Por tanto, Merkle-Hellman no se puede utilizar directamente para la autenticación mediante firma criptográfica , aunque Shamir publicó una variante que 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 supercreciente 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 sean coprimos ). ${\displaystyle r}$ ${\displaystyle \gcd(r,q)=1}$ ${\displaystyle r}$ ${\displaystyle q}$

5. Calcula 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)}$

Cifrado

Sea un mensaje de bits que consta de bits , con el bit de mayor orden. Seleccione cada uno de los cuales sea distinto de cero y súmelos. Equivalentemente, 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 cuya suma sea . Hacemos esto transformando el problema en uno de encontrar un subconjunto de . Ese problema se puede resolver en tiempo polinomial ya que es supercreciente. ${\displaystyle c}$ ${\displaystyle B}$ ${\displaystyle c}$ ${\displaystyle W}$ ${\displaystyle W}$

1. Calcule el inverso modular del módulo utilizando el algoritmo euclidiano extendido . Lo inverso existirá ya que es coprimo con . ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle q}$

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

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

2. Calcular

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

3. Resuelva el problema de suma de subconjuntos para usar la secuencia supercreciente , mediante el algoritmo codicioso simple que se describe a continuación. Sea la lista resultante de índices de los elementos cuya suma es . (Eso es, .) ${\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}}}$

Resolver el problema de la suma de subconjuntos

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

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

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

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

4. Agregar a la lista . ${\displaystyle j}$ ${\displaystyle X}$

5. Si es mayor que cero, regrese 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}$.

Elija ser coprime para : ${\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)}$

Cifrado

Sea el mensaje de 8 bits . Multiplicamos cada bit por el número correspondiente 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 codicioso 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 , y 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 polinómico sin utilizar la clave privada. ^[7] El ataque analiza la clave pública y busca un par de números que sean una secuencia supercreciente. El par encontrado por el ataque puede no ser igual al de la clave privada, pero al igual que ese par, puede usarse para transformar un problema de mochila difícil en un problema fácil usando una secuencia supercreciente. El ataque opera únicamente con la clave pública; no es necesario acceder a 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 polinómico incluso si los números de 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 Ratón: CRC Press. ISBN 0-8493-8521-0.
3. Whitfield Diffie; Martín Hellman (1976). "Nuevas direcciones en criptografía". Transacciones IEEE sobre teoría de la información . 22 (6): 644. CiteSeerX 10.1.1.37.9720 . doi :10.1109/TIT.1976.1055638. 
4. Merkle, Ralph; Hellman, Martín (1978). "Ocultar información y firmas en mochilas con trampilla". Transacciones IEEE sobre teoría de la información . 24 (5): 525–530. doi :10.1109/TIT.1978.1055927.
5. Cherowitzo, William (2 de marzo de 2002). "Criptosistema 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ápida". Memorando 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 Merkle - Hellman". Transacciones IEEE sobre teoría de la información . 30 (5): 699–704. doi :10.1109/SFCS.1982.5.