Printer Friendly

Paralelizacion del algoritmo criptografico GOST empleando el paradigma de memoria compartida.

GOST Cryptographic Algorithm Parallelization Using Shared Memory Paradigm

1. INTRODUCCION

Un algoritmo criptografico se caracteriza por convertir un texto claro, en otro, llamado texto cifrado. El contenido de la informacion es igual al anterior pero solo puede ser entendido por la persona autorizada [1]. Los canales de comunicacion se suponen inseguros cuando se desea enviar informacion confidencial a traves de estos, en cuyos casos se requiere cifrar el mensaje. El presente trabajo se enfoca en la reduccion del tiempo de ejecucion de la implementacion del algoritmo criptografico GOST (Estandar Gubernamental de la Union de Republicas Socialistas Sovieticas). Los detalles del algoritmo fueron publicados en 1990 bajo el nombre de Estandar Sovietico (GOST 28147-89). El estandar provee un nivel de seguridad flexible y puede ser empleado para proteger informacion en sistemas de computo y en redes de computadoras [2, 3].

La investigacion tiene como proposito introducir tecnicas de programacion paralela que permitan mejorar el rendimiento del algoritmo en cuanto a su tiempo de ejecucion. La version paralela del algoritmo, se empleara para proteger la informacion que se envie por un canal de comunicacion. Es necesario destacar que los flujos de datos en los procesos de las redes, son crecientes con una tasa de transferencia elevada. La informacion que se transfiera por la red debe cifrarse en tiempo real y para lograr esto se hace necesario reducir el tiempo de ejecucion del algoritmo.

Para darle cumplimiento al objetivo principal de este trabajo se requiere comprender el algoritmo criptografico GOST asimilando conceptos criptograficos relacionados con las tecnicas empleadas en el, disenar e implementar el algoritmo empleando tecnicas de programacion paralela y validar la solucion paralela implementada.

2. DESARROLLO DEL ARTICULO

2.1. Descripcion del algoritmo GOST

La criptografia se puede clasificar en dos grandes grupos, dependiendo del tipo de llave empleada: criptografia simetrica y asimetrica. La criptografia simetrica se refiere al conjunto de metodos que permiten tener comunicacion segura siempre y cuando, anteriormente, hayan intercambiado la llave. La simetria implica que se emplea la misma llave k para cifrar como para descifrar [1,4].

El GOST es un algoritmo simetrico de cifrado por bloques que emplea una llave de 256 bits, el cual contiene una red Feistel, con 32 iteraciones. Cada iteracion contiene una llave de adicion modulo de 232 , un conjunto de 8 S-box de 4 bits, y una rotacion simple de 11 posiciones. Una particularidad del GOST es que sus S-Cajas pueden ser secretas y pueden ser usadas continuamente como una llave secundaria, la cual es comun a cada aplicacion; de esta forma el tamano de la llave se extenderia a un total de 610 bits [2, 3].

En el estandar [3] se especifican 4 modos en los que el criptosistema puede trabajar, en este trabajo se emplea el modo de sustitucion simple. La Fig. 1 explica el funcionamiento del algoritmo, la que se detalla a continuacion:

El modo empleado plantea dividir el texto plano a cifrar en bloques de 64 bits. Cada bloque es copiado en los registros [R.sub.1] y [R.sub.2]. La llave K de 256 bits es dividida en 8 fragmentos de 32 bits y es almacena en el KSU (unidad de almacenamiento de llaves). El cifrado consiste en 32 iteraciones. La primera iteracion se caracteriza por el valor inicial de registro que es adicionado al primer fragmento de la llave. El resultado de esta operacion es divido en 8 pedazos de 4 bits y enviado a cada una de las S-Cajas (el bloque S). Luego se hace una rotacion de 11 bits a la izquierda. El contenido de es R adicionado al contenido de [R.sub.2] y almacenado en [R.sub.1] y el valor anterior de [R.sub.1] es almacenado en R2 [3],

