1. Educación

Universidad Simón Bolívar
Departamento de Computación
Sistemas de Operación I
Proyecto 1: Criptografia Concurrente (15%)
Objetivos
•
Utilizar las primitivas fork, wait, exec y exit de manejo de procesos concurrentes
para cifrado y descifrado de archivos de texto.
•
Utilizar las primitivas de hilos (threads) de manejo de procesos concurrentes para
cifrado y descifrado de archivos de texto.
•
Desarrollar la aplicación secuencialmente para compararla con las versiones
concurrentes.
•
Desarrollar un mecanismo de comunicación de memoria compartida para la
comunicación entre los procesos e hilos mediante archivos de texto.
•
Manejar primitivas que permitan medir el tiempo de ejecución de los procesos/hilos.
Enunciado
La criptografía es el conjunto de estrategias que permiten transformar la información para
ocultarla a terceros no autorizados. Los algoritmos más utilizados se valen de técnicas de
substitución y transposición para modificar el texto original y obtener el texto cifrado. Un
algoritmo antiguo y muy sencillo es el “código cesar” que sólo usa substitución y consiste
en lo siguiente:
Cada letra del texto original se traduce por la letra que está dos posiciones más
adelante en el alfabeto. Las que están al final del alfabeto Y y Z se substituyen
por A y B respectivamente, es decir, que la estrategia de substitución es
circular. Por ejemplo cifrar el texto:
sólo te lo diré mañana al mediodía en la biblioteca
quedaría como:
uqnq vg nq fktg ñcpcoc cn ñgfkqfkc go nc ekenkqvgec
Otro algoritmo muy conocido es el “código murciélago” que consiste en lo siguiente:
Inicialmente la palabra murciélago tiene la característica de poseer todas las
vocales y tener una longitud de 10 caracteres. Así se propone una substitución
letra a número, si la letra está en el texto en claro, bajo el siguiente patrón:
M U R C I E LAG O
0 1 2 3 4 5 6 7 8 9
En consecuencia el mismo mensaje del ejemplo anterior quedaría como
s969 t5 69 d425 07ñ7n7 76 05d49d47 5n 67 b4b640t537
Ud. deberá implantar en C, tres versiones del programa de cifrado y descifrado de texto:
una secuencial y dos versiones concurrentes: una usando procesos y otra usando hilos. Para
las versiones concurrentes, dado que el cifrado o descifrado es evidentemente paralelizable,
se realizará con un árbol de procesos/hilos de tres niveles: raíz, intermedios y hojas, de la
siguiente manera:
Para cifrar se recibe el texto en claro en un archivo de texto y se transforma usando los
códigos cesar y murciélago con los espacios en blanco eliminados. Los procesos/hilos hojas
aplican código cesar para la primera fase de cifrado guardando sus respuestas en archivos
de texto. Los procesos/hilos intermedios recuperan el texto de los archivos creados por sus
procesos/hilos hijos, los concatena en orden y aplica el código murciélago para una segunda
fase de substitución. El proceso/hilo raíz, recibe los textos cifrados de todos sus hijos del
nivel intermedio, elimina los espacios en blancos o tabuladores y concatena ordenadamente
los archivos de respuesta de cada proceso/hilo para finalmente obtener el texto cifrado y
guardarlo en otro archivo de texto.
El programa de descifrado es justamente en reverso, es decir, dado el texto cifrado en un
archivo de texto, se obtiene el texto en claro sin blancos ni tabuladores. Es decir, los
procesos/hilos hojas ejecutan el código murciélago en reverso. Los archivos de respuesta
son recuperados por el nivel de procesos/hilos intermedio y aplican código cesar en reverso.
Finalmente los archivos creados son recuperados por el nivel más alto que sólo concatena
adecuadamente los archivos en claro del nivel intermedio y así definitivamente obtener el
archivo de texto en claro sin blancos ni tabuladores (éstos fueron eliminados cuando el
archivo de texto original se cifró).
Los espacios en blancos se eliminan para evitar la identificación de monosílabos comunes
por eventuales atacantes que obtengan el texto cifrado.
La línea de comandos se realizará de la siguiente forma:
$ cript <-c / -d> ArchivoConTexto (para la versión secuencial)
$ cript_p <-c / -d> NroHijos ArchivoEntradaConTexto ArchivoSalidaConTexto (para la
versión usando procesos)
$ cript_t <-c / -d> NroHijos ArchivoEntradaConTexto ArchivoSalidaConTexto (para la
versión usando hilos)
Donde:
-c Indica que el programa debe cifrar
-d Indica que el programa debe descifrar
NroHijos Indica cuántos procesos/hilos debe crear cada proceso/hilo del nivel 1 y 2.
ArchivoEntradaConTexto Contiene el texto en claro o cifrado (según el caso)
ArchivoSalidaConTexto Contiene el texto en claro o cifrado resultante (según el caso)
Salida del Programa
La salida del programa se compone de un único archivo (ArchivoSalidaConTexto) donde se
almacenará el texto cifrado o en claro según sea el caso. Además, el proceso/hilo raíz debe
imprimir en pantalla el tiempo que tardó toda la ejecución.
En http://www.ldc.usb.ve/~yudith/docencia/ci-3825-taller/Ejemplo_Tiempo.c encontrará un
ejemplo del uso de rutinas para tomar tiempos.
Estrategia Concurrente
Los procesos hojas deben dejar el resultado del descifrado en archivos de texto que serán
recuperados por los procesos de segundo nivel. Estos ensamblan en orden los archivos de
los procesos hojas, agregan los espacios en blancos y también dejarán el resultado de su
procesamiento en archivos. Finalmente la raíz toma los archivos de los procesos de segundo
nivel los ensambla y obtiene el texto en claro.
Detalles de Implementación
• Para la implementación con procesos:
Inicialmente el proceso raíz reparte el trabajo entre sus hijos en partes iguales
siempre que sea posible. En cualquiera caso, a cada proceso hijo le tocará una
porción de texto a cifrar/descifrar. Sucesivamente cada proceso realiza la misma
división entre sus hijos con su respectiva porción de texto. Cada proceso recibirá
(heredará) de su proceso padre inmediato los siguientes valores:
• El nombre del archivo donde se encuentra el texto a cifrar/descifrar.
• La cantidad de caracteres a cifrar/descifrar: nc.
• A partir de qué posición del archivo comienza su parte del texto:inicio.
Ejemplo: Suponga que el archivo inicial tiene el texto
sólo te lo diré mañana al mediodía en la biblioteca
Es decir 51 caracteres a cifrar y se indicó 2 hijos por procesos. El proceso raíz
indicará a su primer hijo, nc=25 e inicio=1, mientras que a su segundo hijo le
indicará, nc=26 e inicio=26. El primer hijo del segundo nivel, asignará a su primer
hijo, nc=12 e inicio = 1 y a su segundo hijo nc=13 e inicio=13. Mientras que el
segundo hijo del segundo nivel, asignará a su primer hijo, nc=13 e inicio = 26 y a su
segundo hijo nc=13 e inicio=39.
Asegúrese de que cada proceso realiza los cálculos necesarios para que al crear a sus
hijos, éstos hereden los valores de nc e inicio que le correspondan.
Una vez que los procesos hojas terminen de cifrar/descifrar su parte, crean un
archivo (cuyo nombre será su PID.txt) que contenga su parte cifrada/descifrada y
terminan.
Los procesos intermedios leen los archivos correspondientes a sus hijos, realizan el
siguiente paso del cifrado/descifrado, crean sus correspondientes archivos (PID.txt),
eliminan los archivos generados por sus hijos y terminan. Finalmente, el proceso
raíz realiza su trabajo correspondiente y crea el ArchivoSalidaConTexto que se
recibe como argumento de llamada.
Los procesos hojas
Cada uno de los procesos hojas abrirá el archivo inicial (cuyo nombre recibe de su
proceso padre inmediato), tomará la porción de texto que le corresponda (revise la
función de librería fseek que le permitirá desplazarse dentro del archivo), realizará
su tarea de cifrar/descifrar y crea su archivo (cuyo nombre será su PID.txt) con el
resultado parcial del cifrado/descifrado.
•
Para la implementación con hilos:
La implementación con hilos tiene algunas diferencias respecto a la implementación
con procesos:
• La comunicación debe hacerse a través de pase de parámetros al momento de
crear los hilos y de estructuras de datos compartidas entre los hilos, haciendo
uso eficiente de la memoria. Note que en la versión de hilos no se deben
crear archivos intermedios.
Observaciones Adicionales
• El archivo de entrada se supone correcto, sólo contiene letras, signos de
puntuación y caracteres especiales si es texto en claro (no se consideran
números par el texto claro).
• Se considera el alfabeto inglés, agregando la ñ.
• Deben escribir un makefile para la compilación óptima.
• Deben estructurar modularmente el programa usando archivos y manejar
correctamente los posibles errores de las llamadas al sistema.
• Recuerde validar las llamadas al sistema con perror() y verificar los
argumentos de entrada.
Entrega
La entrega del proyecto está pautada para el jueves de la semana 7. Ese día Ud.
deberá:
• Subir a Aula Virtual un archivo tar.gz que contenga únicamente los fuentes
(archivos .c y .h) de su proyecto y un archivo Makefile para generar los
ejecutables.
• Un informe de no más de 3 páginas explicando los algoritmos utilizados, el
manejo de la memoria compartida, parámetros de llamada a los
procesos/hilos, comunicación de procesos/hilos, etc. Compare hilos y
procesos en función a la memoria utilizada, tiempo de ejecución, facilidad de
programación, etc. Agregar al informe una tabla de tiempo promediando al
menos 10 ejecuciones, para comparar las tres versiones del proyecto. Calcule
tiempo de tal manera que justifique las respuestas anteriores y sus
conclusiones. Compare las ejecuciones con archivos de entrada con textos
pequeños y pocos hijos (2 y 3) y con archivos de entrada con textos grandes
y muchos hijos (5 y 10). Especifique la arquitectura que usó para realizar las
ejecuciones (Intel dual core, dual processor, etc.).