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.

Historia

El concepto de criptografía de clave pública fue introducido por Whitfield Diffie y Martin Hellman en 1976. En ese momento, propusieron el concepto general de una "función unidireccional de trampilla", una función cuyo inverso es computacionalmente inviable de calcular sin cierta 'información de trampilla' 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.

Descripción

Merkle-Hellman es un criptosistema de clave pública, lo que significa que se utilizan dos claves, una clave pública para la encriptación y una clave privada para la desencriptación. Se basa en el problema de la suma de subconjunto (un caso especial del problema de la mochila). El problema es el siguiente: dado un conjunto de enteros ${displaystyle A}$ y un entero ${displaystyle c}$, encontrar un subconjunto de ${displaystyle A}$ que suma ${displaystyle c}$. En general, se sabe que este problema está completo. Sin embargo, si ${displaystyle A}$ es superincreciente, lo que significa que cada elemento del conjunto es mayor que la suma de todos los números en el conjunto menos que él, el problema es "fácil" y solvable en el tiempo polinomio con un simple algoritmo codicioso.

En Merkle-Hellman, descifrar un mensaje requiere resolver un problema aparentemente "difícil". La clave privada contiene una lista de números superincreciente ${displaystyle W.$, y la clave pública contiene una lista no superincreciente de números ${displaystyle B}$, que es en realidad una versión "disguida" de ${displaystyle W.$. La clave privada también contiene cierta información de "trapdoor" que se puede utilizar para transformar un problema de knapsack duro utilizando ${displaystyle B}$ en un problema de knapsack fácil ${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 usar directamente para la autenticación mediante firma criptográfica, aunque Shamir publicó una variante que se puede usar para firmar.

Generación de claves

1. Elige un tamaño de bloque ${displaystyle n}$. Integers hasta ${displaystyle n}$ bits de longitud se pueden encriptar con esta clave.

2. Elija una secuencia de superincremento al azar ${displaystyle n}$ enteros positivos

${displaystyle ¿Qué?$

El requisito de superincremento significa que ${displaystyle w_{k}sum ¿Qué?$, para ${displaystyle 1seqleq n}$.

3. Elija un entero al azar ${displaystyle q}$ tales que

${displaystyle q confíasum ¿Qué?$

4. Elija un entero al azar ${displaystyle r}$ tales que ${displaystyle gcd(r,q)=1}$ (es decir, ${displaystyle r}$ y ${displaystyle q}$ son coprime).

5. Calcular la secuencia

${displaystyle B=(b_{1},b_{2},dotsb_{n}}$

Donde ${displaystyle ¿Qué?$.

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

Cifrado

Vamos ${displaystyle m}$ ser un ${displaystyle n}$-bit mensaje consistente en bits ${displaystyle m_{1}m_{2}dots m_{n}$, con ${displaystyle m_{1}$ el pedido más alto. Seleccione cada uno ${displaystyle B_{i}$ para la cual ${displaystyle #$ no es cero, y añadirlos juntos. Equivalentemente, calcular

${displaystyle c=sum ¿Qué?$.

El cifertexto es ${displaystyle c}$.

Descifrado

Para descifrar un ciphertext ${displaystyle c}$, debemos encontrar el subconjunto de ${displaystyle B}$ que suma ${displaystyle c}$. Lo hacemos transformando el problema en uno de encontrar un subconjunto de ${displaystyle W.$. Ese problema se puede resolver en el tiempo polinomio desde entonces ${displaystyle W.$ es superincreciente.

1. Calcular el inverso modular de ${displaystyle r}$ modulo ${displaystyle q}$ usando el algoritmo Extended Euclidean. El inverso existirá desde ${displaystyle r}$ es coprime ${displaystyle q}$.

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

La computación de ${displaystyle r'}$ es independiente del mensaje, y se puede hacer sólo una vez cuando se genera la clave privada.

2. Calcular

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

3. Resolver el problema de la suma de subconjunto ${displaystyle c'}$ usando la secuencia superincreciente ${displaystyle W.$, por el simple algoritmo codicioso descrito a continuación. Vamos ${displaystyle X=(x_{1},x_{2},dotsx_{k}}$ ser la lista resultante de índices de los elementos ${displaystyle W.$ que suma ${displaystyle c'}$. (Eso es, ${displaystyle c'=sum ¿Qué?$.)

4. Construir el mensaje ${displaystyle m}$ con 1 en cada uno ${displaystyle x_{i}}$ posición del bit y un 0 en todas las posiciones del bit:

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

Resolviendo el problema de la suma de subconjuntos

Este simple algoritmo codicioso encuentra el subconjunto de una secuencia superincreciente ${displaystyle W.$ que suma ${displaystyle c'}$, en tiempo polinomio:

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

2. Encontrar el elemento más grande en ${displaystyle W.$ que es inferior o igual a ${displaystyle c'}$, di ${displaystyle w_{j}$.

3. Subtract: ${displaystyle c.$.

4. Apéndice ${displaystyle j}$ a la lista ${displaystyle X}$.

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

Ejemplo

Generación de claves

Cree una clave para cifrar números de 8 bits mediante la creación de una secuencia supercreciente aleatoria de 8 valores:

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

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

${displaystyle q=881}$.

Elija ${displaystyle r}$ ser coprime ${displaystyle q}$:

${displaystyle r=588}$.

Construir la clave pública ${displaystyle B}$ multiplicando cada elemento en ${displaystyle W.$ por ${displaystyle r}$ modulo ${displaystyle q}$:

${fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {b} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft ] {fnMicrosoft} {fnMicrosoft ] {b} {b} {b}b}b}b} {b}b}b2}b}b}b2}b}b}b}}b}b2} {b2} {b}}b}b2}b2}}b2}b2}b2} {b2}b2}b2} {b2}}b2b2}b2}b2} {b2}}b}b2} {b2}b}b2b2}b2}b}b2}b$

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

Cifrado

Que el mensaje de 8 bits sea ${displaystyle m=97=01100001_{2}$. Multiplicamos cada bit por el número correspondiente en ${displaystyle B}$ y añadir los resultados:

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

El ciphertext ${displaystyle c}$ es 1129.

Descifrado

Para descifrar 1129, primero utilice el Algoritmo Euclideano Extendido para encontrar el inverso modular de ${displaystyle r}$ mod ${displaystyle q}$:

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

Computación ${fnMicrosoft}=1129*442{bmod {8}81=372}$.

Utilice el algoritmo codicioso para descomponer 372 en una suma de ${displaystyle ¿Qué?$ valores:

${displaystyle {begin{aligned}c' limit=372\f}=354leq 372c' diez = 372-354=18\\\cH3}=11leq 18c 'c' juntos=18-11=7\cccc' tarden}$

Así ${displaystyle 372=354+11+7=w_{8}+w_{3}+w_{2}$, y la lista de índices es ${displaystyle X=(8,3,2)}$. El mensaje ahora puede ser calculado como

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

Cripanálisis

En 1984 Adi Shamir publicó un ataque contra el criptosistema Merkle-Hellman que puede descifrar mensajes cifrados en tiempo polinomio sin usar la clave privada. El ataque analiza la clave pública ${displaystyle B=(b_{1},b_{2},dotsb_{n}}$ y busca un par de números ${displaystyle u}$ y ${displaystyle m}$ tales que ${displaystyle (ub_{i}{bmod {m}}}$ es una secuencia superincreciente. El ${displaystyle (u,m)}$ par encontrado por el ataque puede no ser igual a ${displaystyle (r',q)}$ en la llave privada, pero como ese par se puede utilizar para transformar un problema de knapsack duro utilizando ${displaystyle B}$ en un problema fácil usando una secuencia superincreciente. El ataque opera únicamente en la clave pública; no es necesario acceder a mensajes cifrados.