Las siguientes iteraciones son similares a la primera, la diferencia radica en el orden en el cual son usadas las llaves. En la segunda iteracion, se usa la llave parcial [K.sub.1] del KSU. A las iteraciones 3, 4, 5, 6, 7, 8, se les aplica las llaves parciales [K.sub.2], [K.sub.3], [K.sub.4], [K.sub.5], [K.sub.6], [K.sub.7] respectivamente. Las iteraciones desde la 9 a la 16 y desde la 17 a la 24 usan las mismas llaves parciales. Las iteraciones desde la 25 a la 32, aplican las llaves parciales en orden inverso, o sea, la iteracion 25 usa la llave [K.sub.7], la iteracion [K.sub.6] usa la llave y asi sucesivamente [3],

[FIGURA 1 OMITIR]

2.2. Analisis y diseno paralelo del algoritmo

La seccion anterior caracterizo el funcionamiento del algoritmo GOST. En esta, se realiza un analisis del codigo implementado con el objetivo de identificar la region de codigo caliente o region a paralelizar. Se cuenta con una implementacion en C/C++ que sigue el modelo mostrado en la Fig. 1.

Se realizan varias ejecuciones del algoritmo divido por secciones para determinar la region de mayor procesamiento.

La Fig. 2 muestra los tiempos obtenidos para diferentes tamanos de ficheros e n una arquitectura i7 920. Las pruebas demuestran que el tiempo de ejecucion depende del tamano de lo datos cifrar/descifrar.

Las secciones analizadas son: Creacion de las S-Cajas y Proceso de Cifre/Descifre. El cifrado y descifrado de un fichero de 750 MB se demora 24 segundos, lo que representa un 70 % del tiempo total del algoritmo.

Dentro del proceso de cifre y descifre se encuentran las 32 iteraciones que se realizan a cada bloque de 64 bits que a su vez contiene la rotacion de las 11 posiciones, por lo cual se decide como region a paralelizar el proceso de cifre/descifre de los datos.

[FIGURA 2 OMITIR]

El diseno que a continuacion se propone hace uso de la metodologia de Lan Foster [5]. Esta metodologia permite que el programador se concentre primero en la concurrencia y la escalabilidad y despues se enfoque en los otros aspectos como son la localidad y el rendimiento. La metodologia se divide en 4 etapas. La primera es el particionado, que plantea dividir el problema en tareas mas pequenas. En esta esta etapa suele ignorarse el numero de procesadores disponibles en la arquitectura. Existen 2 formas de particionar un algoritmo, una es la descomposicion de dominio y la otra es descomposicion funcional. La descomposicion de dominio implica dividir los datos en tantas partes como sea posible y la descomposicion funcional platea dividir el algoritmo en funciones que puedan realizarse concurrentemente. La segunda etapa es la comunicacion, la cual se enfoca en el flujo de informacion y coordinacion entre las tareas que son creadas durante la etapa del particionado. La tercera etapa es la de agrupacion, en la cual la tarea y la estructura de la comunicacion son divididas primeramente en dos etapas de diseno y evaluadas respecto de los requerimientos de ejecucion y el costo de implementacion. Si es necesario, las tareas son combinadas en tareas mas grandes para mejorar el rendimiento o reducir los costos del desarrollo. La ultima etapa es el mapeo, donde cada tarea es asignada a un procesador de forma tal que se maximice el uso de la mayoria de los procesadores y se minimice el costo de las comunicaciones. El mapeo puede ser especificamente estatico o determinado en tiempo de ejecucion, buscando el balanceo de carga de los algoritmos [5]. Por tanto se propone:

1- Emplear particionado de dominio, pues no existen funciones que puedan realizarse paralelamente, debido a que el cifrado/descifrado de un bloque es intrinsecamente secuencial. Se necesita crear primero las S-Cajas, luego dividir el bloque a la mitad y cifrarlo con cada porcion de la llave correspondiente. La Fig. 1 explica el funcionamiento del algoritmo para un bloque de 64 bits, por lo cual se decide dividir el texto a cifrar/descifrar en bloques de 64 bits como plantea el GOST.

2- Cada bloque de 64 bits puede ser cifrado/descifrado sin depender del siguiente bloque, por lo que la fase de comunicacion queda exenta.

3- Realizar grupos en dependencia de la cantidad de hilos que contenga la arquitectura donde se ejecute el algoritmo.

4- Asignar a los grupos creados los hilos de ejecucion de forma dinamica, buscando que todos los hilos tengan la misma cantidad de trabajo.

El diseno realizado es aplicado a dos implementaciones empleando el paradigma de memoria compartida, los cuales son: OpenMP y CUDA.

OpenMP es una API para la programacion de aplicaciones paralelas. Esta conformado por tres elementos principales: directivas de compilacion, librerias de rutinas en tiempo de ejecucion y variables de entorno. Se basa en el modelo Fork-Join, donde la tarea es dividida entre el hilo master y un numero de hilos esclavos. Los hilos se ejecutan al mismo tiempo y se distribuyen entre los diferentes procesadores [6-8].

CUDA es un lenguaje orientado a C++ propuesto por NVIDIA para la programacion y manejo de operaciones e instrucciones sobre una tarjeta grafica (GPU). Las GPUs, a parir de la serie G8X de NVIDIA, GeForce, Quadro y la linea Tesla son compatibles con CUDA. La arquitectura de CUDA se descompone de manera jerarquica en varias capas: driver del hardware, una API y su runtime, y dos librerias matematicas de alto nivel de uso comun como son CUFFT y CUBLAS. La API es una extension del lenguaje de programacion C y aporta un compilador que redirige la parte que no se ejecuta en la GPU al compilador por defecto del sistema [9-11].

La diferencia fundamental entre los paradigmas descritos se basa en el dispositivo que pueden explotar. OpenMP solo puede emplear la CPU; CUDA es para tarjetas graficas, pero solo de la compania NVIDIA [9]. Cada uno de estos anade porciones de codigos a la implementacion original. OpenMP es el menos complejo teniendo en cuenta que solo se le adiciona a las secciones a paralelizar los pragmas. Los pragmas son sentencias especiales que le indican al compilar que el siguiente codigo se ejecutara en paralelo [8]. Las tarjetas graficas cuentan con su propia memoria, por lo que CUDA requiere enviar los datos hacia la GPU, calcular el resultado y enviar el resultado a la memoria RAM [11]. Todas estas caracteristicas anaden un tiempo adicional; el objetivo fundamental es identificar el paradigma que logre disminuir mas el tiempo de ejecucion.

3. ANALISIS DE RESULTADOS

El acapite presenta la validacion de la solucion propuesta. Para ello se hace uso de las metricas para evaluar los algoritmos paralelos y se desarrolla una serie de pruebas comparativas. El objetivo de esta seccion es comprobar que el tiempo de ejecucion del algoritmo implementado disminuye respecto a su version secuencial e identificar cual es la tecnica de programacion paralela que logra reducir mas el tiempo logrado con el algoritmo secuencial.

3.1. Aceleracion

El primer criterio tomado en cuenta en la ejecucion de un programa paralelo es analizar la aceleracion (Speed Up) obtenida. La aceleracion es una medida que indica cuantas veces es mas rapido el programa paralelo comparado con el programa secuencial.

La formula de la aceleracion es la que se expone a continuacion [12]:

s = Ts/Tp

Donde Ts es el tiempo de ejecucion secuencial y Tp es el tiempo de ejecucion paralelo.

3.2. Eficiencia

La eficiencia paralela es una medida que denota que tan bien se han utilizado los procesadores, o sea, es la fraccion de tiempo que los procesadores emplean para realizar las tareas asignadas. No depende del tamano del problema [12].

Se puede definir la Eficiencia como:

E = Ts/p x Tp

Donde Ts es el tiempo de ejecucion secuencial, Tp es el tiempo de ejecucion paralelo y P numero de procesadores empleados.

El valor maximo teorico de esta ecuacion es 1.

3.3. Escenarios de Prueba

La validacion de los resultados se realiza teniendo en cuenta las metricas descritas y varios escenarios de pruebas, los cuales se detallan a continuacion:

Arquitectura 1: Intel Core 2 Duo y una tarjeta de video nVidia Geforce GTX 550 Ti.

Arquitectura 2: Intel Core 2 Quad y una tarjeta de video nVidia Geforce GTX 260.

Arquitectura 3: Intel Core i7 920 y una tarjeta de video nVidia Geforce GTX 660.

Las caracteristicas mas significativas de las arquitecturas descritas se especifican en la tabla 1.

Las pruebas se realizaron con cinco ficheros con tamanos 50, 150, 300, 450, 600 y 750 MB respectivamente. El tiempo de ejecucion que se grafica en cada figura es el promedio de un total de 15 iteraciones del algoritmo en cada arquitectura descrita. El sistema operativo donde se ejecutaron las pruebas fue Centos 6.4. Los resultados obtenidos con las implementaciones paralelas son los mismos que se logran con la implementacion secuencial.

El siguiente experimento se realiza con las tres arquitecturas de prueba. Los tiempos que se muestran son los obtenidos con las tres implementaciones.

La tabla 2 muestra que los mejores tiempos de ejecucion se logran con la implementacion realizada en CUDA.

A continuacion se realiza un analisis teniendo en cuenta el speed-up y la eficiencia alcanzada para cada arquitectura de prueba.

[FIGURA 3 OMITIR]

[FIGURA 4 OMITIR]

La Fig. 3 muestra que la ganancia de velocidad se mantiene constante respecto a la obtenida de forma secuencial, aunque la mayor ganancia se logra con la arquitectura 3.

La Fig. 4 muestra para la arquitectura 1 y 2 una ganancia de velocidad constante respecto a la obtenida de forma secuencial con cada uno de los ficheros, aunque para la arquitectura 1, a partir de ficheros con 450 MB el speed up comienza a crecer en 2 unidades mas de lo esperado. La arquitectura 3 tiene un comportamiento similar al descrito para la arquitectura 2, pero para ficheros mayores de 450 MB. El comportamiento del algoritmo para la arquitectura 2 si crece de forma exponencial respecto al obtenido con el algoritmo secuencial. La arquitectura que logra obtener el mejor speed up es la 3.

[FIGURA 5 OMITIR]

La Fig. 5 muestra que los procesadores de las arquitecturas 1 y 2 se emplean eficientemente aproximadamente un 99 %, en cambio en la arquitectura 3 solo se logra emplear eficientemente un 64 %.

4. CONCLUSIONES

El articulo presenta dos implementaciones paralelas empleando OpenMP y CUDA. Ambas implementaciones logran reducir el tiempo de la ejecucion secuencial, pero los mejores tiempos se logran con CUDA, especificamente con la tarjeta 660 GTX de la arquitectura de prueba 3. El proceso de cifre y descifre para esta arquitectura se realiza en 0.94 segundos para un fichero de 750 MB, lo que significa que el algoritmo paralelo con CUDA es aproximadamente 37 veces mas rapido que el tiempo secuencial. Se recomienda implementar el algoritmo empleando OpenCL y comparar los tiempos obtenidos para CPU con OpenMP y para GPU con CUDA.

Marlis Fulgueira-Camilo, Ing.

Centro de Investigacion Tecnologica Integrada

La Habana, Cuba,

mfulgueirac@citi.cu

Omar A. Hernandez-Duany, MSc.

Centro de Investigacion Tecnologica Integrada

La Habana, Cuba,

ohernadez@citi.cu

Venus Henry-Fuenteseca, Ing.

Instituto Superior Politecnico Jose Antonio Echeverria

La Habana, Cuba,

vhenry@ceis.cujae.edu.cu

(Recibido el 15-05-2015. Aprobado el 20-06-2015)

REFERENCIAS

[1] H. C. Van Tilborg & S. Jajodia, Encyclopedia of cryptography and security. Springer Science & Business Media, 2011. 1416p. ISBN 978-14419-5907-2

[2] N. T Courtois, "Security Evaluation of GOST 28147-89 In View Of International Standardisation," Cryptologia, Vol. 36, no. 1,2012, pp. 2-13. D0I:10.1080/01611194.2011.632807

[3] J. Pieprzyk & L. Tombak, "Soviet Encryption Algorithm", University of Wollongong, Department of Computing Science, 1994.

[4] N. Ferguson, B. Schneier, T Kohno, "Cryptography engineering: design principles and practical applications", John Wiley & Sons, 2011, 384p. ISBN: 978-0-470-47424-2

[5] I. Foster, "Designing and building parallel programs," Addison Wesley Publishing Company, 1995, 430p. ISBN: 978-0201575941

[6] OpenMP, "The OpenMP API specification for parallel programming," 2010 URL http://openmp.org.

[7] OpenMP, A. R. Board, "OpenMP Application Pro gram Interface 3.0", 2008. URL: http://www. openmp.org/mp-documents/spec30.pdf

[8] R. Chandra, "Parallel programming in OpenMP" en Morgan Kaufmann Publishers Inc, 2001, 248p. ISBN: 978-1558606715

[9] N. Wilt, "CUDA Handbook: A Comprehensive Guide to GPU Programming", 1st ed. Addison-Wesley Professional, 2013, 528p. ISBN: 9780321809469

[10] S. Cook, "CUDA programming: a developer's guide to parallel computing with GPUs", Newnes, 2012, 576p. ISBN: 978-0124159334

[11] J. Sanders & E. Kandrot, "CUDA by example: an introduction to general-purpose GPU programming", Addison-Wesley Professional, 2010, 312p. ISBN: 978-0131387683

[12] A. Grama, A. Gupta, G. Karyspis, V. Kumar, "Introduction to Parallel Computing", 2nd ed. Addison Wesley, 2003, 656p. ISBN: 978-0201648652
Tabla 1. Caracteristicas del hardware empleado

                                              Memoria

Hardware                     Tipo    Elemento     Reloj    Tipo
                                    de Computo    (MHZ)

Intel Core 2 Duo E7300       CPU         2         2600    DDR2
Intel Core 2 Quad Q9300      CPU         4         2500    DDR2
Intel Core i7 920            CPU         8         2670    DDR3
nVidia Geforce GTX 260       GPU        216        1242    DDR3
nVidia Geforce GTX 550 Ti    GPU        192        1800    DDR5
nVidia Geforce GTX 660       GPU        960        980     DDR5

                                  Memoria

Hardware                     Cantidad    Reloj
                               (MB)      (MHz)

Intel Core 2 Duo E7300         2048       800
Intel Core 2 Quad Q9300        4096       800
Intel Core i7 920              6144       1066
nVidia Geforce GTX 260          896       1998
nVidia Geforce GTX 550 Ti      1024       4104
nVidia Geforce GTX 660         2048       3004

                                     Memoria

Hardware                      Ancho de      Ancho de
                             Bus (bits)   banda (GB/s)

Intel Core 2 Duo E7300           64           12.4
Intel Core 2 Quad Q9300          64           12.4
Intel Core i7 920                64           25.5
nVidia Geforce GTX 260          448          111.9
nVidia Geforce GTX 550 Ti       192           98.5
nVidia Geforce GTX 660          192           144

Tabla 2. Tiempos obtenidos (segundos) con las implementaciones
Secuencial (Sec), OpenMP y CUDA para cada una de las Arquitecturas
(Arq) de pruebas con ficheros de distintos tamanos

                50 MB    150 MB   300 MB

Arq 1 Sec       2.50      7.47    14.96
Arq 2 Sec       2.65      7.94    15.88
Arq 3 Sec       2.29      6.88    13.74
Arq 1 OpenMP    1.25      3.76     7.50
Arq 2 OpenMP    0.66      1.99     3.99
Arq 3 OpenMP    0.45      1.33     2.65
Arq 1 CUDA      0.08      0.24     0.48
Arq 2 CUDA      0.28      0.83     1.47
Arq 3 CUDA      0.07      0.22     0.42

               450 MB    600 MB   750 MB

Arq 1 Sec       22.43    29.85    37.39
Arq 2 Sec       23.83    31.78    39.70
Arq 3 Sec       20.66    27.44    34.32
Arq 1 OpenMP    11.23    14.96    18.72
Arq 2 OpenMP    6.00      7.69     9.97
Arq 3 OpenMP    4.11      5.31     6.66
Arq 1 CUDA      0.73      0.93     1.09
Arq 2 CUDA      1.62      1.76     1.95
Arq 3 CUDA      0.65      0.84     0.94
COPYRIGHT 2015 Fundacion Universitaria Luis Amigo
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:GOST, Gosudarstvenny Standart; Estandar Gubernamental de la Union de Republicas Socialistas Sovieticas
Author:Fulgueira-Camilo, Marlis; Hernandez-Duany, Omar A.; Henry-Fuenteseca, Venus
Publication:Lampsakos
Date:Jul 1, 2015
Words:3290
Previous Article:Los cursos masivos en linea en Coursera y su empleo potencial en los programas de ingenieria en America Latina.
Next Article:Produccion, reservas y sostenibilidad de la energia en Venezuela.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters