Cifradores de mochila de Merkle-Hellman

Hellman                   Merkle

•En 1978 Ralph Merkle y Martin Hellman proponen un sistema de cifra de clave pública denominado Mochila con Trampa de Merkle y Hellman.

•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.   

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 (módulo de trabajo) mayor que la suma de los elementos de la mochila.

                              m

           m > S Si’

                             i = 1                    más fácil:    m ³ 2*Sm’

3.  Se elige un entero w primo relativo con m.   mcd(w,m) = 1

Se recomienda que w no tenga factores con los elementos de S’.

4.  Se multiplica S’ por w mod m.     Si = w*Si’ mod m

5.  Se calcula el inverso de w en el cuerpo m.   w-1 = inv(w,m)

Clave privada:      m, w-1     Esto se interpreta como encontrar los

Clave pública: mochila S    vectores que cumplan con un valor de T.

CIFRADO:                            DESCIFRADO:

C = S * M                             M = w-1 * C mod m

como S = w * S’ mod m       Entonces obtenemos: 

C = w * S’* M mod m <-------------------> S’* M

Cifrado mochila de Merkle y Hellman (1)

Vamos a cifrar el mensaje M = Sol usando la mochila simple y supercreciente 

S’ = {3, 5, 12, 21}.

1. Elección de m:                     m ³ 2*S4 ³ 2*21    m = 45

2. Elección de w:                     mcd(w, m) = 1        w = 32  (w-1 = 38)

3. Mochila S:                           S = w * S’ mod m

  S1 = 32 * 3 mod 45 = 96 mod 45 = 6

  S2 = 32 * 5 mod 45 = 160 mod 45 = 25

  S3 = 32 * 12 mod 45 = 384 mod 45 = 24

  S4 = 32 * 21 mod 45 = 672 mod 45 = 42

Clave pública: S = {6,25,24,42}          Clave privada: m=45, w-1=38

Cifrado mochila de Merkle y Hellman (2)

Clave pública: S = {6,25,24,42}          Clave privada: m=45, w-1=38

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 = (25+42), (24+42), (25+24), (6+25+24+42), (25+24), (6+25)

C = 67, 66, 49, 97, 49, 31

Descifrado mochila de Merkle y Hellman

Clave pública: S = {6,25,24,42}     Clave privada: m = 45, w-1 = 38

Cifrado:   M = Sol = 0101 0011  0110 1111  0110 1100

C = (25+42), (24+42), (25+24), (6+25+24+42), (25+24), (6+25)

C = 67, 66, 49, 97, 49, 31                Como S’ = {3,5,12,21}

       Descifrado:

       38*67 mod 45=2546 mod 45 = 26     38*97 mod 45=3686 mod 45 = 41

       38*66 mod 45=2508 mod 45 = 33     38*49 mod 45=1862 mod 45 = 17

       38*49 mod 45=1862 mod 45 = 17     38*31 mod 45=1178 mod 45 = 8      

M = 0101 0011  0110 1111  0110 1100 = Sol 

Valores de diseño de mochilas M-H (1) 

Merkle y Hellman proponen los siguientes parámetros:

a)  Tamaño de la mochila m ³ 100

b)  Módulo m uniforme en el siguiente intervalo:

  Intervalo m: [22m+1+1, 22m+2-1]     Þ   2m+2 bits

  Si m = 100: todos los elementos de S son de 202 bits.

c) Valores de Si’ elegidos uniformemente en el intervalo:

  Intervalo Si’: [(2i-1-1)*2m +1, 2i-1*2m]

  Si m = 100: 1 £  S1’ £ 2100 £  S2’ £ 2101 £  S3’ £ 2102 ...

d)  Elegir un valor x en el intervalo [2, m-2]. El factor w se calcula como: w = mcd 

     (m, x)

Fortaleza de las mochilas M-H

En el año 1982 Adi Shamir y Richard Zippel encuentran debilidades a las 

mochilas de Merkle-Hellman:

•Si se conoce el módulo m (o puede deducirse) ...

•Y si los dos primeros elementos (S1 y S2) de la mochila difícil se corresponden 

con los dos primeros elementos (S1’ y S2’) de la mochila simple y son primos con m ...

•Entonces podemos generar la mochila simple a partir de la difícil ya 

que encontraremos la clave secreta w-1 ... M

•Esta debilidad, aunque tenga fuertes restricciones, no hace recomendable 

el uso de  las mochilas M-H para el cifrado de la información ... L

Criptoanálisis de Shamir y Zippel

El ataque para m = 100 supone:

a) Que los dos primeros elementos de S’ de 100 y 101 bits son mucho 

más pequeños que el módulo m de 202 bits.

b) Que podemos identificar los elementos S1 y S2 en la  mochila difícil y hacerlos 

corresponder con S1’ y S2’.

c) Que conocemos el módulo m o podemos deducirlo. 

•Con estos datos se trata de encontrar los valores de S1’ y S2’ además del 

factor de multiplicación w.

•Con estos valores podemos generar la mochila fácil.

Pasos del ataque de Shamir y Zippel (1)

1. Se calcula q = (S1/S2) mod m

       Como Si = Si’* w mod m entonces:

       q = (S1’/S2’) mod m = [S1’* inv(S2’, m)] mod m

       Esto implica una condición: mcd (S2’, m) = 1

2. Se calculan todos los múltiplos modulares del valor q con multiplicadores 

en el rango.   

      [1, 2m+1] = [1, 2101]

      CM = {1*q mod m, 2*q mod m, ..., 2m+1*q mod m}

3. El candidato para S1’ será el valor más pequeño de CM.

4. Encontrado el candidato para S1’se calcula:

     w = (S1/S1’) mod m = [S1* inv(S1’, m)] mod m

     Esto implica una nueva condición: mcd (S1’, m) = 1

5. Conocido w encontramos w-1 =  inv(w, m) y así calculamos todos los elementos de la mochila Si’ = Si * w-1 mod m que debería ser del tipo supercreciente.

6. Si no se genera una mochila supercreciente, se elige el siguiente valor más pequeño del conjunto CM y así hasta recorrer todos sus valores. Si con este conjunto CM no se obtiene una mochila simple, se repite el punto 2 tomando ahora valores en el rango 

         2m+i  con i = 2, 3, ...

Bibliográfica:

Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza su uso, reproducción en computador e impresión en papel sólo para fines docentes, respetando siempre los derechos del autor.

http://es.scribd.com/doc/4679988/Seguridad-Informatica-y-Criptografia-Cifrado-Asimetrico-con-Mochilas#scribd