El problema de la mochila en criptografía

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de mayo de 2020; las comprobaciones requieren 4 ediciones .

El problema de la mochila (o problema de la mochila ) en criptografía ( eng. Problema de la mochila ) es un problema sobre la base del cual los criptógrafos estadounidenses Ralph Merkle y Martin Hellman desarrollaron el primer algoritmo de cifrado de clave pública . Se llama criptosistema Merkle-Hellman. Para cifrar los mensajes, utilizamos la solución del problema de la mochila, que se conoce como NP-hard . Por lo tanto, se creía que podría garantizar la estabilidad criptográfica del sistema. Por el momento, se han creado muchos criptosistemas de mochila. Sin embargo, casi todos los existentes en la actualidad están pirateados o se reconocen como potencialmente inseguros.

Historia

El problema de la mochila está en el corazón del primer algoritmo de encriptación asimétrica (o encriptación de clave pública). La idea de la criptografía de clave pública fue propuesta por los criptógrafos estadounidenses Whitfield Diffie , Martin Hellman e, independientemente, Ralph Merkle . Fue presentado por primera vez por Diffie y Hellman en la Conferencia Nacional de Computación en 1976, en el mismo año se publicó su trabajo conjunto sobre este tema, New Directions in Cryptography . ) [1] . El artículo de Merkle "Secure Communication Over Insecure Channels" se publicó recién en 1978 [2] . La novedad en relación con los criptosistemas simétricos comunes en ese momento fue el uso de claves emparejadas: secreta ( ing. clave privada, clave secreta, SK ) y pública ( ing. clave pública, PK ), creada por el usuario. El usuario debe mantener en secreto la clave secreta utilizada para descifrar la información, mientras que la clave pública, que solo se necesita para el cifrado, puede hacerse pública. En muchos criptosistemas, la clave pública se obtiene de la clave secreta [3] [4] .

El primer algoritmo de cifrado basado en el problema de la mochila fue desarrollado por Merkle y Hellman en 1978 y se denominó " Algoritmo Merkle-Hellman " [3] . Se publicó en versiones de una sola etapa ( inglés de una sola iteración ) y de varias etapas ( inglés de múltiples iteraciones ). El algoritmo solo podía usarse para el cifrado, pero el criptoanalista israelí Adi Shamir lo adaptó para su uso en firmas digitales [3] . Después de que se publicó el esquema, Merkle ofreció una recompensa de $ 100 a cualquiera que descifrara con éxito el algoritmo de una etapa. En 1982, Shamir llevó a cabo un ataque exitoso y recibió la recompensa prometida. Pero incluso después de pagarlo, Merkle confiaba en la fortaleza criptográfica del sistema de múltiples etapas y ofreció $ 1,000 si se descifraba con éxito. En 1984, el matemático estadounidense Ernest Brickell logró completar un truco para una variante de cuarenta etapas en poco más de 1 hora en una máquina Cray-1 [5] [6] .

Independientemente el uno del otro, allá por 1980, el matemático estadounidense Ron Graham y Adi Shamir descubrieron una forma de aumentar la fuerza criptográfica del esquema Merkle-Hellman, pero ya en 1983 el esquema Graham-Shamir resultante fue descifrado por el científico estadounidense Leonard Adleman . . Sin embargo, continuó la búsqueda de modificaciones desprovistas de las deficiencias del esquema Merkle-Hellman. En 1985, el profesor asociado británico Rodney Goodman y el ingeniero estadounidense Anthony McAuley crearon un circuito basado en mochilas modulares con una escapatoria secreta que no se basaba en vectores supercrecientes , sino que utilizaba el teorema chino del resto [7] [8] .

Posteriormente, quedó claro que el esquema era vulnerable a los ataques basados en la búsqueda de lagunas secretas. Sin embargo, en 1990, Valtteri Niemi propuso un nuevo esquema basado en el mismo cometido de una mochila modular. Fue descifrado al año siguiente por Chi Ye Meng , Antoine Zhu y Jacques Stern [9] independientemente el uno del otro, utilizando métodos ligeramente diferentes. Además del uso de mochilas modulares, ha habido intentos de usar otros tipos de mochilas.

Entonces, en 1986, Harald Niederreiter publicó un criptosistema de mochila basado en la teoría de la codificación algebraica, que luego se rompió, y en 1988 Masakatsu Morii y Masao Kasahara desarrollaron un criptosistema de mochila usando una mochila multiplicativa [10] . Esta idea resultó exitosa y hasta el momento el sistema de las mochilas multiplicativas no ha sido hackeado.

En 2001, Shinya Kiuchi , Yasuyuki Murakami y Masao Kasahara propusieron una mejora al esquema Moriya-Kasahara basado en mochilas multiplicativas usando el algoritmo de Schalkwijk [11] .

También tuvo éxito la idea de Hussein Ali Hussein , Jafar Wadi Abdul Sad y M. Khalifa , quienes propusieron en 1991 un criptosistema de mochila multietapa ( English multistage trapdoor knapsack cryptosystem ). Fija el vector de mochila para cada etapa, y la salida (texto cifrado) después de cada etapa del algoritmo se usa como entrada (texto) para la siguiente etapa. No se conoce ningún ataque exitoso a este esquema (a partir de 2001) [12] .

Qu Minghua y Scott Vanstone en 1992 propusieron un criptosistema híbrido que se basa principalmente en el problema de la mochila, pero también incluye firmas logarítmicas. En 1994, R. Blackburn , Murphy, Sean y Jacques Stern demostraron que una versión simplificada del criptosistema U-Waston no es segura. Estos criptosistemas fueron estudiados más a fondo por Fong Nguyen y Jacques Stern en 1997 [5] .

También continuaron las mejoras al algoritmo clásico de Merkle-Hellman. En 1994, Orton propuso una modificación del esquema Merkle-Hellman de múltiples etapas, pero dos años más tarde fue pirateado por Ritter [13] .

En 1995, se propusieron dos nuevos enfoques al problema a la vez. El primero, basado en ecuaciones diofánticas , se debe a Lin Zhuxing , Zhang Zhencheng y Li Jia Tong . Casi de inmediato, Lai Qisong y Blackburn, Murphy, Sean y S. G. Paterson demostraron de forma independiente que este criptosistema no es seguro.

Segundo enfoque, basado en el problema multiplicativo de la mochila, fue propuesto por David Naccache y Jacques Stern [14] . Nakkashe y Stern ofrecieron DM 1024 a alguien que descifró con éxito su esquema criptográfico, pero no había información de que alguien hubiera recibido esta recompensa todavía (a partir de 2001) [5] .

En 1996, Kunikatsu Kobayashi y Masaki Kimura propusieron un criptosistema de mochila mejorado basado en un nuevo concepto, donde el remitente puede elegir una clave de cifrado de un conjunto completo de claves. Dos años más tarde, Hidenori Kuwakado y Hatsukazu Tanaka demostraron que el sistema era potencialmente inseguro [15] .

La última versión del algoritmo fue propuesta por B. Shor y R. L. Rivest en 2006. En 2002, el algoritmo Chor-Rivest se consideró seguro [3] .

En 2015, se informó que Nathan Hamlin y William Webb de la Universidad Estatal de Washington habían creado un algoritmo de mochila sin las deficiencias de las implementaciones anteriores [16] .

Desde entonces, se han propuesto muchos algoritmos de clave pública que no se basan en sistemas de mochila. Los más famosos son: RSA , EIGamal y Rabin . Se pueden utilizar tanto para el cifrado como para las firmas digitales. Sin embargo, son lentos y no son adecuados para el cifrado/descifrado rápido de grandes volúmenes de mensajes. La solución a este problema son los criptosistemas híbridos, los mensajes se cifran con un algoritmo simétrico rápido con una clave aleatoria, y el algoritmo de clave pública se utiliza para cifrar la clave aleatoria (de sesión).

Planteamiento del problema

El problema de la mochila es el siguiente: dado un conjunto de enteros positivos distintos. Sea un número que también sea entero y positivo. La tarea es encontrar un conjunto tal que sumen exactamente . Está claro que no siempre existe una solución a este problema. $A=(a_{1},...,a_{n})$ $norte$ $k$ $ai}$ $k$

De acuerdo con la definición de sistemas de clave pública, debe tener dos claves para cifrar/descifrar con éxito. El destinatario legítimo del mensaje conoce la clave secreta A, mientras que el remitente solo tiene la clave pública B. ¿Cómo se puede evitar que un atacante descifre el mensaje si conoce la clave pública? La respuesta es simple, la clave pública debe derivarse de la clave privada usando alguna transformación f que tenga las siguientes dos propiedades [17] :

Es fácil de calcular sabiendo ${\ estilo de visualización B = f (A)}$ $A$
Determinar , conocer , es probablemente una tarea difícil. ${\ estilo de visualización A = f ^ {-1} (B)}$ $B$

Como problemas difíciles, se suelen considerar los problemas NP-completos, por lo que el problema de la mochila es adecuado para construir sistemas de clave pública.

Cifrado con el problema de la mochila

El mensaje está encriptado como una solución a un conjunto de problemas de mochila [2] .

Def. Un vector mochila es un conjunto ordenado de n elementos [18] .

A=(a_{1},...,a_{n})

Para cifrar el texto plano en representación binaria, se divide en bloques de longitud (por ejemplo, corresponde a 5 artículos en una mochila). Se cree que uno indica la presencia de un artículo en la mochila y cero indica su ausencia. Hay dos formas de cifrar: $norte$ $(11100)$

1) El cifrado del mensaje se obtiene elevando los elementos del vector mochila a la potencia de los bits del mensaje cifrado que les corresponde y multiplicando aún más los resultados, es decir, si , y el mensaje , entonces el cifrado será el número . Este método se llama multiplicativo [5] . ${\ estilo de visualización A = (2,3,5)}$ ${\ estilo de visualización (100)}$ ${\ estilo de visualización 2^{1}*3^{0}*5^{0}=2}$

