Entrega Final

Junio 12, 2014

1 Contenido

1.1 Nombre del grupo

One More Time Again

1.2 Nombres de los integrantes

Andres Felipe Castellanos Paez

Francisco Andres Aranguren Torres

Oscar David Garcia Medina

1.3 Tıtulo

Transmision eficiente y segura de imagenes

1.4 Introduccion

Con el desarrollo de la computacion y en especial la transmision de datos por medios virtuales, se ve

la necesidad de reducir el tamano de los datos para que estos puedan ser transmitidos mas rapido.

Tambien es importante la seguridad a la hora de transmitir estos datos. Las grandes cantidades

de imagenes que se generan en la actualidad o el tamano de las mismas son razones por las cuales

se piensa en metodos de compresion, por ejemplo en imagenes medicas, o fotografıas hechas por

satelites o telescopios espaciales. Con ello se han logrado divulgar y estandarizar varios algoritmos,

1

tanto de seguridad fuerte como debil y ası logrando una transmision efectiva de la misma. El

objetivo sera comparar los algoritmos utilizados para encontrar cual serıa mejor en complejidad y

procesamiento de las imagenes, mostrando la forma en la cual se codifica y decodifica la imagen y

las particularidades de cada algoritmo respecto al procesamiento de las imagenes.

1.5 Marco teorico

Se utilizaran tres algoritmos de compresion y encriptacion de texto plano, los cuales seran modifica-

dos para que cumplan su labor sobre imagenes. Estos son el algoritmo basado en teorıa de numeros

(Teorema chino del residuo), el algoritmo de Hill Cipher y un algoritmo denominado de Hill Cipher

Avanzado.

1.5.1 Teorema Chino del residuo

Este metodo se basa en representar la imagen como una matriz cuadrada de tamano N × N , el

cual puede ser, por ejemplo, 256 × 256, 512 × 512 y 1024 × 1024. Esta matriz se fragmenta en

bloques de tamano 1 ×K; cada pixel en este bloque es representado por una representacion de su

bit mas pequena al dividirlo por 16. Ası, tenemos las congruencias lineales yi = ai(modni) para

algun entero ni escogido cuidadosamente, donde ai es el bit en su representacion reducida. Este

sistema se resuelve con el teorema chino del residuo.

Teniendo las congruencias lineales:

x = ai(modni) donde i varia hasta k

Ası tenemos que:

Y = X(modN) con N siendo el producto de cada ni, siendo estos primos relativos entre ellos.

X = sum(ai ·Ni · xi)modP ,

Ni ∗ xi = 1(modni)

De esta manera se encuentra X.

Para decodificar la imagen, se aplica, usando cada X: ai = Xmodni

Ası, el valor original de cada pixel esta dado por:

P = ai · 16

2

1.5.2 Algoritmo de Hill Cipher

Este algoritmo, basado en algebra lineal, funciona de la siguiente manera:

Para texto plano, el algoritmo toma m letras sucesivas y provee, para esas letras, m letras sustitutas.

En este algoritmo, a cada letra se le asigna un valor numerico de 0 a 25 (a=0, b=1,, z=25). La

sustitucion de las m letras a sus sustitutas esta dada por m ecuaciones lineales, de la forma:

C1 = (K11 · P1 +K12 · P2 +K13 · P3 + . . .+K1m · Pm)mod26

C2 = (K21 · P1 +K22 · P2 +K23 · P3 + . . .+K2m · Pm)mod26

. . .

Cm = (Km1 · P1 +Km2 · P2 +Km3 · P3 + . . .+Kmm · Pm)mod26

Esto puede ser expresado en terminos de vectores y matrices:

C1

C2

...

Cm

=

K11 K12 . . . K1m

K11 K12 . . . K1m

K11 K12 . . . K1m

K11 K12 . . . K1m

P1

P2

. . .

Pm

mod26

O bien, se puede escribir como C = KP , donde C y P son vectores columna de tamano m,

representando el texto sustituto y el texto original, respectivamente; ademas, K es una matriz

cuadrada de tamanom, la cual sera nuestra matriz llave. Esta matrizK debe ser, ademas, invertible,

ya que para recuperar el mensaje original, es necesario hacer la operacion P = K−1C. Todas estas

operaciones son desarrolladas mod(26).

1.5.3 Generando llaves

• Para el teorema Chino del Residuo:

Para generar los numeros primos que se van a usar se realizan los siguientes pasos:

1. Se genera un numero aleatorio p, del tamano deseado (n bits).

2. Se pone a 1 el bit mas significativo (para asegurar el tamano del numero) y el bit menos

significativo (para permitir que sea primo).

3. Se prueba a factorizar el numero, usando una tabla almacenada de numeros primos

pequenos (numeros primos menores que 1000, 2000 o 3000). Con esto se elimina de

3

manera rapida un tanto por ciento alto de numeros no primos (el 99, 8% de los numeros

impares no primos es divisible por algun primo menor que 2000).

4. Se ejecuta alguno de los test de primalidad para comprobar que es primo.

• Para el algoritmo de Hill Cipher:

– Metodo 1: Es necesario utilizar una matriz cuadrada del tamano del alfabeto m como

llave, la cual debe ser invertible (det(A)! = 0), y ademas, el valor de su determinante

debe ser un primo relativo con respecto a m. Para encontrar la llave de decodificacion,

es necesario hallar la llave inversa a la usada en la encriptacion (A−1), esto lo podemos

hacer con la ecuacion:

A−1 =adj(A)

det(A)−1mod(m)

– Metodo 2: Se puede utilizar una matriz auto-invertible, esto quiere decir que se cumple

la igualdad A= A-1. El algoritmo para encontrar una matriz auto-invertible con la cual

se puede ahorrar la busqueda de la inversa de la matriz, es el siguiente:

Primero, para una matriz 2x2 sabemos que:

A−1 = adj(A)det(A)

A−1 = 1/det(A)

a22 a12

−a21 a11

Entonces si A es auto-invertible, tenemos que A = A−1 y ademas tenemos que a21 = −a21

det(A)

y a12 = −a12det(A)

, ası que el det(A) = −1. Entonces a11 = −a22 y a22 = −a11.

Ejemplo: Para mod(13)

A =

2 3

11 12

Siendo A una matriz auto-invertible de tamano n, tenemos que:

A =

a11 a12 . . . a1n

a21 a22 . . . a2n...

.... . .

...

an1 an2 . . . ann

4

Y se puede fraccionar en:

A =

A11 A12

A21 A22

Donde A11 es la matriz de tamano 1 × 1 A11 =

[a11

]A12 es la matriz de tamano 1 × (n− 1) A12 =

[a11 a12 . . . a1n

]

A21 es la matriz columna de tamano (n− 1) × 1 A21 =

a21

a31...

am1

A22 es la matriz de tamano (n− 1) × (n− 1) A22 =

a22 . . . a2n...

. . ....

an2 . . . ann

Entonces A12A21 = IA11

2 = Ia112, A12(A11I + A22) = 0. Ademas a11 = − (uno de

los eigenvalores de A22 diferente de 1). Ya que es una matriz singular, se tiene que

A21A12 = IA222; ası, debe tener rango (n − 2) de eigenvalores +1 de multiplicidad

(n− 2).

Un segundo metodo para hallar una matriz auto-invertible esta dado por la definicion de

eigenmatriz:

EA = Eτ

Donde E es la eigenmatriz y τ es la matriz diagonal con los eigenvalores como los ele-

mentos de la diagonal.

Entonces A = EτE−1 y A−1 = (EτE−1)−1 = Eτ−1E−1

Entonces A = A−1 se cumple cuando τ = τ−1

1.6 Implementacion

• Implementacion del Teorema Chino del residuo

Se aplica el Teorema Chino del residuo para cada bloque de tamano 1 ×m donde la imagen

es de tamano m×m.

• Implementacion del Algoritmo de Hill Cipher

Este algoritmo se puede desarrollar tanto para imagenes en escala de gris como para imagenes

5

a color: Para las imagenes en escala de gris, el modulo sera 256 (el numero de niveles); si

es una imagen a color, se descompone en componentes RGB. En ambos casos, se procede a

partir la imagen en bloques de tamano 1xm y se procede a aplicar el algoritmo en cuestion

anadiendo que, en el segundo caso, se aplica el algoritmo para cada componente RGB de

manera independiente y luego se concatenan los componentes encriptados juntos para obtener

la imagen codificada. El algoritmo de Hill Cipher, sin embargo, no es muy eficaz con imagenes

con grandes zonas con el mismo color o escala de gris. Este problema es resuelto con el

algoritmo avanzado de Hill Cipher.

• Implementacion del Algoritmo Avanzado de Hill Cipher

Se aplica de manera similar al algoritmo antes abordado de Hill Cipher. La gran diferencia se

presenta en la escogencia del tamano de los bloques, que en este caso seran bloques simetricos

del tamano de la matriz llave (tomemos como referencia la notacion m×m). Luego se toma

el i-esimo pixel de cada bloque y, con ellos, se forma un bloque temporal al cual se le aplica

el algoritmo de Hill Cipher; acto seguido, a la matriz resultante del algoritmo se le calcula su

transpuesta y se aplica de nuevo el algoritmo. Por ultimo, la matriz resultante es colocada en

el i-esimo bloque de la imagen codificada.

1.7 Resultados

Como se puede apreciar en las figuras 1, 2 y 3, la diferencia en el resultado usando estos algoritmos

es mınima (compresion baja, ruido nulo); sin embargo, el tiempo del proceso es muy diferente,donde

el algoritmo de Hill Cipher en ambas es mas rapido frente al algoritmo aplicando el Teorema Chino

del residuo.

Aunque el criptoanalisis de estos algoritmos no fue muy profunda, la vulnerabilidad frente a un

ataque de fuerza bruta esta dada por:

• Hill Cipher: Existen 2562n posibles matrices posibles llave nxn modulo 256, aunque de todas

de estas, no todas son invertibles. Si se utiliza el algoritmo propuesto para hallar una matriz

auto invertible modulo 256, se tienen 2562n.

6

Figure 1: Imagen Original

(a) codificado Hill Chiper (b) codificado Teorema Chino

del residuo

Figure 2: Imagenes procesadas 1

(a) decodificado Hill Chiper (b) decodificado Teorema Chino

del residuo

Figure 3: Imagenes procesadas 2

7

• Teorema Chino del residuo: Por el teorema del nmero primo, que describe la distribucion de

los numeros primos, tenemos que el numero de numeros primos menores o iguales a x esta

dado por la funcion de conteo de primos: τ(x) ≈ x/ln(x)

Entonces el numero de primos de 512bits es aproximadamente:

2513

ln(2513)− 2512

ln(2512)≈ 2.76 ∗ 10151

Existen aproximadamente 2.76∗10151 primos de 512 bits. Ahora bien, se necesitan n numeros

coprimos por bloque, siendo n bloques, por lo cual se tienen n2 ∗ 2.76 ∗ 10151 numeros.

1.8 Conclusiones

En este trabajo se proponen tres metodos de codificacion de imagenes, de los cuales el algoritmo de

Hill Cipher es mas seguro a ataques de fuerza bruta, ademas de ser mas rapido.

Para procesar imagenes de gran tamano es necesario hacer operaciones con numeros grandes, los

cuales suman tiempo de procesamiento y por lo cual, aumenta aun mas la complejidad de proce-

samiento.

Entre mas grandes sean los bloques que se escogen en el algoritmo del Teorema Chino de los Restos,

mayor es la compresion. De igual manera, tambien se aumenta la complejidad por el punto descrito

anteriormente de procesamiento de numeros grandes.

1.9 Bibliografia

Vinoly Seromony, Image Encryption and Compression using Number Theoretic Paradigm,2003,

GSPx Conference, April

Vikram Jagannathan, Simultaneous Color Image Compression and Encryption using Number The-

ory

Ryan Doyle, Hills Cipher: Linear Algebra in Cryptography

8