Algoritmo de cifrado de mochila en criptografía

El algoritmo de cifrado de mochila es el primer algoritmo criptográfico de clave pública general. Es desarrollado por Ralph Merkle y Mertin Hellman en 1978. Como es una criptografía de clave pública, necesita dos claves diferentes. Una es la clave pública que se usa para el proceso de cifrado y la otra es la clave privada que se usa para el proceso de descifrado. En este algoritmo veremos dos problemas de mochila diferentes en los que uno es fácil y el otro es difícil. La mochila fácil se usa como clave privada y la mochila dura se usa como clave pública. De la mochila fácil se deriva la mochila dura. 

Para la mochila fácil, elegiremos un problema de mochila súper creciente . La mochila súper creciente es una secuencia en la que cada término siguiente es mayor que la suma de todos los términos anteriores. 

Ejemplo – 

{1, 2, 4, 10, 20, 40} is a super increasing as
1<2, 1+2<4, 1+2+4<10, 1+2+4+10<20 and 1+2+4+10+20<40.

Derivar la clave pública 

• Paso 1: 
  elija una mochila súper creciente {1, 2, 4, 10, 20, 40} como clave privada. 
   
• Paso 2: 
  Elija dos números n y m. Multiplique todos los valores de la clave privada por el número n y luego encuentre el módulo m. El valor de m debe ser mayor que la suma de todos los valores de la clave privada, por ejemplo, 110. Y el número n no debe tener ningún factor común con m, por ejemplo, 31. 
   
• Paso 3: 
  Calcule los valores de la clave pública usando m y n. 

1x31 mod(110) = 31
2x31 mod(110) = 62
4x31 mod(110) = 14
10x31 mod(110) = 90
20x31 mod(110) = 70
40x31 mod(110) = 30

• Por lo tanto, nuestra clave pública es {31, 62, 14, 90, 70, 30} 
  y la clave privada es {1, 2, 4, 10, 20, 40}. 
   

Ahora tome un ejemplo para comprender el proceso de cifrado y descifrado. 

Ejemplo: 
permite que nuestro texto sin formato sea 100100111100101110. 

1. Cifrado: 
como nuestras mochilas contienen seis valores, dividiremos nuestro texto sin formato en grupos de seis:  

100100  111100  101110 

Multiplique cada valor de clave pública con los valores correspondientes de cada grupo y tome su suma. 

100100  {31, 62, 14, 90, 70, 30}
1x31+0x62+0x14+1x90+0x70+0x30 = 121

111100  {31, 62, 14, 90, 70, 30}
1x31+1x62+1x14+1x90+0x70+0x30 = 197

101110  {31, 62, 14, 90, 70, 30}
1x31+0x62+1x14+1x90+1x70+0x30 = 205 

Entonces, nuestro texto cifrado es 121 197 205. 

2. Descifrado: 
el receptor recibe el texto cifrado que debe descifrarse. El receptor también conoce los valores de m y n. 
Entonces, primero necesitamos encontrar el  , que es el inverso multiplicativo de n mod m, es decir,  

n x  mod(m) = 1

31 x mod(110) = 1

 = 71

Ahora, tenemos que multiplicar 71 con cada bloque de texto cifrado que tome el módulo m. 

121 x 71 mod(110) = 11 

Luego, tendremos que hacer la suma de 11 a partir de los valores de la clave privada {1, 2, 4, 10, 20, 40} es decir, 
1+10=11 para que los bits correspondientes sean 1 y los demás 0, que es 100100. 
Similarmente, 

197 x 71 mod(110) = 17
1+2+4+10=17 = 111100

And, 205 x 71 mod(110) = 35
1+4+10+20=35 = 101110 

Después de combinarlos obtenemos el texto decodificado. 
100100111100101110 que es nuestro texto sin formato.