Criptosistema de mochila Merkle-Hellman

El criptosistema de mochila Merkle-Hellman , basado en el " problema de la mochila ", fue desarrollado por Ralph Merkle y Martin Hellman en 1978 [1] . Fue uno de los primeros criptosistemas de clave pública , pero resultó ser criptográficamente débil [2] y, como resultado, no ganó popularidad.

Descripción

El "problema de la mochila" es el siguiente: conociendo el subconjunto de cargas empacadas en la mochila, es fácil calcular el peso total , pero conociendo el peso, no es fácil determinar el subconjunto de cargas. Más detalladamente, sea una secuencia de n números positivos (n es el "tamaño" de la mochila)

w = ( w 1 , w 2 , …, w n ) y s .

La tarea es encontrar dicho vector binario .

x = ( x 1 , x 2 , …, x norte ), ( x yo = 0 o 1),

{\displaystyle s=\sum_{i=1}^{n}x_{i}w_{i))

Si cada número binario x está asociado con alguna letra del alfabeto, entonces podría transmitirse en forma encriptada simplemente como la suma de s . Para un conjunto arbitrario de números w i , el problema de restaurar x a partir de s es NP-difícil .

Merkle logró obtener una función inversa al número s que daría un vector x , conociendo solo cierta clave “secreta” , y ofreció $100 a alguien que pudiera descubrir el sistema de mochila Merkle-Hellman.

Considerémoslo con más detalle.

Merkle no usó una sucesión arbitraria w i , sino supercreciente, es decir, tal que

{\displaystyle w_{k+1}>\sum_{i=1}^{k}w_{i))

Es fácil ver que para tal conjunto de números la solución del problema es trivial. Para librarse de esta trivialidad, fue necesario introducir una "clave secreta", a saber, dos números: q tal que yr tal que mcd( r , q) =1. Y ahora en lugar del conjunto original de números w i usaremos los números b i =r w i mod q . En los artículos originales, Merkle recomendaba usar n del orden de 100, donde n es el número de elementos en la secuencia supercreciente (el "tamaño" de la mochila). ${\displaystyle q>\sum _{i=1}^{n}w_{i))$

Como resultado, obtenemos: clave pública - ( b 1 , b 2 , ..., b n ), clave privada - ( w 1 , w 2 , ..., w n ; q , r ).

Cifrado

– mensaje x = ( x 1 , x 2 , ..., x n ) - calcular y = segundo 1 x 1 + segundo 2 x 2 + , ..., + segundo norte x norte

Descifrado

- calcular s = yr -1 mod q - resolver el problema de s para una secuencia supercreciente ( w 1 , w 2 , ..., w n ), es decir encontrar el número binario x

El premio fue para A. Shamir después de que publicara en marzo de 1982 un informe sobre la divulgación del sistema de mochila Merkle-Hellman con una iteración. Tenga en cuenta que Shamir pudo construir una clave que no es necesariamente igual al secreto, pero le permite abrir el cifrado .

Entonces, este fue uno de los intentos fallidos, pero muy interesantes, de construir un criptosistema basado en el problema de la mochila.

Generación de claves

En el sistema Merkle-Hellman, las claves se componen de secuencias. La clave pública es una secuencia "compleja", la clave privada consiste en una secuencia "simple" o supercreciente, así como dos números adicionales: un multiplicador y un módulo, que se utilizan para convertir la secuencia supercreciente en una "compleja". uno (generación de clave pública) y transformar la suma de un subconjunto de una secuencia "compleja" en la suma de un subconjunto de una secuencia "simple" (descifrado). El último problema se resuelve en tiempo polinomial .

Cifrado

En primer lugar, el texto de origen debe representarse en forma binaria y dividirse en bloques de igual longitud que la clave pública. Además, de la secuencia que forma la clave pública, solo se seleccionan aquellos elementos que corresponden al orden 1 en la notación binaria del texto fuente, ignorando los elementos correspondientes al bit 0 . Después de eso, se agregan los elementos del subconjunto resultante. La suma resultante es el texto cifrado.

Descifrado

El descifrado es posible porque el multiplicador y el módulo utilizados para generar la clave pública a partir de la secuencia supercreciente también se utilizan para convertir el texto cifrado en la suma de los elementos correspondientes de la secuencia supercreciente. Además, usando un algoritmo codicioso simple , uno puede descifrar el mensaje usando operaciones aritméticas O(n).

Descripción matemática del algoritmo

Generación de claves

Para cifrar un mensaje de n bits, elegimos una secuencia supercreciente de n números naturales distintos de cero

w = ( w 1 , w 2 , …, w n ).

A continuación, elegimos aleatoriamente números enteros coprimos q y r tales que

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

El número q se elige de tal manera que garantice la unicidad (unicidad) del texto cifrado. Si es al menos un poco menos, puede surgir una situación en la que varios textos fuente (abiertos) correspondan a un texto cifrado. r debe ser coprimo con q , de lo contrario no tendrá un módulo q inverso multiplicativo , cuya existencia es necesaria para el descifrado.

Ahora construyamos la secuencia.

β = (β 1 , β 2 , …, β norte ),

donde cada elemento se calcula mediante la siguiente fórmula

β yo = rw yo mod q .

β será la clave pública mientras que la clave privada forma la secuencia ( w , q , r ).

Cifrado

Para cifrar un mensaje de n bits

α = (α 1 , α 2 , …, α n ),

donde está el i -ésimo bit, es decir, {0, 1}, calculamos el número c, que será el texto cifrado. $\alpha_i$ $\alpha _{i}{\boldsymbol {\in}}$

c=\sum_{i=1}^{n}\alpha_{i}\beta_{i}.

Descifrado

Para leer el texto original, el destinatario debe determinar los bits del mensaje que satisfarían la fórmula $\alpha_i$

c=\sum_{i=1}^{n}\alpha_{i}\beta_{i}.

Tal problema sería NP-difícil si β i fueran valores elegidos al azar. Sin embargo, los valores de β i se han elegido de forma que el descifrado sea una tarea sencilla, siempre que se conozca la clave privada ( w , q , r ).

La clave para encontrar el texto fuente es encontrar un número entero s que sea el inverso multiplicativo de r módulo q . Esto significa que s satisface la ecuación sr mod q = 1, que es equivalente a la existencia de un entero k tal que sr = kq + 1. Dado que r es coprimo con q , es posible encontrar s y k usando el algoritmo euclidiano extendido . A continuación, el destinatario del texto cifrado calcula

c'\equiv cs{\pmod {q)).

De aquí

c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q)).

Del hecho de que rs mod q = 1 y βi = rwi mod q

\beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q)).

Después

c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q)).

La suma de todos los w i es menor que q . Por lo tanto, el valor también está en el intervalo [0,q-1]. Así, el destinatario debe determinar a partir de la condición que $\sum_{i=1}^{n}\alpha_{i}w_{i}$ $\alpha_i$

c'=\sum_{i=1}^{n}\alpha_{i}w_{i}.

Y esto ya es una tarea fácil, ya que w es una sucesión supercreciente. Sea w k el elemento más grande de w . Si w k > c' , entonces α k = 0; si w k ≤c', entonces α k = 1. A continuación, reste el producto w k × α k de c' y repita estos pasos hasta que calculemos α.

Ejemplo

w = {2, 7, 11, 21, 42, 89, 180, 354} es una secuencia supercreciente.

Es la base para generar una clave privada. Calcular la suma de los elementos de la secuencia.

{\ estilo de visualización \ suma w = 706}

A continuación, elegimos un número primo q que supere el valor de la suma obtenida por nosotros.

q = 881

También elegimos un número r del intervalo [1,q]

r = 588

w , q y r forman una clave privada.

Para generar una clave pública, construimos una secuencia β multiplicando cada elemento de la secuencia w por r módulo q .

2 * 588 módulo 881 = 295 7 * 588 módulo 881 = 592 11 * 588 módulo 881 = 301 21 * 588 módulo 881 = 14 42 * 588 módulo 881 = 28 89 * 588 módulo 881 = 353 180 * 588 módulo 881 = 120 354 * 588 módulo 881 = 236 Obtenemos β = (295, 592, 301, 14, 28, 353, 120, 236).

La secuencia β forma la clave pública.

Deja que Alice quiera cifrar "a". Primero debe convertir "a" a binario

01100001

Luego, multiplica cada bit por el número correspondiente de la secuencia β y envía la suma de los valores al destinatario.

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

Para descifrar el mensaje, Bob multiplica el valor que recibió por el inverso multiplicativo de r módulo q .

1129 * 442 mod 881 = 372

Después de eso, Bob descompone 372 de la siguiente manera. Primero elige el elemento más grande de w que es menor que 372 y calcula su diferencia. A continuación, selecciona el siguiente elemento más grande que es menor que la diferencia resultante y repite estos pasos hasta que la diferencia se vuelve cero.

372 - 354 = 18 18 - 11 = 7 7 - 7 = 0

Los elementos que fueron seleccionados de w corresponderán a 1 en la notación binaria de la fuente.

01100001

Al volver a traducir desde la notación binaria, Bob finalmente obtiene la "a" deseada.

Véase también

Notas

↑ Ralph Merkle y Martin Hellman, Ocultar información y firmas en mochilas con trampilla, IEEE Trans. Teoría de la información , 24(5), septiembre de 1978, pp525-530.
↑ Adi Shamir, Un algoritmo de tiempo polinomial para romper el criptosistema básico de Merkle-Hellman. CRYPTO 1982, págs. 279-288. Copia archivada . Consultado el 6 de diciembre de 2005. Archivado desde el original el 24 de abril de 2005. (indefinido)

Literatura

Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .

Enlaces

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

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP