66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf ·...

32
UNIVERSIDAD DE BUENOS AIRES FACULTAD DE INGENIERIA 66.69 – Criptografía y Seguridad Informática Implementación en lenguaje C, de un sistema criptográfico simétrico basado en el método de Huffman, el cual comprime y brinda seguridad de datos al mismo tiempo. Díaz Silvester, Gabriel 71.777 Gregorio, Luciano 71.600 Skigin, Jorge Elías 70.607 Diciembre 1998

Transcript of 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf ·...

Page 1: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

UNIVERSIDAD DE BUENOS AIRES

FACULTAD DE INGENIERIA

66.69 – Criptografía y SeguridadInformática

Implementación en lenguaje C, de un sistemacriptográfico simétrico basado en el método de

Huffman, el cual comprime y brinda seguridad dedatos al mismo tiempo.

Díaz Silvester, Gabriel 71.777

Gregorio, Luciano 71.600

Skigin, Jorge Elías 70.607

Diciembre 1998

Page 2: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Índice

Índice..................................................................................................................................................................... 2Contenido del trabajo ............................................................................................................................................. 3Formas de representar un texto............................................................................................................................... 4La compresión de Huffman .................................................................................................................................... 4El algoritmo de Huffman........................................................................................................................................ 4Ejemplo de codificación empleando el método de Huffman .................................................................................... 6Método Criptográfico basado en el método de Huffman.......................................................................................... 7Implementación del algoritmo en lenguaje C.......................................................................................................... 8

Información contenida en el archivo encriptado.................................................................................................. 9Método de almacenamiento del árbol en el archivo comprimido ........................................................................10

Instrucciones para el uso del programa..................................................................................................................10Posibles ataques ....................................................................................................................................................11Histograma............................................................................................................................................................12Código - Programa principal del cifrador ..............................................................................................................13Código - Librería Compress.h ...............................................................................................................................15Código - Histograma .............................................................................................................................................30Bibliografía ...........................................................................................................................................................32

Page 3: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Contenido del trabajo

A continuación se exponen los puntos que desarrollamos en el Trabajo Final correspondiente a

la asignatura Ciptografía y Seguridad Informática.

1) Implementación de un algoritmo en lenguaje C que obtenga el texto cifrado a partir del texto

plano utilizando el método de Huffman. (utilizado como compresor).

2) Implementación de un algoritmo en lenguaje C que obtenga el texto plano a partir del texto

cifrado mediante el método de Huffman. (utilizado como compresor).

3) Verificación de que la longitud promedio de bits del mensaje cifrado corresponde a la Entropía

del texto plano correspondiente (codificación óptima).

4) Obtención de la curva de distribución de frecuencias del texto cifrado (histograma) mediante un

programa en C. Análisis de los resultados obtenidos.

5) Incorporación de seguridad al algoritmo de Huffman, añadiendo claves al sistema.

Clave de encriptación y desencriptación

Especifica el criterio de asignación de valor 1 o 0 a las aristas. El peor caso corresponde al

caso que se tiene 256 caracteres lo cual implica que la longitud de la clave es 255 bits (N-1).

6) Análisis de los posibles ataques que se pueden realizar al método criptográfico.

Page 4: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Formas de representar un texto

Para representar un texto en una computadora, los caracteres deben ser traducidos a una formabinaria. Una manera de expresar estos caracteres es utilizando el código ASCII. En este código,cada carácter es representado por siete bits. Por ejemplo el carácter “a” es representado como lasecuencia 1100001.

Otra manera de expresar un texto es por medio del código Morse. El mismo consiste enrepresentar los caracteres a través de puntos y rayas. El código Morse es más eficiente que elcódigo ASCII ya que asigna códigos cortos a los caracteres de mayor frecuencia y códigos largosa los de menor frecuencia. El resultado es que en promedio menor cantidad de bits son utilizadospara codificar un determinado texto. El criterio de asignación de códigos se basa en el análisis dela frecuencia de aparición de los caracteres del alfabeto inglés.

Esta diferencia nos lleva a analizar el concepto de eficiencia en la codificación que estáíntimamente ligada con la Entropía.

La Entropía se define como la cantidad mínima promedio de bits necesaria para representar unmensaje.

La Entropía es un factor fundamental al evaluar la eficiencia de un código, ya que en el mejor delos casos, un método de codificación utilizará en promedio una cantidad de bit igual a H(X),mientras que en la generalidad de las veces, se tendrá un valor superior a dicha cantidad.

La codificación de Huffman es un método óptimo para la compresión de textos, es decir, elpromedio de la longitud de bits del mensaje codificado se aproxima en gran medida al valor de laEntropía lo que hace que sea el método de codificación más eficiente.

La compresión de Huffman

La codificación de Huffman fue inventada por D. A. Huffman en el año 1952. Es un método decompresión estadístico, basado en la observación previa de lo que se va a comprimir .

La compresión de Huffman se basa en la sustitución de cadenas de caracteres por códigos queocupan menos espacio. Como la mayoría de los métodos de compresión, busca las cadenas dedatos que se repitan más veces en una secuencia: cuanto mayores sean estas cadena y más serepitan mayor será el grado de compresión, pero por lo general esto no ocurre así.Estadísticamente esta comprobado que las cadenas grandes casi no se repiten dentro de unasecuencia de datos. Es mas probable encontrar cadenas pequeñas que se repitan.

El algoritmo de Huffman

1) Lo primero que se hace es estudiar o fabricar una tabla de frecuencias de los caracteres deltexto plano, ordenando los mismos de menor a mayor frecuencia.

Page 5: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

2) Después se hace un árbol binario. Un árbol binario es una estructura de datos en la cual el nodoraíz apunta a dos nodos, denominados hijos y cada uno de ellos apunta a su vez a otros dosnodos. Esta estructura se repite hasta llegar a nodos especiales llamados hojas, los cuales tienenla característica de no poseer hijos. Las ramas de la izquierda se representan con un 0, mientrasque las de la derecha se representan con un 1. El árbol se construye de abajo hacia arribasiguiendo todos estos pasos. Todos los caracteres utilizados en el texto y sus respectivasfrecuencias quedan finalmente almacenados en las hojas del árbol.

3) Se toman los dos nodos de menor frecuencia y se colocan en una estructura de árbol mínima,

es decir, un nodo raíz y sus hijos. Los hijos contienen los caracteres de menor frecuenciadentro del texto plano. La raíz contendrá como información, la suma de las frecuencias de sushijos.

4) A continuación se escogen otros dos nodos de menor frecuencia excluyendo los dos utilizados

anteriormente e incluyendo el nodo raíz generado en el paso anterior dando lugar a un nuevoárbol. El nodo raíz nuevamente contendrá la suma de frecuencias de sus dos nodos hijos.

5) Este procedimiento se repite hasta llegar a la formación de un único árbol el cual contienetantas hojas como cantidad de caracteres distintos posea el texto analizado.

En ésta instancia se está en condiciones de obtener la forma óptima de codificación del textoplano. Se puede obtener el código asociado a cada carácter recorriendo el árbol generadoanteriormente desde la hoja que corresponde al carácter buscado hasta la raíz.

El árbol obtenido depende del texto plano con lo que textos distintos producirá árboles distintos.

La descompresión posterior de los datos se realiza siguiendo la estructura de árbol. Se ingresa porla raíz y de acuerdo a la codificación del carácter queda unívocamente determinado el camino quelleva hasta la hoja que contiene el carácter del texto plano.

El árbol diseñado para la compresión de archivos se almacena en el propio archivo, para sabercómo interpretar los datos allí almacenados a la hora de descomprimir. Los datos comprimidos sealmacenan en formato binario y se graban en bytes. Esto hace que los datos comprimidos nofinalicen exactamente en los limites de un byte. Para solventar este problema se puede llenar conceros ese espacio restante hasta completar el byte. Aunque el inconveniente principal es que sepueden obtener caracteres extra al descomprimir, debido a la incorrecta interpretación de esosceros.

Una solución más elegante consiste en incluir un código especial para indicar el final de la serie dedatos. Esto plantea una reorganización del árbol de codificación y del propio algoritmo decompresión, que debe detectar ese código “artificial” indicativo del final de datos.

Otra solución es incluir la longitud del texto plano dentro del encabezado del archivo comprimido.A medida que se descomprime se lleva la cuenta de los bytes generados hasta llegar al valorindicado.

Page 6: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Ejemplo de codificación empleando el método de Huffman

Desarrollaremos un ejemplo de codificar un texto plano bajo el método de Huffman.

Sea el siguiente texto plano: “hello world.”

La tabla de frecuencia asociada a dicho texto es:

carácter espacio d e h r w o l

frecuencia 1 1 1 1 1 1 2 3

• espacio (1) d (1) e (1) h (1) r (1) w (1) o (2) l (3)

• e (1) h (1) r (1) w (1) (2) o (2) l (3)

espacio (1) d (1)

• r (1) w (1) (2) (2) o (2) l (3)

e (1) h (1) espacio (1) d (1)

• (2) (2) (2) o (2) l (3)

r (1) w (1) e (1) h (1) espacio (1) d (1)

• (2) o (2) l (3) (4)

espacio (1) d (1) (2) (2)

r (1) w (1) e (1) h (1)

Page 7: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

• l (3) (4) (4)

(2) o (2) (2) (2)

espacio (1) d (1) r (1) w (1) e (1) h (1)

• (4) (7)

(2) (2) l (3) (4)

r (1) w (1) e (1) h (1) (2) o (2)

espacio (1) d (1)

• (11)

(4) (7)

(2) (2) l (3) (4)

r (1) w (1) e (1) h (1) (2) o (2)

espacio (1) d (1)

Método Criptográfico basado en el método de Huffman

El cifrador que proponemos es una versión modificada del método de Huffman, el cual agregaseguridad en los datos introduciendo una clave privada la cual es utilizada tanto en el proceso deencriptado como en el de desencriptado del mensaje. Esta versión del cifrador conserva lapropiedad de compresión optima que posee el método de Standard.

Page 8: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

El algoritmo puede ser interpretado como un método de sustitución, en el cual la codificación decada uno de los caracteres del texto plano es de longitud variable.

Implementación del algoritmo en lenguaje C

El algoritmo propuesto requiere recorrer dos veces el archivo de texto plano para generar elarchivo cifrado.

La primera recorrida permite generar una tabla de frecuencias de los caracteres contenidos en eltexto plano, es decir para cada uno de los 256 caracteres posibles del código ASCII se asigna unvalor correspondiente a la cantidad de repeticiones de dicho carácter en el archivo.

A partir de dicha tabla se genera un mecanismo que permita asignar los códigos correspondientesa cada carácter en forma unívoca. Para ello, se adopta la estructura de tipo árbol binario que serealiza asignando a cada hoja del árbol un carácter del texto y uniendo las hojas desde la de menorfrecuencia hasta llegar a la de mayor aparición de acuerdo a la tabla generada en el paso anterior.El objetivo es que un carácter que se repita muchas veces en el archivo le corresponda un códigode pocos bits y un carácter que aparezca pocas veces le corresponda un código de muchos bits.

Una vez obtenido la estructura de árbol, se asignan los correspondientes pesos binarios a lasaristas con el fin de obtener el código correspondiente a cada carácter recorriendo el árbol desdelas hojas hasta la raíz.

El criterio con el cual se asignan los valores binarios (1 o 0) a las aristas del árbol es función de laclave ingresada cuyo tamaño es de 255 bits. En caso que la clave sea de menor tamaño, se repiteen forma periódica hasta completar los 255 bits. Por el contrario si la clave es posee mas de 255bits, el sistema la trunca en 255 bits. De esta forma la longitud de la clave contempla el peor casoen el cual todos los caracteres del código ASCII están presentes en el texto plano. Para ese casose tiene un árbol de 255 pares de aristas.

Cada uno de los bits de la clave fija el criterio de asignación de los pesos a las aristas, siendo unbit = TRUE equivalente a conmutar el par de aristas correspondiente y el bit = FALSE mantiene laestructura por defecto (sin conmutar). El árbol es recorrido en inorden en forma recursiva.

En las segunda lectura del archivo, se debe ir leyendo carácter por carácter, obtener su códigocorrespondiente e ir escribiendo sobre el archivo destino. Los códigos de los caracteres seguardan en una tabla para no tener que recorrer todo el árbol por cada carácter leído.

Para la descompresión se recorre el archivo cifrado bit a bit y a partir del árbol binario por mediode la clave se obtiene el texto plano.

Para determinar el momento en que se debe finalizar el proceso de desencriptado, se almacena eltamaño del archivo fuente en el encabezado del archivo comprimido.

Si la clave ingresada para la descompresión no es igual a la utilizada en el proceso de compresiónpueden darse dos casos:

Page 9: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

1) Finaliza la recorrida del archivo antes de completar la cantidad de caracteres indicada por lalongitud del archivo en el encabezado.

2) Finaliza la decodificacion de la cantidad de caracteres indicada en el encabezado antes de quefinalice el archivo.

En ambos casos, el contenido del archivo descomprimido contiene los caracteres del texto planooriginal pero sin mantener ni el orden ni la cantidad. Esto se debe a que solo el contenido de lashojas del árbol coincide con el árbol verdadero, mientras que los pesos de las aristas se encuentranintercambiadas dando origen a las variaciones.

En el caso de que la clave de decodificacion coincida con la de codificación finaliza el proceso dedesencriptado juntamente con la lectura del archivo.

Información contenida en el archivo encriptado

Esta formada por 2 partes. La primera corresponde al encabezado y contiene la descripción delarchivo y la segunda es el texto encriptado.

El encabezado contiene:

1) Longitud del archivo de texto plano (palabra de 32 bits).2) Longitud de tabla de caracteres (16 bits)3) Tabla conteniendo los caracteres utilizados en el texto plano4) Árbol

Page 10: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Método de almacenamiento del árbol en el archivo comprimido

Con el objetivo de reducir al máximo la memoria utilizada en el archivo comprimido seaprovechan las características particulares de este tipo de árboles. De esta forma el árbol esalmacenado en dos partes: por un lado se almacena la información de las hojas en una tabla delongitud variable mencionada anteriormente, por otra parte se implementa una función paraguardar la forma del árbol (para generar el árbol vacío).

La función se encarga de escribir el árbol de Huffman sobre el archivo destino (comprimido).Como el árbol de Huffman posee 2 casos (nodos sin hijos o nodos con 2 hijos), se coloca un ceroen caso de encontrarse un nodo sin hijos y un uno en caso contrario. El árbol se recorrerecursivamente en inorden.

status escr_arbol(FILE *f_out, t_arbol* raiz, long* pos_bit, byte* byte_buf){ if ((!raiz->h_izq)&&(!raiz->h_der)) return (escribir_bit(f_out, byte_buf, pos_bit, FALSE)); if ((escribir_bit(f_out, byte_buf, pos_bit, TRUE)==ERROR)|| (escr_arbol(f_out, raiz->h_izq, pos_bit, byte_buf)==ERROR)|| (escr_arbol(f_out, raiz->h_der, pos_bit, byte_buf)==ERROR)) return ERROR; return OK;

Instrucciones para el uso del programa

El programa TPF_CRIP.EXE requiere para su funcionamiento el ingreso de 3 parámetros. Elprimero deberá ser “C” o “D” según se quiera comprimir/cifrar o descomprimir/descifrarrespectivamente. El segundo parámetro deberá ser el archivo origen y el tercero deberá ser elarchivo destino.

Al ingresar estos parámetros en la línea de comandos aparecen 3 opciones para elegir como semuestra a continuación:

Elija opción:

1- Utilizar clave manual2- Utilizar clave en archivo3- No utilizar clave

Opción>_

La opción 1 requiere el ingreso de la clave por medio del teclado como una cadena de 32caracteres de longitud.

Page 11: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

La opción 2 requiere el ingreso de la clave por medio de un archivo de al menos 32 bytes delongitud. En caso de tener una longitud menor el programa indica que el archivo de clavesingresado es incompatible.La opción 3 no requiere el ingreso de clave ya que únicamente realiza el proceso de compresiónsin ningún tipo de seguridad

Posibles ataques

Si se considera el peor caso en que el archivo a comprimir posee los 256 caracteres posibles delcódigo ASCII, el árbol de Huffman correspondiente tendrá 256 hojas y 255 pares de aristas. Porcada par de aristas existen 2 formas de asignar los pesos a las mismas, (1=izquierda y 0=derecha oviceversa) por lo tanto se necesitará 1 bit de la clave para especificar la convención utilizada encada par de aristas con lo que la clave deberá tener una longitud de 255 bits para cubrir todos loscasos posibles.

Un ataque a fuerza bruta aplicado al caso anterior implica probar las 2255 claves posibles lo cualhace al algoritmo computacionalmente seguro.

En el caso general de poseer un árbol de N hojas la cantidad de aristas es 2*(N-1) , es decir, N-1pares de aristas, necesitándose claves de N-1 bits para poder encriptar.

Al tratarse de textos planos con alfabetos de menor tamaño se generan árboles más pequeños yclaves más pequeñas, la cantidad de claves posibles se reduce exponencialmente con la cantidadde bits utilizados con lo cual los ataques a fuerza bruta serán computacionalmente realizables si eltexto plano no contiene un alfabeto suficientemente rico en variedad de caracteres.

Al tratarse de una codificación que utiliza palabras de longitud variable no habrá relación entre lafunción de distribución de frecuencias del texto plano y la correspondiente al texto cifrado y por lotanto un análisis criptográfico que utilice métodos estadísticos no ayudará a descifrar el mensaje.

Una forma de aumentar la variedad de caracteres utilizados en el texto plano es aplicar un métodocriptográfico previo a la compresión. Este paso previo puede ser realizado utilizando una clavepúblicamente conocida y su único objetivo es aumentar la longitud de la clave. Una desventaja deeste método es que la función de distribución de frecuencias del nuevo texto plano utilizado puederesultar uniforme con lo cual se tendrán los siguientes efectos indeseables:

• Se tendrá menos compresión pues se tiene mayor variedad de caracteres y todos confrecuencias similares.

• Puede darse el caso especial en el cual la función de distribución sea perfectamente uniforme yse tengan todos los caracteres del código ASCII para codificar, esto hará que se generencódigos de exactamente ocho bits para cada carácter según el método de Huffman pues esaserá la forma óptima, con lo cual el método se habrá transformado en un simple SubstitutionCipher. (aquí se podrá hacer criptoanálisis, pero el atacante deberá saber que se encuentra enese caso especial)

Page 12: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Sin embargo, dado que el algoritmo ha sido diseñado con el doble objetivo de cifrar y comprimir,en general se contará con textos planos de gran tamaño. En estos casos será muy probable que seutilicen alfabetos de alrededor de 50 o 60 caracteres, considerando la utilización de mayúsculas,minúsculas, números, signos de puntuación y caracteres especiales con lo cual la seguridad esrelativamente alta.

Histograma

Para completar el estudio de este método criptográfico, se realizó un programa implementado enC que obtiene una tabla con la distribución de frecuencias (histograma) de los caracteres de untexto. A continuación se muestran las curvas de distribución de frecuencias de un texto plano enidioma castellano y su respectivo archivo cifrado. Una vez obtenida la tabla con el programaimplementado en C, se obtiene la curva con el excel.

Histograma del archivo comprimido

0

50

100

150

200

250

1 14 27 40 53 66 79 92 105

118

131

144

157

170

183

196

209

222

235

248

Código ASCII

e re

pet

icio

nes

Series1

Histograma del texto plano

0

500

1000

1500

2000

2500

3000

3500

4000

1 14 27 40 53 66 79 92 105

118

131

144

157

170

183

196

209

222

235

248

Código ASCII

de

rep

etic

ion

es

Series1

Page 13: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Se puede observar como el histograma del texto cifrado es mucho mas uniforme que elhistograma del texto plano original.

Por otro lado, en el histograma del texto plano se observa un pico muy alto en el código ASCIInúmero 32 el cual corresponde al espacio en blanco.

Código - Programa principal del cifrador

#include "compress.h"

void ingresar_clave(t_texto clave){ FILE* arch; char nomarch[80]; int i; char opcion;

for (i=0; i<32; clave[i++] = 0);

printf("Elija opci¢n:\n\n"); printf(" 1- Utilizar clave manual\n 2- Utilizar clave en archivo\n"); printf(" 3- No utilizar clave\n\nOpci¢n> "); do opcion=getch()-'0'; while ((opcion>3)||(opcion<1));

if (opcion==1) {

printf("\n\nIngrese clave de 32 caracteres sin espacios: ");scanf("%s", clave);

} else if (opcion==2) {

printf("\n\nIngrese el nombre del archivo: ");scanf("%s", nomarch);if ((arch = fopen(nomarch, "rb")) == NULL) { printf("\n\nNo se pudo abrir archivo con la clave.\n"); exit(1); };if (fread(clave, 32, 1, arch)!=1) { printf("\n\nArchivo no compatible"); exit(1); }

}}

Page 14: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

void main(int argc,char *argv[]){ FILE *f_in,*f_out; t_texto clave; struct time t; long t1;

clrscr();

if(argc!= 4 ) /* Exige el par metro C o D segun se quiera comprimir o */ /* descomprimir y los archivos origen y destino al invocar */ /* al programa desde la l¡nea de comandos */

{ explicacion(); exit(1); }

if ((*argv[1]=='c')||(*argv[1]=='C')) { if ((f_in = fopen(argv[2], "rb")) == NULL)

{ /* Se abre el archivo que se pasa*/

fprintf(stderr, "No se pudo abrir archivo de entrada.\n"); /* como parametro en la linea decomandos */

exit(1); /* Si no se puede abrir sale del programa */ };

if ((f_out = fopen(argv[3], "wb")) == NULL) { fprintf(stderr, "No se pudo abrir archivo de salida.\n"); exit(1); };

ingresar_clave(clave);gettime(&t);t1 = 360000*((long)t.ti_hour)+6000*((long)t.ti_min)+100*((long)t.ti_sec)+((long)t.ti_hund);

if (comprimir(f_in,f_out, clave) == ERROR)printf("\n Se produjo un ERROR en la compresi¢n");

gettime(&t);t1 = 360000*((long) t.ti_hour)+6000*((long) t.ti_min)+100*((long) t.ti_sec)+((long) t.ti_hund)-t1;

printf("\nTiempo transcurrido en la compresi¢n: %lf segundos", ((float) t1)/100);

fclose(f_in); fclose(f_out); }

else if ((*argv[1]=='d')||(*argv[1]=='D')){if ((f_in = fopen(argv[2], "rb")) == NULL)

{fprintf(stderr, "No se pudo abrir archivo de entrada.\n");exit(1);};

Page 15: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

if ((f_out = fopen(argv[3], "wb")) == NULL){fprintf(stderr, "No se pudo abrir archivo de salida.\n");exit(1);

};ingresar_clave(clave);gettime(&t);t1 = 360000*((long) t.ti_hour)+6000*((long) t.ti_min)+100*((long) t.ti_sec)+((long) t.ti_hund);

if (descomprimir(f_in,f_out, clave) == ERROR)printf("\nSe produjo un ERROR en la descompresi¢n");

gettime(&t);t1 = 360000*((long) t.ti_hour)+6000*((long) t.ti_min)+100*((long) t.ti_sec)+((long) t.ti_hund)-

t1;

printf("\nTiempo transcurrido en la descompresi¢n: %lf segundos", ((float) t1)/100);

fclose(f_in);fclose(f_out);}

else{

explicacion();}

}

Código - Librería Compress.h

#include <conio.h>#include <alloc.h>#include <stdio.h>#include <dos.h>#include <stdlib.h>#include <math.h>

/* Declaraci¢n de constante */

#define MAX_ELEM_PILA 256

/* Declaraci¢n de tipos de variables */

typedef unsigned char byte;typedef enum{FALSE,TRUE}boolean;typedef enum{OK,ERROR}status;

typedef struct t_dato_arb{ byte codigo; long peso; } t_dato_arb;

typedef struct n_arb{

Page 16: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

t_dato_arb dato; struct n_arb *h_izq; struct n_arb *h_der; } t_arbol;

typedef struct t_pila{ boolean datos[MAX_ELEM_PILA]; int tope; } t_pila;

typedef struct t_dato_tabla{byte tam;unsigned long codigo;} t_dato_tabla;

typedef t_dato_tabla t_tabla[256];typedef long t_vec_cont[256];typedef t_arbol* t_vec_arb[256];typedef char t_texto[80];typedef boolean t_clave[256];

/* Esta funci¢n crea una pila vacia */

void inicializar_pila(t_pila* pila){ pila->tope = -1;}

/* Esta funci¢n verifica si la pila esta vac¡a */

boolean pila_vacia(t_pila *pila){ return (pila->tope==-1) ? TRUE : FALSE;}

/* Esta funci¢n inserta un elemento en la pila */

status apilar(t_pila* pila, boolean dato){ if (pila->tope<MAX_ELEM_PILA-1) {

pila->tope++;pila->datos[pila->tope] = dato;return OK;

}; return ERROR;}

/* Esta funcion elimina un elemento de la pila */

boolean desapilar(t_pila* pila) /* Precondici¢n: La pila no debe */{ /* estar vac¡a */

Page 17: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

pila->tope--; return (pila->datos[(pila->tope)+1]);}

/* Esta funci¢n calcula el tama¤o en bytes del archivo ingresado *//* como par metro.*/

long filesize(FILE *stream){ long curpos, length;

curpos = ftell(stream); fseek(stream, 0L, SEEK_END); length = ftell(stream); fseek(stream, curpos, SEEK_SET); return length;}

/* Esta funci¢n realiza una lectura de un long del archivo pasado como *//* par metro */

status leer_long(FILE *f_in, long* l){ return (fread(l,sizeof(long),1,f_in)==1) ? OK : ERROR;}

/* Esta funci¢n realiza una escritura de un long del archivo pasado como *//* par metro */

status escribir_long( FILE *f_out, long* l){ return (fwrite(l, sizeof(long), 1, f_out)==1) ? OK : ERROR;}

/* Esta funci¢n realiza una lectura de un byte del archivo pasado como par metro */

status leer_byte(FILE *f_in, byte* b){ return (fread(b,sizeof(byte),1,f_in)==1) ? OK : ERROR;}

/* Esta funci¢n realiza una escritura de un bytes en el archivo pasado como par metro */

status escribir_byte( FILE *f_out, byte* b){ return (fwrite(b, sizeof(byte), 1, f_out)==1) ? OK : ERROR;}

/* Esta funci¢n setea (pone en 1) el bit n£mero n del byte pasado como par metro */

Page 18: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

void encender_bit(byte* b, int n) { *b |= 1<<n; }

/* Esta funci¢n resetea (pone en 0) el bit n£mero n del byte pasado como par metro */

void apagar_bit(byte* b, int n) { *b &= ~(1<<n); }

/* Esta funci¢n setea (pone en 1) el bit n£mero n del long pasado como par metro */

void encender_bit_long(unsigned long* b, int n) { *b |= 1<<n; }

/* Esta funci¢n resetea (pone en 0) el bit n£mero n del long pasado como par metro */

void apagar_bit_long(unsigned long* b, int n) { *b &= ~(1<<n); }

/* Esta funci¢n lee del archivo el bit de la posici¢n pasada como par metro *//* (pos_bit) devolviendo TRUE si dicho bit es uno y FALSE en caso contrario.*//* Si la posici¢n del bit recibido es m£ltiplo de 8 (se complet¢ un byte), *//* adem s realiza la lectura del pr¢ximo byte y lo coloca en el buffer. *//* En rigor, la lectura se realiza sobre un buffer, y cuando se termina de *//* leer, reci‚n se vuelve a traer el pr¢ximo byte del archivo coloc ndolo en*//* el buffer para la pr¢xima lectura del bit (no se leer de a un bit en el *//* archivo) */

status leer_bit( FILE *f_in, byte* byte_buf, long *pos_bit, boolean* bit){ long n = (*pos_bit)%8;

if ((n==0)&&(leer_byte(f_in, byte_buf)==ERROR)) return ERROR; (*pos_bit)++; if (((*byte_buf)&(1<<n))==0) *bit = FALSE; else

*bit = TRUE; return OK;}

/* Esta funci¢n escribe en el archivo el bit (pasado como par metro), en la *//* posici¢n (pos_bit) devolviendo OK si pudo realizar la operaci¢n. Si la *//* posici¢n del bit recibido es m£ltiplo de 8 (se complet¢ un byte) se reali*//* za la escritura del byte buffer sobre el archivo. En rigor la escritura *//* del bit se realiza sobre un buffer y cuando ‚ste se llena reci‚n se escri*//* todo el buffer sobre el archivo */

status escribir_bit( FILE *f_out, byte* byte_buf, long *pos_bit, boolean bit){ long n = (*pos_bit)%8;

(bit) ? encender_bit(byte_buf,(int)n) : apagar_bit(byte_buf,(int)n); (*pos_bit)++;

Page 19: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

if (n==7) return (escribir_byte(f_out, byte_buf)); return OK;}

/* Esta funci¢n calcula la cantidad de repeticiones de los caracteres del *//* archivo a comprimir. Se recorre todo el archivo y se almacenan dichas *//* repeticiones un arreglo, donde la posici¢n de cada elemento del array *//* corresponde al c¢digo ASCII del caracter en cuesti¢n */

status estadistica(FILE *f_in, t_vec_cont v, long* tam_estimado){ byte b; long i; double tamanio = (double) filesize(f_in); double L2 = log(2); double H = 0, P_i;

for (i=0; i<256; i++) v[i] = 0;

for (i=0; i<((long) tamanio); i++) {

if (leer_byte(f_in,&b)==ERROR) return ERROR; v[b]++;

}; fseek(f_in,0,SEEK_SET);

/* c lculo de la entrop¡a del texto plano */

for (i=0; i<256; i++) {

P_i = ((double) v[i])/tamanio; if (P_i>0) H -= P_i*log(P_i);

}

H /= L2;

/* estimaci¢n de la longitud del texto cifrado en bytes */

*tam_estimado = (long) ((H*tamanio)/8.0);

return OK;}

/* Esta funci¢n crea una hoja de arbol, en la cual coloca los punteros hijo *//* derecho e izquierdo en NULL y el dato del caracter y su repetici¢n que se*//* pasan a trav‚s de una estructura como par metro */

status crear_hoja( t_arbol* *arbol, t_dato_arb *dato){ t_arbol* nuevo = (t_arbol*) malloc (sizeof(t_arbol));

Page 20: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

if (!nuevo) return ERROR; nuevo->dato = *dato; nuevo->h_izq = NULL; nuevo->h_der = NULL; *arbol = nuevo; return OK;}

/* Esta funci¢n se encarga de ordenar de mayor a menor el vector de arboles *//* de acuerdo al dato de repetici¢n de caracteres que contiene cada una de *//* las hojas */

void ordenar(t_vec_arb vec_arb, int n){ int i; t_arbol* aux; boolean ordenado = FALSE;

while (!ordenado) {

ordenado = TRUE;for (i=0; i<n-1; i++) if (vec_arb[i]->dato.peso < vec_arb[i+1]->dato.peso) {

ordenado = FALSE; aux = vec_arb[i]; vec_arb[i] = vec_arb[i+1]; vec_arb[i+1] = aux;

}; };}

/* Esta funci¢n se encarga de crear una hoja de arbol por cada caracter con *//* repetici¢n distinta de cero coloc ndola en un vector de hojas. Luego se *//* ordena dicho vector de acuerdo al factor de repetici¢n (dato ubicado en *//* en las hojas. Por £ltimo se procede a generar el rbol de Huffman reali *//* zando movimiento de punteros sobre dicho vector de rboles */

int fcmp(const void* P1, const void* P2){

t_arbol* A1 = (t_arbol*) (P1); t_arbol* A2 = (t_arbol*) (P2); return (A1->dato.peso < A2->dato.peso)? -1 : 1;}

status armar_arbol(t_arbol* *raiz, t_vec_cont vec_cont){

Page 21: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

int i,j=0; t_dato_arb dato_aux; t_arbol* aux, P1,P2; t_vec_arb vec_arb;

for (i=0; i<256; i++) {

if (vec_cont[i]>0) { dato_aux.codigo = i; dato_aux.peso = vec_cont[i]; if (crear_hoja(vec_arb+j,&dato_aux)==ERROR) return ERROR; j++; };

};

// qsort(vec_arb, sizeof(t_arbol*),j, fcmp);

ordenar(vec_arb, j);

while (j>1) {

dato_aux.peso = vec_arb[j-2]->dato.peso + vec_arb[j-1]->dato.peso; if (crear_hoja(&aux,&dato_aux)==ERROR) return ERROR; aux->h_izq = vec_arb[j-2]; aux->h_der = vec_arb[j-1]; i = j-2; while ( (i>0) && (aux->dato.peso > vec_arb[i-1]->dato.peso) ) {

vec_arb[i] = vec_arb[i-1]; i--;

}; vec_arb[i] = aux; j--;

};

*raiz = vec_arb[0];

return OK;}

/* Una vez generado el rbol de Huffman, se procede a realizar una tabla, *//* en la cual se colocan los caracteres de las hojas, recorriendo al arbol *//* en inorden. */

void formar_tabla( t_arbol* raiz, byte* tabla, int* n){ if ((!raiz->h_izq)&&(!raiz->h_der)) {

*(tabla+(*n)) = raiz->dato.codigo;(*n)++;

} else

{

Page 22: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

formar_tabla( raiz->h_izq, tabla, n); formar_tabla( raiz->h_der, tabla, n);};

}

/* Esta funci¢n se encarga de escribir la tabla generada en el procedimiento*//* anterior sobre el archivo destino (archivo comprimido). */

status escribir_tabla( FILE *f_out, byte* tabla, int n){ byte b; int i;

b = n-1; if (escribir_byte(f_out,&b)==ERROR) return ERROR; for (i=0; i<=b; i++) if (escribir_byte(f_out,tabla+i)==ERROR) return ERROR; return OK;}

/* Esta funci¢n se encarga de leer la tabla de caracteres del archivo compri*//* mido para luego poder reconstru¡r el arbol de Huffman. */

status leer_tabla( FILE *f_in, byte* tabla){ byte b; int i;

if (leer_byte(f_in,&b)==ERROR) return ERROR; for (i=0; i<=b; i++) if (leer_byte(f_in,tabla+i)==ERROR) return ERROR; return OK;}

/* Esta funci¢n se encarga de escribir el arbol de Huffman sobre el archivo *//* destino (comprimido). Como el rbol de Huffman posee 2 casos (nodos sin *//* hijos o nodos con 2 hijos), se colocar un cero en caso de encontrarse *//* un nodo sin hijos y un uno en caso contrario. El rbol se recorre en *//* inorden */

status escr_arbol(FILE *f_out, t_arbol* raiz, long* pos_bit, byte* byte_buf){ if ((!raiz->h_izq)&&(!raiz->h_der)) return (escribir_bit(f_out, byte_buf, pos_bit, FALSE)); if ((escribir_bit(f_out, byte_buf, pos_bit, TRUE)==ERROR)|| (escr_arbol(f_out, raiz->h_izq, pos_bit, byte_buf)==ERROR)|| (escr_arbol(f_out, raiz->h_der, pos_bit, byte_buf)==ERROR)) return ERROR; return OK;}

Page 23: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

/* Este procedimiento tiene la funci¢n de recrear el rbol de Huffman en *//* base a la lectura del arbol y de la tabla de caracteres (pasado como *//* par metro) del archivo comprimido */

status recrear(FILE *f_in, t_arbol* *raiz, long* pos_bit, byte* byte_buf, byte* tabla, int* i)

{ t_arbol* aux; t_dato_arb d_aux; boolean bit;

if ((crear_hoja(&aux, &d_aux)==ERROR)|| (leer_bit(f_in, byte_buf, pos_bit, &bit)==ERROR)) return ERROR;

if (bit) {

if ((recrear(f_in, &(aux->h_izq), pos_bit, byte_buf, tabla, i)==ERROR)|| (recrear(f_in, &(aux->h_der), pos_bit, byte_buf, tabla, i)==ERROR)) return ERROR;

} else {

aux->dato.codigo = *(tabla+(*i));(*i)++;

}

*raiz = aux; return OK;}

/* Esta funci¢n se encarga de destru¡r el rbol de Huffman, una vez que se *//* lo ha utilizado y ya no se lo necesita */

t_arbol* destruir_arbol(t_arbol* raiz){ if (raiz) { destruir_arbol(raiz->h_izq); destruir_arbol(raiz->h_der); free(raiz); }; return NULL;}

/* Esta funci¢n se encarga de generar el c¢digo correspondiente a cada carac*//* ter. Devuelve, por par metro, una pila en la cual est el c¢digo buscado *//* Se deber tener en cuenta que en el tope de la pila se encuentra el bit *//* m s significativo del c¢digo (el que se copiar primero en el archivo) */

boolean buscar_cod(t_arbol* raiz, t_pila* pila, byte b){ if (raiz)

Page 24: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

{if ((!raiz->h_izq)&&(!raiz->h_der)&&(raiz->dato.codigo==b)) return TRUE;if (buscar_cod(raiz->h_izq, pila, b)) { apilar(pila, FALSE); return TRUE;};if (buscar_cod(raiz->h_der, pila, b)) { apilar(pila, TRUE); return TRUE;};

} return FALSE;}

/* Esta funci¢n se encarga de ir leyendo bit a bit el archivo (en rigor *//* se lee el buffer, y obtener el caracter correspondiente al c¢digo le¡do */

status buscar_byte(FILE *f_in, t_arbol* raiz, long* pos_bit, byte* byte_buf, byte* b)

{ boolean bit;

for(;;) if ((!raiz->h_izq)&&(!raiz->h_der))

{ *b = raiz->dato.codigo; return OK; } else { if (leer_bit(f_in, byte_buf, pos_bit, &bit)==ERROR) return ERROR; if (bit)

raiz = raiz->h_der;else raiz = raiz->h_izq;

};}

/* Esta funci¢n se encarga se generar una tabla que contiene, para cada ca *//* racter existente en el archivo, el c¢digo y el tama¤o del c¢digo que le *//* corresponde. Esto se hace para acelerar el proceso de compresi¢n de archi*//* vos grandes, ya que se acceder en forma directa al c¢digo a trav‚s de la*//* tabla y no se requerir recorrer el rbol para cada caracter. */

void crear_tabla_de_codigos(t_arbol *arbol,t_tabla tabla_cod,t_vec_cont v){ int p,b; byte n=1; unsigned long cod_aux=0; t_pila pila;

inicializar_pila(&pila);

for(p=0;p<256;p++){

Page 25: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

tabla_cod[p].codigo=0;tabla_cod[p].tam=0;}

for(b=0;b<256;b++){if (v[b]!=0)

{buscar_cod(arbol,&pila,(byte) b);n = 0;while (!pila_vacia(&pila))

{if (desapilar(&pila)) encender_bit_long(&cod_aux,n); else apagar_bit_long(&cod_aux,n);n++;

}tabla_cod[b].tam=n;tabla_cod[b].codigo=cod_aux;}

}}

void transformar_clave(t_texto texto, t_clave clave){ int i, j, k=0, l=strlen(texto); char ch;

if (l==0) texto[0] = 0;

for (i=l, j=0; i<32; i++, j++) texto[i]=texto[j];

for (i=0; i<32; i++) for(j=0; j<8; j++, k++)

clave[k] = (texto[i]&(1<<j))? TRUE: FALSE;}

void permutar_segun_clave(t_arbol* arbol, t_clave clave, int* i){ t_arbol* aux;

if (arbol) { if (arbol->h_izq)

{ if (clave[(*i)++])

Page 26: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

{ aux = arbol->h_izq; arbol->h_izq = arbol->h_der; arbol->h_der = aux;

} permutar_segun_clave(arbol->h_izq, clave, i); permutar_segun_clave(arbol->h_der, clave, i);

} }}

/* Esta funci¢n se encarga de escribir sobre el archivo destino, los datos *//* correspondientes al cuerpo del archivo a comprimir. Inicialmente se escri*//* be el rbol, luego se genera la tabla de c¢digos y por £ltimo se va leyen*//* do del archivo a comprimir (fuente), convirtiendo (a trav‚s de la tabla) *//* al c¢digo correspondiente y escribiendo finalmente el c¢digo sobre el *//* archivo destino.*/

status escribir_comprim(FILE* f_in, FILE* f_out, t_arbol* arbol, t_vec_cont v,long* tam_cifrado, t_texto texto)

{ long tamanio=filesize(f_in); long i,pos_bit = 0; byte b, byte_buf, tamanio_aux; unsigned long cod_aux; boolean bit; t_tabla tabla_cod; t_clave clave; int ent=0;

if (escr_arbol(f_out, arbol, &pos_bit, &byte_buf)==ERROR) return ERROR;

transformar_clave(texto, clave); permutar_segun_clave(arbol, clave, &ent);

*tam_cifrado = pos_bit;

crear_tabla_de_codigos(arbol,tabla_cod, v);

for (i=0,tamanio=filesize(f_in); i<tamanio; i++) {

if (leer_byte(f_in,&b)==ERROR) return ERROR;

tamanio_aux=tabla_cod[b].tam;cod_aux=tabla_cod[b].codigo;while (tamanio_aux!=0)

{if (((cod_aux)&(1))==0)

Page 27: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

bit=FALSE;else

bit=TRUE;

if (escribir_bit(f_out, &byte_buf, &pos_bit, bit)==ERROR)return ERROR;

cod_aux >>= 1;tamanio_aux--;

} };

*tam_cifrado = (pos_bit-*tam_cifrado)/8;

if ((pos_bit%8)!=0) return(escribir_byte(f_out,&byte_buf)); /* VACIA BUFFER */

return OK;}

/* Esta funci¢n se encarga de descomprimir el archivo comprimido obteni‚ndose*//* el archivo original. Va leyendo byte por byte el archivo comprimido y, a *//* trav‚s del rbol reconstru¡do anteriormente, se obtiene el caracter corres*//* pondiente a dicho c¢digo. */

status escribir_descomp(FILE *f_in,FILE *f_out, t_arbol* raiz,long* pos_bit, byte* byte_buf, long tamanio)

{ long i; byte b;

for (i=0; i<tamanio; i++) {

if (buscar_byte(f_in, raiz, pos_bit, byte_buf, &b)==ERROR) return ERROR; if (escribir_byte(f_out, &b)==ERROR) return ERROR;

}; return OK;}

/* Esta funci¢n realiza toda la compresi¢n del archivo, inicialmente realiza*//* la tabla de repeticiones de caracteres, luego arma el rbol de Huffman, *//* luego forma la tabla de caracteres, luego escribe sobre el archivo des *//* tino el tama¤o del archivo original, luego escribe la tabla de caracteres*//* luego escribe el arbol y por £ltimo escribe el c¢digo correspondiente al *//* cuerpo del archivo. Antes de salir del procedimiento realiza la destruc *//* ci¢n del rbol utilizado para no dejar basura en la memoria. Adem s la *//* funci¢n nos da datos como el tama¤o del archivo origen y destino para *//* apreciar la capacidad de compresi¢n del programa. */

status comprimir(FILE *f_in, FILE *f_out, t_texto texto){ t_vec_cont vec_cont;

Page 28: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

int n=0; t_arbol* raiz; byte tabla[256]; long tam_estimado, tam_cifrado; long tamanio = filesize(f_in);

clrscr();

if (tamanio==0){printf("El archivo tiene tama¤o 0");

fclose(f_in); fclose(f_out);

return OK; }

printf("\nHaciendo estadistica de los datos"); if (estadistica(f_in, vec_cont, &tam_estimado)==ERROR) return ERROR; printf("\ntama¤o estimado del archivo comprimido: %ld bytes", tam_estimado); printf(" OK\nArmando arbol"); if (armar_arbol(&raiz,vec_cont)==ERROR) return ERROR; printf(" OK\nEscribiendo tabla"); formar_tabla(raiz,tabla,&n); if (escribir_long(f_out, &tamanio)==ERROR) return ERROR; if (escribir_tabla(f_out,tabla,n)==ERROR) return ERROR; printf(" OK\nEscribiendo destino"); if (escribir_comprim(f_in, f_out, raiz, vec_cont, &tam_cifrado, texto)==ERROR) return ERROR; printf(" OK\n"); printf("\nTama¤o del archivo origen (descomprimido): %ld bytes",filesize(f_in)); printf("\nTama¤o del archivo destino (comprimido): %ld bytes",filesize(f_out)); printf("\nTama¤o del texto cifrado: %ld bytes", tam_cifrado);

raiz = destruir_arbol(raiz);

fclose(f_in); fclose(f_out); return OK;}

/* La funci¢n se encarga de recuperar el archivo original a trav‚s de la *//* descompresi¢n. Inicialmente lee la longitud del archivo original, luego *//* lee la tabla de caracteres, luego reconstruye el rbol de Huffman, y por*//* £ltimo convierte el c¢digo le¡do en su caracter correspondiente. */

status descomprimir(FILE *f_in, FILE *f_out, t_texto texto){ byte byte_buf; int i=0, ent=0; t_arbol* raiz; byte tabla[256]; long pos_bit = 0; long tamanio = filesize(f_in);

Page 29: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

long aux; t_clave clave; long aux2;

clrscr();

if (tamanio==0){printf("El archivo tiene tama¤o 0");

fclose(f_in); fclose(f_out);

return OK; }

printf("\n\nLeyendo tabla"); if (leer_long(f_in, &tamanio)==ERROR) return ERROR; if (leer_tabla(f_in, tabla)==ERROR) return ERROR; printf(" OK\nReconstruyendo arbol"); if (recrear(f_in, &raiz, &pos_bit, &byte_buf, tabla, &i)==ERROR) return ERROR; transformar_clave(texto, clave); permutar_segun_clave(raiz, clave, &ent); printf(" OK\nEscribiendo destino"); if (escribir_descomp(f_in, f_out, raiz, &pos_bit ,&byte_buf, tamanio) ==ERROR) return ERROR; printf(" OK\n"); printf("\nTama¤o del archivo origen (comprimido): %ld bytes",filesize(f_in)); printf("\nTama¤o del archivo destino (descomprimido): %ld bytes",filesize(f_out));

raiz = destruir_arbol(raiz);

fclose(f_in); fclose(f_out); return OK;}

/* Esta funci¢n realiza una explicaci¢n de c¢mo se utiliza el compresor en *//* cuanto a los par metros que necesita */

void explicacion(void){printf("El programa COMPRESS requiere 3 parametros a ingrasar desde la l¡nea de comandos");printf("El primero deber ser 'c' o 'd' para indicar que se quiere comprimir o descompri");printf("mir respectivamente. El segundo deber ser el nombre del archivo origen, archivo");printf("a comprimir en caso de haber colocado 'c' o a descomprimir en caso de haber colo");printf("cado 'd'.El tercero deber ser el nombre del archivo destino (el archivo compri-");printf("mido en caso de haber colocado 'c' o archivo descomprimido en caso de haber colo");printf("cado 'd').\n");}

Page 30: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Código - Histograma

#include <conio.h>#include <alloc.h>#include <stdio.h>#include <dos.h>#include <stdlib.h>#include <math.h>#include <string.h>

typedef long t_vec_cont[256];

void estadistica(FILE *f_in, FILE *f_out, t_vec_cont v){ unsigned char b; int i;

for (i=0; i<256; v[i++] = 0);

while (!feof(f_in)) {

fread(&b, 1, 1, f_in); v[b]++;

};

for (i=0; i<256; fprintf(f_out,"%ld\n",v[i++]));

}

void explicacion(void){printf("\nEl programa FREC requiere 2 parametros a ingrasar desde la l¡nea de comandos.\n");printf("El primero deber ser el nombre del archivo origen y el segundo ser el destino.\n");}

void main(int argc,char *argv[]){ FILE *f_in,*f_out; t_vec_cont v; clrscr();

if(argc!=3) { explicacion(); exit(1); }

if ((f_in = fopen(argv[1], "rb")) == NULL) {

fprintf(stderr, "No se pudo abrir archivo de entrada.\n");exit(1);

};

Page 31: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

if ((f_out = fopen(argv[2], "wb")) == NULL) {

fprintf(stderr, "No se pudo abrir archivo de salida.\n");exit(1);

};

estadistica(f_in, f_out, v);

fclose(f_in); fclose(f_out);}

Page 32: 66.69 – Criptografía y Seguridad Informáticamaterias.fi.uba.ar/6669/alumnos/1999/huffman.pdf · La codificación de Huffman es un método óptimo para la compresión de textos,

Bibliografía

1. Publicaciones en Internet 2. Cryptography, Theory and Practice - Douglas Stinson 3. El lenguaje de Programación C - Kernighan & Ritchie