2) El cifrado del mensaje se obtiene multiplicando los elementos del vector mochila por el bit correspondiente del mensaje cifrado y luego sumando los resultados, es decir, si , y el mensaje , entonces el cifrado será el número . Este método se llama aditivo [5] . ${\ estilo de visualización A = (2,3,5)}$ ${\ estilo de visualización (100)}$ ${\ estilo de visualización 2*1+3*0+5*0=2}$

Un ejemplo de un texto cifrado obtenido por un algoritmo aditivo.

Sea dado un vector mochila Α = (3 4 6 7 10 11) con longitud n = 6.

Texto sin formato	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
cosas en una mochila	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
texto cifrado	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	once

Para un Α dado, todos los criptosistemas son números que no superan 41, el peso total de todos los elementos del vector mochila. Solo hay un criptotexto para cada texto sin formato.

La complejidad del cifrado radica en el hecho de que hay dos problemas de la mochila: "fácil" y "difícil". Un problema "fácil" se puede resolver en tiempo lineal, uno "difícil" no. La clave pública es un problema "difícil" porque es fácil de usar para cifrar e imposible de descifrar un mensaje. La clave privada es un problema "fácil", ya que facilita el descifrado del mensaje. En ausencia de una clave privada, el problema de la mochila “dura” debe resolverse. Merkle y Hellman, utilizando aritmética modular, desarrollaron una forma de transformar una mochila "fácil" en una "difícil" [2] .

Problema "fácil"

Para algunos vectores Α, el problema de la mochila se resuelve fácilmente. Los vectores de supercrecimiento tienen esta propiedad [2] .

Def. Un vector de mochila se llama supercrecimiento si para , es decir, cada miembro de la secuencia es mayor que la suma de los anteriores [18] .

A=(a_{1},...,a_{n})

{\displaystyle \sum _{i=1}^{j-1}a_{i}<a_{j))

{\ estilo de visualización j = 2,..., n}

Ejemplo

Deje que el peso total de la mochila y el vector de la mochila se den como supercrecientes . ${\ estilo de visualización P = 70}$ ${\ estilo de visualización A = (2,3,6,13,27,52)}$

Para este vector mochila, el algoritmo para resolver el problema de la mochila es simple. Se toma el peso más grande, 52. Como 52 < 70, se coloca el artículo correspondiente en la mochila. El espacio libre en la mochila se volvió igual a 70 - 52 = 18. A continuación, tome un artículo con un peso de 27. Como 27 > 18, este artículo no entrará en la mochila. El tercer artículo con un peso de 13 < 18 cabrá en la mochila, dejando espacio libre para 5. El siguiente artículo con un peso de 6 no cabrá. De manera similar, los artículos con pesos 2 y 3 se colocan en una mochila. El peso residual de la mochila se ha convertido en 0, ¡se ha encontrado la solución!

El problema "difícil"

Una mochila normal no tiene un vector de mochila supercreciente A. La única forma de resolver este problema es probar todas las posibles hasta encontrar la solución correcta. El algoritmo más rápido tiene una dependencia exponencial del número de elementos [2] .

Un criptosistema de clave pública basado en el problema de la mochila

Como antes, el vector A es la clave secreta y el vector B es la clave pública.

Crear una clave pública a partir de una privada

Para números enteros y denote . $X$ ${\ estilo de visualización m \ geq 2}$ ${\ estilo de visualización (x, modm) = x-[x/m] m}$

Sea un vector mochila supercreciente. Introduzcamos un número entero y un número natural tal que el máximo común divisor sea . $A=(a_{1},...,a_{n})$ $m>\sum_{i=1}^{n}a_{i}$ ${\ estilo de visualización t<m}$ ${\ estilo de visualización (t, m) = 1}$

Def. Si tal que para , entonces decimos que se obtiene de la multiplicación modular fuerte [18] .

{\ estilo de visualización B = (b_{1},...,b_{n})}

b_{i}=(ta_{i},modm)

{\ estilo de visualización i = 1, .., n}

B

A

El creador del criptosistema elige los parámetros para que A sea supercreciente y B se obtenga de A mediante una fuerte multiplicación modular con respecto a m y t. ${\ estilo de visualización A, B, t, m}$

Lema válido [19] : Sea A un vector supercreciente, y B se obtiene de A por multiplicación modular fuerte con respecto a m y t. Supongamos que u = 1/t, β es un número natural arbitrario y α =(uβ,modm). Entonces es cierto que:

El problema de la mochila con datos de entrada (A,α) tiene solución en tiempo lineal, y si existe una solución, entonces es única;
El problema de la mochila con datos de entrada (B,β) tiene como máximo una solución;
Si hay una solución de entrada (B,β), entonces es la misma que la única solución de entrada (A,α).

Ejemplo

Crear el vector B a partir del vector A [18] .

Deje que se dé un vector de supercrecimiento (clave secreta) con . La suma de sus componentes es 55 205. Elija , y . Entonces se cumple la condición. ${\ estilo de visualización A = (103,107,211,430,863,1718,3449,6907,13807,27610)}$ $n=10$ ${\ estilo de visualización m = 55207}$ ${\ estilo de visualización t = 25236}$ ${\ estilo de visualización (t, m) = 1}$

Se encuentra de acuerdo con la fórmula . En este caso: $t^{-1}módulo$ ${\ estilo de visualización (tu) modm = 1}$

1061 * 25236 - 1= 485 * 55207

Por lo tanto ${\ estilo de visualización t ^ {-1} = u = 1061}$

La clave pública B se calcula mediante y α =(uβ,modm). por ejemplo, para $b_{i}=(ta_{i},modm)$ ${\displaystyle a_{1},a_{6},a_{10))$

$b_{1}=103*25236=4579+47*55207=4579$ y α1 = 1061 * 4579 = 103 + 88 * 55 207 = 103,

$b_{6}=1718*25236=17953+785*55207=17953$ y α6 = 1061 * 17 953 = 1718 + 345 * 55 207 = 1718,

$b_{10}=27610*25236=53620+12620*55207=53620$ y α10 = 1061 * 53 620 = 27 610 + 1030 * 55 207 = 27 610

Habiendo hecho cálculos similares para los elementos restantes, se obtiene un vector ${\ estilo de pantalla B = (4579,50316,24924,30908,27110,17953,32732,16553,22075,53620)}$

Cifrado

Aplicar la clave pública B y cifrar el mensaje: LOS DIOSES DE LA MUERTE SOLO COMEN MANZANAS

Primero se utiliza la codificación numérica, al espacio se le asigna el valor 0, a las letras de la A a la Z se les asigna el valor 1 a 26. Los códigos numéricos se expresan en conjuntos binarios. Dado que el vector B tiene una longitud de 10, se puede utilizar para cifrar bloques de dos letras a la vez. El código de bloque, como antes, se obtiene sumando los pesos de los artículos incluidos en la mochila. $bi}$

bloque de texto fuente	código binario	código de bloque
Delaware	00100 00101	95097
A	00001 10100	61616
H	01000 00000	50316
VAMOS	00111 01111	207922
D.S.	00100 10011	118572
mi	00000 00101	70173
A	00001 10100	61616
O	00000 01111	124980
Países Bajos	01110 01100	155433
Y	11001 00000	82005
punto de acceso	00001 10000	45063
ES	10000 01100	53864
ES	00101 10011	149480

Descifrado

Vamos a descifrar el primer número 95 097. Vale la pena señalar que

1061*95097 = 1827*55207 + 34728

Se considera el problema de la mochila (A.34728). La solución se obtiene viendo el vector mochila A de derecha a izquierda. Cuando el número de la columna de la izquierda no es menor que el componente A actualmente visualizado, se escribe 1 y el nuevo número de la columna de la izquierda se obtiene restando el componente del número anterior. De lo contrario, se escribe 0 y el número de la columna de la izquierda no cambia. El resultado se muestra en la tabla:

Número	Componente A	Símbolo
34728	27610	una
7118	13807	0
7118	6907	una
211	3449	0
211	1718	0
211	863	0
211	430	0
211	211	una
0	107	0
0	103	0

Leer la columna de la derecha de abajo hacia arriba da como resultado el vector binario 00100 00101, es decir, DE.

Supongamos que tratamos de actuar en orden inverso. El cifrado se realizaría utilizando el vector A y se obtendría un determinado número a. Pero entonces el par (B,a) no tenía solución, ya que la igualdad habitual de los números no se puede deducir de su módulo de igualdad.

Seguridad

Mochila sistemas de seguridad

Para vectores de mochila pequeña, el problema de la mochila es fácil de resolver incluso a mano. Una mochila real debe contener una gran cantidad de elementos. Abrir una mochila de este tipo con fuerza bruta, es decir, revienta, será una tarea difícil (imposible). Sin embargo, los sistemas de mochila no son seguros para el criptoanálisis . Shamir y Zippel ( ing. Zippel ) descubrieron que conociendo los números ( "escapatoria secreta" ), se puede restaurar un vector supercreciente a partir de un vector abierto normal [3] . Lo importante es que los números (el "par secreto") no tienen que ser los mismos que se usaron cuando el usuario legal creó el sistema. Es suficiente encontrar cualquier par tal que nos dé un vector supercreciente [20] . ${\ estilo de visualización t, t ^ {-1}, m}$ $A$ $B$ ${\ estilo de visualización t, m}$ ${\ estilo de visualización (t', m')}$ $B*(t'modm')$

Cómo buscar una escapatoria secreta

Problema: se sabe que se utiliza un vector de mochila como clave pública. Se obtiene a partir de A, un vector supercreciente, por multiplicación modular fuerte con respecto al módulo my el número t. Necesitamos encontrar A, t, m que no conocemos, o más bien my (podemos calcular A a partir de ellos). Conociéndolos, uno puede descifrar el criptotexto [21] . ${\ estilo de visualización B = (b_{1},...,b_{n})}$ ${\ estilo de visualización t ^ {-1} = u}$

Encontrar el par secreto

El enfoque que se describe a continuación fue propuesto por A. Shamir . El algoritmo resultante se ejecutará en tiempo polinomial. Sin embargo, se debe tener cuidado al elegir el tamaño del vector B con respecto al cual el algoritmo es polinomial. Vale la pena recordar que el tamaño del vector B depende del número de componentes n y del tamaño de . Por lo tanto, existen restricciones en su elección. $bi}$

Fijamos la constante de proporcionalidad y los componentes del vector supercreciente A, que consta de bits. Dado que el dígito más significativo en cada uno de los componentes es uno, entonces A es supercreciente y m se elige para que sea mayor que la suma de los componentes del vector mochila A [20] . $d>1$ $a_{i},i=[1,n]$ ${\ estilo de visualización [dn]-1-n+i}$

Para construir un algoritmo, no es necesario buscar la u y la m realmente utilizadas para el cifrado. Cualquier par (u, m) servirá, llamémoslo un par secreto , satisfaciendo las restricciones de la multiplicación modular fuerte con respecto a B, que el vector A está supercreciendo como resultado de esta multiplicación, y m es mayor que la suma de sus componentes Después de encontrar al menos un par secreto, aplicamos el lema y comenzamos el descifrado. Su existencia es obvia, ya que el creador del criptosistema usó uno de esos pares al cifrar.

Para mayor claridad, construimos gráficas de funciones . Estos son segmentos de línea recta con puntos de discontinuidad . ${\ Displaystyle b_ {i} u}$ ${\ estilo de visualización (módulo)}$ ${\displaystyle u=pm/b_{i))$ ${\ estilo de visualización p = 1,2,...}$

Recordando que escribiremos : $b_{i}=(ta_{i},modm)$ ${\ estilo de visualización t ^ {-1} = u}$

$(b_{1}u,modm)=a_{1}$ , donde es el factor inverso deseado, es el primer componente del vector , es, por suposición, muy pequeño en comparación con . Esto significa que el valor está cerca del mínimo de la función . $tu$ $un_{1}$ $A$ $metro$ $tu$ $b_{1}$

Para , el valor está cerca del mínimo de la función . Entonces los dos mínimos de las funciones y están cerca uno del otro. Así, también se pueden considerar el resto de las curvas en diente de sierra. Está claro que los mínimos de todas estas curvas están cerca unos de otros. Es posible construir un pequeño intervalo que contenga los "puntos de acumulación" de los mínimos de las curvas de diente de sierra [22] . En base a este pequeño intervalo, también se encuentra el valor del par secreto. $(b_{2}u,modm)=a_{2}$ $tu$ $b_{2}$ $b_{1}$ $b_{2}$ $norte$ $tu$

Como no conocemos el valor del módulo, cambiaremos la escala de la figura para que sea igual a 1 (divide todas las longitudes entre ). $metro$ $metro$ $metro$

Algoritmo para encontrar un par secreto:

1) Encontrar candidatos para el entero tal que el enésimo mínimo de la función sea el punto de acumulación deseado. $pags$ $pags$ $b_{1}$

Para que el número de candidatos no sea demasiado grande, introducimos un parámetro fijo : el número máximo de candidatos permitidos. $r$

En la primera parte del algoritmo, no es necesario considerar todo a la vez , se debe introducir un parámetro y considerar el componente. ${\displaystyle b_{2},...,b_{n))$ ${\ estilo de visualización s<n}$ $s$

$p/b_{1}$ -coordenada del -ésimo mínimo en la curva . $tu$ $pags$ $b_{1}$

La condición para la proximidad de los mínimos de las curvas y puede escribirse como las siguientes desigualdades: $b_{1}$ $b_{2}$

$-e<p/b_{1}-q/b_{2}<e$ ,

$1\leq p\leq b_{1}-1$ , ${\ estilo de visualización 1 \ leq q \ leq b_{2}-1}$

Multiplica la primera desigualdad por : ${\ Displaystyle b_{1}b_{2))$

$-E<pb_{2}-qb_{1}<E$ .

En total tales desigualdades , una para cada ${\ estilo de visualización s-1}$ $b$

Entonces, la primera parte del algoritmo da todos los naturales para los cuales hay naturales tales que se satisfacen todas las desigualdades. $pags$ $q$ ${\ estilo de visualización s-1}$

2) Verificación secuencial de cada uno de los candidatos.

En la segunda parte del algoritmo, se comprueban todos . El candidato será rechazado si para algunos no existe un mínimo de la curva que se encuentre cerca del -ésimo mínimo de la curva . ${\ estilo de visualización i = [2, n]}$ $pags$ $i$ $bi}$ $pags$ $b_{1}$

arreglar _ Organice en orden ascendente todos los puntos de corte en el intervalo . Tomemos dos puntos adyacentes de la lista ordenada y . En el intervalo formado por ellos , cada curva es un segmento de línea recta (la ecuación describe estos segmentos). $pags$ ${\ estilo de visualización [p/b_{1},(p+1)/b_{1}]}$ $x_{yo}$ ${\ estilo de visualización x_ {i} +1}$ ${\ estilo de visualización [x_{i},x_{i}+1]}$ $bi}$ ${\displaystyle b_{i}u-const_{i}^{j))$

Con base en lo anterior, escribimos el sistema de desigualdades:

$x_{j}\leq u\leq x_{j}+1$

$\sum _{i=1}^{n}(b_{i}u-const_{i}^{j})<1$

$(b_{1}u-const_{1}^{j})+(b_{2}u-const_{2}^{j})+...+(b_{i}-1u-const_ {i-1}^{j})<(b_{i}u-const_{i}^{j})$ ${\ estilo de visualización i = [2, n]}$ - condición de sobrecrecimiento

Para dos números y para formar un par secreto, es necesario y suficiente que pertenezca al intervalo así construido para algún par . , el candidato de la primera parte del algoritmo y el índice de puntos de la lista ordenada de puntos correspondientes a los dados . $tu$ $metro$ ${\ estilo de visualización u/m}$ ${\ estilo de visualización (p, j)}$ $pags$ $j$ $pags$

La búsqueda finalizará cuando se encuentre un intervalo que no esté vacío . ${\ estilo de visualización [x_{i},x_{i}+1]}$

Ejemplo [23] .

Deje que la clave pública tenga tres componentes. ${\ estilo de visualización B = (7,3,2)}$

1) De acuerdo con las desigualdades anteriores:

${\ estilo de visualización -E<3p-7q<E}$ ,

${\ estilo de visualización -E <2p-7q <E}$

${\ estilo de visualización 1 \ leq p \ leq 6}$ , , . ${\ estilo de visualización 1 \ leq q \ leq 2}$ ${\ estilo de visualización r = 1}$

La tabla enumera los valores más pequeños tales que las desigualdades se mantienen: $mi$

pags	una	2	3	cuatro	5	6
mi	5	3	2	2	3	5

2) Se puede ver que todos los valores son candidatos aptos (en el caso general, puede que no sea así). Por lo tanto, dividimos el intervalo en subintervalos: de modo que las tres curvas sean segmentos de línea recta en cada intervalo reducido. $pags$ $(0.1)$ $(0.1/7),(1/7.2/7),(2/7.1/3),(1/3.3/7),(3/7.1/2),(1/2.4/7),( 4/7.2/3),(2/3.5/7),(5/7.6/7),(6/7.1)$ $bi}$ $(b_{i}u-const_{i}^{j})$

Escribamos las desigualdades:

${\ estilo de visualización (7u-i')+(3u-i'')+(2u-i''')<1}$

$7u-i'<3u-i''$

$(7u-i')+(3u-i'')<(2u-i''')$

Las constantes cambian dentro de , , dependiendo de la elección del intervalo. ${\ estilo de visualización 0 \ leq i \ leq 6}$ $0\leq i'\leq 2$ $0\leq i'''\leq 1$

Usando la notación , , reescribimos las desigualdades en una forma más simple: $i=1+i'+i''+i'''$ $j=i'-i''$ $k=i'+i''-i'''$

${\ estilo de visualización 12u <i, 4u <j, 8u <k}$

Recolectemos en la tabla todos los valores de las constantes para diferentes intervalos:

Intervalo	1/7	2/7	1/3	3/7	1/2	4/7	2/3	5/7	6/7	una
i'	0	una	2	2	3	3	cuatro	cuatro	5	6
i	0	0	0	una	una	una	una	2	2	2
i	0	0	0	0	0	una	una	una	una	una
i	una	2	3	cuatro	5	6	7	ocho	9	diez
j	0	una	2	una	2	2	3	2	3	cuatro
k	0	una	2	3	cuatro	3	cuatro	5	6	7
12u	PARTE	PARTE	NO	NO	NO	NO	PARTE	NO	PARTE	NO
4u<j	NO	PARTE	SE SENTÓ	NO	SE SENTÓ	NO	SE SENTÓ	NO	PARTE	SE SENTÓ
8u<k	NO	NO	NO	PARTE	SE SENTÓ	NO	NO	NO	PARTE	PARTE

Las últimas tres líneas indican si cada una de las desigualdades es verdadera o no: SAT - verdadero, PARTE-parcialmente verdadero (aparece cuando la desigualdad es verdadera en el lado derecho del subintervalo), NOT - no es verdadero (aparece cuando la desigualdad no es verdadera) verdadero en el lado izquierdo del subintervalo).

Un intervalo genera un par secreto si y solo si los tres SAT o PART están en la columna. El único intervalo de este tipo Al elegir un número del intervalo, por ejemplo (es decir , ), obtenemos un vector de supercrecimiento . ${\ estilo de visualización (5/7, 3/4)}$ ${\ estilo de visualización 8/11}$ ${\ estilo de visualización m = 11}$ ${\ estilo de visualización A = (1,2,5)}$

Variantes del problema de la mochila en criptografía

1) Mochila Merkle-Hellman ( eng. Merkle-Hellman Cryptosystem ).

La clave pública A es un vector supercreciente, la clave secreta B se obtiene de A mediante una fuerte multiplicación modular.

2) Mochila de Graham-Shamir ( ing. Graham-Shamir Cryptosystem ) [5] .

La clave pública A es un vector supercreciente. Sus elementos están escritos en representación de bits. A continuación, se generan números aleatorios, llamados ruido. Su representación de bits se suma a los bits del vector mochila de la izquierda, es decir, en el bit más significativo.

Digamos que elegimos vectores . Agregamos prefijos de números seleccionados al azar en él: ${\ estilo de visualización A = (1,3,5)}$

representación binaria	con prefijo aleatorio
1=001	101 001 = 41
3=011	111 011 = 59
5 = 101	100 101 = 37

El vector mochila resultante no tiene la propiedad supercreciente. Por lo tanto, agregar ruido aleatorio oculta la propiedad de crecimiento excesivo del vector A original y el circuito se vuelve más seguro [24] . ${\ estilo de visualización (41,59,37)}$

3) Morii-Kasahara Backpack ( eng. Morii-Kasahara Cryptosystem ) [10]

El esquema es similar al esquema de Merkle-Hellman, pero utiliza un método de cifrado multiplicativo tanto para la clave pública como para la secreta.

Vamos vector . Elegimos , un número primo (en este esquema ) y , tal que . La clave secreta B se obtiene de A mediante la fórmula , es decir . Deje que el mensaje sea encriptado , luego el cifrado . ${\ estilo de visualización A = (5,6,7)}$ ${\ estilo de visualización m = 211> 5 * 6 * 7 = 210}$ ${\ estilo de visualización p = 211}$ ${\ estilo de visualización p = m}$ ${\ estilo de visualización e = 19}$ $mcd(e,p-1)mod(p-1)=1$ $b_{i}=a_{i}^{e}modp$ ${\ estilo de visualización B = (114,66,85)}$ ${\ estilo de visualización (100)}$ ${\ estilo de visualización 114^{1}*66^{0}*85^{0}=144mod211}$

4) Mochila Goodman -McAuley Cryptosystem [ 8] .

Como en el primer esquema de la mochila de Goodman-McCauley, se utiliza la multiplicación modular para obtener la clave pública a partir de la secreta, pero la clave secreta no es un vector supercreciente. El esquema se basa en la complejidad de la factorización de enteros, por lo que es similar al criptosistema RSA.

5) Mochila Nakashe-Stern ( ing. Naccache-Stern Cryptosystem ) [14] .

Este esquema combina dos métodos: la mochila Merkle-Hellman y el algoritmo Polyg-Hellman . Dado un número primo , S es un subconjunto ( ing. producto de subconjunto ) y un vector de mochila , donde todos son números relativamente primos. Necesitamos encontrar un vector binario tal que $pags$ $A=(a_{1},a_{2},...a_{n})$ $ai}$ ${\ estilo de visualización x = (x_{1},...,x_{n})}$ $\displaystyle \prod _{i=1}^{n}a_{i}^{x_{i}}mpdp=S$

6) Mochila Shor-Rivest ( ing. Chor-Rivest ) [24] [25]

Basado en álgebra en campos finitos (campos de Galois) . Deje que la clave pública A consista en elementos del subcampo del campo , es decir . La clave secreta consta de los siguientes elementos: ${\ Displaystyle q = p ^ {h}}$ $FG(p)$ $FG(q)$ $(a_{1},a_{2},...a_{p})=GF(p)\in GF(q)$

elemento de con grado algebraico $t$ $FG(q)$ $h$
generador de $gramo$ $GF^{*}(q)$
todo de $d$ ${\ estilo de visualización \ mathbb {Z} (q-1)}$

Entonces la clave pública B consta de los elementos [5] . $b_{i}=d+\log _{g}(t+a_{i})mod(q-1)$

El futuro de los sistemas de mochila

Hoy en día, la principal atención de los criptógrafos se centra en los criptosistemas basados en factorización de enteros , logaritmos discretos y curvas elípticas . Sin embargo, la investigación sobre los sistemas de mochila continúa, pero tales criptosistemas no son populares y no inspiran confianza, dadas las fallas de los algoritmos anteriores. Si se puede crear un algoritmo que explote completamente la dificultad del problema de la mochila (NP-completitud), con alta densidad y con lagunas secretas difíciles de descubrir, entonces este será un sistema mejor que los sistemas basados en la factorización de enteros y el logaritmo discreto (su No se ha probado la integridad de NP). Además, este sistema será rápido, lo que significa que podrá competir en velocidad con los sistemas clásicos de clave pública [5] .

Para un peso de mochila, una iteración del algoritmo Merkle-Hellman puede ser más de 100 veces más rápida que RSA (con un módulo de 500 bits) [26] . ${\ estilo de visualización n = 100}$

Notas

↑ Diffie W. , Hellman M. E. Nuevas direcciones en criptografía // IEEE Trans . inf. Teoría / F. Kschischang - IEEE , 1976. - Vol. 22, edición. 6.- Pág. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
↑ 1 2 3 4 5 Schnaer, 2002 , pág. 19.1.
↑ 1 2 3 4 5 Schnaer, 2002 , pág. 19.2.
↑ Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Seguridad de la información : libro de texto - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
↑ 1 2 3 4 5 6 7 8 Kin Ming Lai. Criptosistemas de mochila: el pasado y el futuro . — 2001.
↑ . Matriz matemática (inglés) . — 2001.
↑ Publicaciones ._ _ (enlace no disponible)
↑ 1 2 Un nuevo criptosistema de clave pública de mochila con trampilla . — saltador.
↑ Jacques Stern- Artículo Wiki . — saltador.
↑ 1 2 Masakatu Morii, Masao Kasahara. Nuevo criptosistema de clave pública utilizando logaritmos discretos sobre GF(p ) . — saltador.
↑ Shinya Kiuchi, Yasuyuki Murakami, Masao Kasahara. Nuevos criptosistemas multiplicativos de clave pública tipo mochila .
↑ Hussain Ali Hussain, Jafar Wadi Abdul Sada , Klipha SM Nuevo criptosistema de clave pública de mochila multietapa . Archivado desde el original el 26 de diciembre de 2014.
↑ Harald Ritter. Breaking Knapsack Cryptosystems por l-Norm Enumeration . Archivado desde el original el 31 de marzo de 2012.
↑ 1 2 Davis Naccache, Jacques Stern. Un nuevo criptosistema de clave pública . — 2006.
↑ Sobre la seguridad de la mochila del criptosistema mejorado .
↑ Se ha desarrollado un algoritmo de protección de datos que incluso las computadoras cuánticas no pueden descifrar . Consultado el 2 de noviembre de 2015. Archivado desde el original el 17 de agosto de 2015. (indefinido)
↑ Salomaa, 1990 , pág. 76.
↑ 1 2 3 4 Salomaa, 1990 , pág. 103.
↑ Salomaa, 1990 , pág. 104.
↑ 1 2 Salomaa, 1990 , pág. 113.
↑ Salomaa, 1990 , pág. 112.
↑ Salomaa, 1990 , pág. 114.
↑ Salomaa, 1990 , pág. 117.
↑ 1 2 B. Chor, R. L. Rivest. Un criptosistema de clave pública tipo mochila basado en aritmética en campos finitos . — 1988.
↑ Serge Vaudenay. Criptoanálisis del criptosistema Chor-Rivest . (enlace no disponible)
↑ AM Odlyzko. El auge y la caída de los criptosistemas de mochila .

Literatura

en ruso

Algoritmos de Levitin A. V. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 160-163. — 576 pág. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis = Introducción a los Algoritmos. - 2do. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Roberto Sedwick . Algoritmos fundamentales en C++. Partes 1-4. Análisis. Estructuras de datos. Clasificación. Buscar = Algoritmos en C++. Partes 1-4. fundamentos estructuras de datos. Clasificación. Buscando. - 3ro. - Rusia, San Petersburgo: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Problemas aplicados de teoría de grafos. - M. , 1974. - 232 p.
V. N. Burkov, D. A. Novikov. Elementos de Teoría de Grafos . - 2001. - S. 28.
S.Okulov. Programación en algoritmos. - 2007. - S. 383.
B. Schneier. Criptografía aplicada . - 2do. - 2002. Archivado el 28 de febrero de 2014 en Wayback Machine .
A. Salomaa. Criptografía de clave pública = Criptografía de clave pública. - Springer-Verlag, 1990. - S. 102-150. Archivado el 19 de noviembre de 2011 en Wayback Machine .
Koblitz N. Curso de teoría de números y criptografía - 2ª edición - M. : Editorial científica TVP , 2001. - 254 p. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5

en inglés

Silvano Martelo, Paolo Toth. Problemas con la mochila. - Wiley, 1990. - 306 p.
David Pisanger. Problemas con la mochila . - 1995. Archivado el 22 de diciembre de 2012 en Wayback Machine .
Hans Kellerer, Ulrich Pferschy, David Pisinger. Problemas con la mochila. — 1995.

Enlaces

Denis Alekseev. Algoritmo de mochila . Yandex.Gente ._ _ Fecha de acceso: 6 de diciembre de 2012. Archivado desde el original el 7 de enero de 2013. (Ruso)
Mijaíl Chegodar. El uso de la criptografía en materia de protección de datos, tomando como ejemplo un sistema de cifrado de mochila . Centro de Información Subterráneo. Recuperado: 6 de diciembre de 2012. (Ruso)

El problema de la mochila
Aplicaciones	Problema de la mochila en criptografía Tarea de corte
Criptosistemas basados en el problema de la mochila	Merkla-Hellman Naccasha - popa Graham - Shamira
Además	Lista de tareas sobre la mochila