PDF de programación - Capítulo 13 Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 13

Cifrado Asimétrico con Mochilas

Seguridad Informática y Criptografía

Ultima actualización del archivo: 01/03/06
Este archivo tiene: 30 diapositivas

v 4.1

Material Docente de
Libre Distribución

Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid

Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.

Curso de Seguridad Informática y Criptografía © JRA

Tema 13: Cifrado Asimétrico con Mochilas

Página 592

El problema de la mochila

El problema matemático de la mochila,
referido ahora a números y no a los
elementos físicos que puedan entrar en
ella, se plantea como sigue:

Dada la siguiente secuencia de m números enteros
positivos S = {S1, S2, S3, ..., Sm-2, Sm-1, Sm} y un valor
u objetivo T, se pide encontrar un subconjunto de S
SS = {Sa, Sb, ..., Sj} que cumpla con ese objetivo T:

T = Σ SS = Sa + Sb + ... + Sj

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 593

Solución al problema de la mochila

Si los elementos de la mochila son números grandes, no
están ordenados y no siguen una distribución supercreciente
-en este tipo de distribución el elemento iésimo Si de la
mochila es mayor que la suma de todos sus antecesores-, la
resolución de este problema es de tipo no polinomial.

Se trata de encontrar los vectores Vi de 0s y 1s de

forma que:
Σ Si∗Vi = T
i

Si se cumple esta relación, la mochila tiene solución.
En caso contrario, no existirá solución.

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Página 594

Un ejemplo del problema de la mochila

Tenemos la mochila S = {20, 5, 7, 36, 13, 2} con m = 6 y el
valor T = 35. Se pide encontrar una solución, si es que ésta
existe, en una única vuelta. En este momento no importa
que los valores de la mochila no estén ordenados.
SOLUCIÓN: Sin hacer ningún cálculo mental, podemos
recorrer todos los valores (se puede descartar el elemento S4
pues es mayor que el objetivo T) de la mochila S, bien de
izquierda a derecha o al revés (da igual el sentido elegido) y
restaremos el elemento iésimo si es menor que el objetivo T
en esa etapa del algoritmo, como se indica:

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 595

Solución al ejemplo de la mochila

S = {S1, S2, S3, S4, S5, S6} = {20, 5, 7, 36, 13, 2} T = 35

S1 = 20 ¿Es menor que objetivo T = 35? Sí ⇒ T = 35-20 = 15
S2 = 5 ¿Es menor que objetivo T = 15? Sí ⇒ T = 15-5 = 10
S3 = 7 ¿Es menor que objetivo T = 10? Sí ⇒ T = 10-7 = 3
S4 = 36 ¿Es menor que objetivo T = 3? No ⇒ T = 3
S5 = 13 ¿Es menor que objetivo T = 3? No ⇒ T = 3
S6 = 2 ¿Es menor que objetivo T = 3? Sí ⇒ T = 3-2 = 1 ≠ 0

Se ha recorrido toda la mochila y no se ha encontrado solución.
En cambio sí existe una solución:
SS = {S1+S5+S6} = 20+13+2 = 35

Vi = [1,0,0,0,1,1]

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Página 596

¿Puede haber soluciones múltiples?

Si para la misma mochila S = {20, 5, 7, 36, 13, 2} buscamos
ahora el valor T = 27, encontramos tres soluciones válidas:

SS1 = {S1+S3} = 20+7 SS2 = {S1+S2+S6} = 20+5+2

SS3 = {S2+S3+S5+S6} = 5+7+13+2

Esto sería inadmisible en un sistema de cifra puesto que el
resultado de una operación de descifrado debe ser única ya
que proviene de un único mensaje. La solución será el uso
de las denominadas mochilas simples en que la solución al
problema de la mochila, si existe, es única.



© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 597

Mochila simple o supercreciente

k-1

j = 1

Sk > Σ Sj

Una mochila es simple o
supercreciente si el elemento Sk
es mayor que la suma de los
elementos que le anteceden:
Por ejemplo, la mochila S = {2, 3, 7, 13, 28, 55, 110, 221}
con m = 8 elementos es supercreciente y la solución para un
objetivo T = 148 es única: Vi = [S2+S3+S5+S7].
Para resolver cualquier valor T válido para esta mochila,
ésta se recorre de derecha a izquierda (desde el valor mayor
al menor) una sola vez con el algoritmo ya visto.
Compruebe que para T = 289, 196 y 353 los vectores son
V1 = 00010101; V2 = 01001110; V3 = 10110011.

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Página 598

Operación de cifra con mochila simple

Se representa la información en binario y se pasan los bits
por la mochila. Los bits 1s incluyen en la suma el elemento
al que apuntan y los bits 0s no.
Con la mochila S = {2, 4, 10, 19, 40} de m = 5 elementos
cifraremos el mensaje M = ADIOS.
SOLUCIÓN: Usando código ASCII/ANSI: A = 01000001;
D = 01000100; I = 01001001; O = 01001111; S = 01010011
M = 01000 00101 00010 00100 10010 10011 11010 10011
C = (4), (10+40), (19), (10), (2+19), (2+19+40), (2+4+19), (2+19+40)

C = 4, 50, 19, 10, 21, 61, 25, 61

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 599

Descifrado con mochila simple

S = {2, 4, 10, 19, 40}
C = 4, 50, 19, 10, 21, 61, 25, 61
La operación de descifrado es elemental: pasamos por la
mochila los valores de C, encontramos el vector Vi y por
último agrupamos el resultado en grupos de 8 bits. En este
caso 4 ⇒ Vi = 01000, 50 ⇒ Vi = 00101, etc.

PROBLEMA: Es muy fácil cifrar y descifrar
pero también criptoanalizar el sistema de cifra

porque se usa una mochila simple.

Una posible solución es usar mochilas de Merkle y Hellman.

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Página 600

Mochila de Merkle y Hellman MH

• En 1978 Ralph Merkle y Martin Hellman proponen un sistema

de cifra de clave pública denominado Mochila con Trampa.

• El algoritmo se basa en crear una mochila difícil a partir de una
mochila simple de forma que el cifrado se haga con la mochila
difícil y el descifrado con la mochila simple o fácil. Se puede
pasar fácilmente de la mochila simple a la difícil o viceversa
usando una trampa.
La trampa será nuestra clave secreta.
La mochila difícil será nuestra clave pública.

http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.3.e.html



© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 601

Diseño mochila de Merkle y Hellman (1)

1. Se selecciona una mochila supercreciente de m elementos

S’ = {S1’, S2’, ..., Sm’}.

2. Se elige un entero µ (módulo de

trabajo) mayor que la suma de
los elementos de la mochila.

µ > Σ Si’

m

i = 1

más fácil:
µ ≥ 2∗Sm’

3. Se elige un entero ω primo

Se asegura
el inverso

relativo con µ.
Se recomienda que ω no tenga factores con los elementos de S’

mcd (ω,µ) = 1

4. Se multiplica S’ por ω mod µ. Si = ω∗Si’ mod µ
Obteniendo una mochila difícil S = {S1, S2, ..., Sm}

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Página 602

Diseño mochila de Merkle y Hellman (2)

5. Se calcula el inverso de ω en el cuerpo µ.

ω-1 = inv (ω,µ)

Clave privada:

µ, ω-1

Clave pública: mochila S

Esto se interpreta como
encontrar los vectores que
cumplan con un valor de T.

CIFRADO:
C = S ∗ M
como S = ω ∗ S’ mod µ
C = ω ∗ S’∗ M mod µ

DESCIFRADO:
M = ω-1 ∗ C mod µ
Entonces obtenemos:

S’∗ M

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 603

Cifrado mochila de Merkle y Hellman (1)

Se pide cifrar el mensaje codificado en ASCII M = Sol usando
la mochila simple y supercreciente S’ = {3, 5, 12, 21}.
1. Elección de µ:
2. Elección de ω:
3. Mochila S:

µ ≥ 2∗S’4 ≥ 2∗21 µ = 49
mcd (ω, µ) = 1
S = ω ∗ S’ mod µ

ω = 32 ⇒ ω-1 = 23

S1 = 32 ∗ 3 mod 49 = 96 mod 49 = 47
S2 = 32 ∗ 5 mod 49 = 160 mod 49 = 13
S3 = 32 ∗ 12 mod 49 = 384 mod 49 = 41
S4 = 32 ∗ 21 mod 49 = 672 mod 49 = 35

Clave pública: S = {47,13,41,35}

Clave privada: µ = 49, ω-1 = 23

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Página 604

Cifrado mochila de Merkle y Hellman (2)

Clave pública: S = {47,13,41,35}

Clave privada: µ = 49, ω-1 = 23

Como m = 4, cifraremos bloques de 4 bits,
convirtiendo el mensaje a su equivalente

en binario del código ASCII.

Cifrado: M = Sol = 0101 0011 0110 1111 0110 1100
C = (13+35), (41+35), (13+41), (47+13+41+35), (13+41), (47+13)

C = 48, 76, 54, 136, 54, 60

Observe que se repite el valor 54 puesto
que m = 4 sería una muy mala elección.

© Jorge Ramió Aguirre Madrid (España) 2006

Tema 13: Cifrado Asimétrico con Mochilas

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Tema 13: Cifrado Asimétrico con Mochilas

Página 605

Descifrado mochila de Merkle y Hellman

Clave pública: S = {47,13,41,35} Clave privada: µ = 49, ω-1 = 23

Cifrado: M = Sol = 0101 0011 0110 1111 0110 1100
C = 48, 76, 54, 136,