UNIVERSIDAD CATÓLICA SANTA MARÍA FACULTAD DE CIENCIAS E INGENIERÍAS FÍSICAS Y FORMALES ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS “OPTIMIZACIÓN DEL TIEMPO DE RESPUESTA EN EL CIFRADO DE DATOS UTILIZANDO COMPUTACIÓN DE ALTO DESEMPEÑO POR GPGPU”. Tesis Presentada por la Bachiller: ANA MADELEYN OPORTO GUZMÁN Para optar el Título Profesional de: INGENIERA DE SISTEMAS AREQUIPA-PERÚ 2015 PRESENTACIÓN Sra. Directora del Programa Profesional de Ingeniería de Sistemas. Sres. Miembros del Jurado. De conformidad con las disposiciones del Reglamento de Grados y Títulos del Programa Profesional de Ingeniería de Sistemas, pongo a vuestra consideración el presente trabajo de investigación titulado: “Optimización del tiempo de respuesta en el cifrado de datos utilizando computación de alto desempeño por GPGPU”, el mismo que de ser aprobado me permitirá optar el Título Profesional de Ingeniería de Sistemas. Oporto Guzmán Ana Madeleyn A mis papás Walther y Marlene, por su amor, paciencia y apoyo incondicional en todos los momentos buenos y no tan buenos de mi vida, los quiero muchísimo, son el mejor ejemplo. A mi hermanita Astrid, por su apoyo moral en cada llamada y conversación por wechat, quiero decirle que la quiero mucho y que admiro su ímpetu de ir más allá de lo razonable. A Edy, que día a día me demuestra que esta vida solo es de valientes. Y a toda mi familia Solo me queda decirles gracias por todo. TABLA DE CONTENIDO ÍNDICE DE TABLAS ................................................................................................... 3 ÍNDICE DE FIGURAS ................................................................................................. 4 RESUMEN .................................................................................................................. 6 ABSTRACT ................................................................................................................. 7 INTRODUCCIÓN ........................................................................................................ 8 CAPITULO I: PLANTEAMIENTO DE LA INVESTIGACIÓN ...................................... 11 1.1. TITULO ........................................................................................................ 11 1.2. Identificación del Problema .......................................................................... 11 1.3. Descripción del problema ............................................................................. 11 1.4. Justificación .................................................................................................. 12 1.5. Objetivos ...................................................................................................... 13 1.5.1. General ..................................................................................................... 13 1.5.2. Específicos ............................................................................................... 13 1.6 Hipótesis ...................................................................................................... 13 1.7 Variables ...................................................................................................... 14 1.7.1. Independientes ......................................................................................... 14 1.7.2. Dependientes ............................................................................................. 14 1.8 Área de Investigación ................................................................................... 14 1.9 Línea de investigación .................................................................................. 14 1.10 Tipo de investigación.................................................................................... 14 1.11 Nivel de investigación ................................................................................... 15 CAPITULO II: FUNDAMENTOS TEÓRICOS ............................................................ 16 2.1 ESTADO DEL ARTE .................................................................................... 16 2.2 MARCO CONCEPTUAL .............................................................................. 27 2.2.1. Algoritmo RSA ............................................................................................. 27 2.3 Unidad de Procesamiento Grafico ............................................................... 29 2.4 Computación de alto desempeño basada en GPGPU (CUDA) .................... 29 2.5 CUDA como una Plataforma de Programación ............................................ 31 2.6 Comparativa entre el uso de la CPU y la GPU ............................................. 32 2.7 Arquitectura de CUDA .................................................................................. 34 2.7.1. Escalabilidad Transparente ....................................................................... 40 1 2.7.2. Asignación de hilos ................................................................................... 41 2.7.3. Acceso a memoria .................................................................................... 41 2.7.4. Otros tipos de memoria ............................................................................. 42 2.7.5. Acceso a memoria en CUDA .................................................................... 45 CAPITULO III: MARCO METODOLÓGICO ............................................................... 53 3.1. Selección del Algoritmo .................................................................................... 53 3.2 La implementación del algoritmo ....................................................................... 53 3.2.1. Implementación del algoritmo RSA mono-núcleo. .................................... 53 3.2.2. Implementación del algoritmo RSA basada en CPU, múltiples núcleos. .. 58 3.2.3. Implementación del algoritmo RSA basada en GPU. ............................... 60 3.3. Pruebas para la implementación del algoritmo ............................................ 62 3.2.1. Criterios de inclusión. ................................................................................ 62 3.2.2. Criterios de exclusión. ............................................................................... 63 CAPITULO IV: RESULTADO .................................................................................... 64 4.1. Evaluación de la implementación en un solo núcleo de CPU. ..................... 64 4.2. Evaluación de la implementación en varios núcleos de CPU utilizando la librería TBB de INTEL. .............................................................................................. 64 4.3. Evaluación de la implementación con GPU, utilizando la tecnología CUDA de NVIDIA. ..................................................................................................... 65 4.4. Ejecución del algoritmo RSA en un solo núcleo.. ......................................... 66 4.5. Ejecución del algoritmo RSA en GPU (CUDA). ............................................ 68 4.6. Ejecución del algoritmo en múltiples núcleos utilizando la librería de INTEL TBB. ............................................................................................................... 71 CONCLUSIONES ...................................................................................................... 75 RECOMENDACIONES Y TRABAJOS FUTUROS .................................................... 77 BIBLIOGRAFÍA ......................................................................................................... 78 ANEXO A: Base de datos utilizada ........................................................................... 80 ANEXO B: Implementaciones Realizadas ............................................................... 104 ANEXO C: Tiempo de Ejecución de las Implementaciones .................................... 109 2 ÍNDICE DE TABLAS Tabla 1: Velocidad de memoria Global vs Local. ...................................................... 48 Tabla 2: Mensaje a ser cifrado, cada carácter representado por su código ASCII. ... 56 Tabla 3: Mensaje cifrado utilizando el algoritmo RSA con clave pública (7,713)....... 57 Tabla 4: Maquinas utilizadas para la realización de pruebas. ................................... 65 Tabla 5: Tiempos mínimos y máximos del proceso de encriptación. ........................ 74 Tabla 6: Tiempos mínimos y máximos del proceso de desencriptación. ................... 74 3 ÍNDICE DE FIGURAS Figura 1: CPU vs GPU GFLOP/s .............................................................................. 32 Figura 2: CPU vs GPU GB/s ..................................................................................... 33 Figura 3: Arquitectura de CUDA ................................................................................ 36 Figura 4: Organización de Hilos Basada en WARPS – Tarjeta de Video GEFORCE 8800GTX. ............................................................................................... 38 Figura 5: Organización de Hilos en la Arquitectura de CUDA. .................................. 39 Figura 6: La falta de Sincronización entre Bloques permite Escalabilidad Transparente. ............................................................................................................ 41 Figura 7: Implementación de memorias en CUDA - GEFORCE 8800GTX, Imagen. ..................................................................................................................... 45 Figura 8: Multiplicación de matrices con varios bloques. .......................................... 50 Figura 9: Tiling en la multiplicación de matrices con CUDA. ..................................... 50 Figura 10: Fases de ejecución del algoritmo de multiplicación en tiles. .................... 51 Figura 11: Procesamiento del mensaje de entrada en un solo núcleo, el cálculo de la encriptación de cada carácter es secuencial y realizado por un solo procesador. ............................................................................................................... 58 Figura 12: Procesamiento del mensaje de entrada en una Core I7 (ocho núcleos) el cálculo de la encriptación de cada carácter es paralelo y realizado por los ocho procesadores. ....................................................................................... 59 Figura 13: Procesamiento del mensaje de entrada en una GPU NVIDIA (20 núcleos), el cálculo de la encriptación de cada carácter es paralelo y realizado por los veinte procesadores. ..................................................................................... 62 4 Figura 14: Ejecución en CPU simple, Maquina 1: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. ............................................. 66 Figura 15: Ejecución en CPU simple, Maquina 2: a la izquierda proceso de encriptación a la derecha proceso de desencriptación .............................................. 67 Figura 16: Ejecución en CPU simple, Maquina 3: a la izquierda proceso de encriptación a la derecha proceso de desencriptación .............................................. 67 Figura 17: Ejecución en CPU simple, Maquina 4: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. ............................................. 68 Figura 18: Ejecución en GPU con CUDA, Maquina 1: a la izquierda proceso de encriptación a la derecha proceso de desencriptación .............................................. 69 Figura 19: Ejecución en GPU con CUDA, Maquina 2: a la izquierda proceso de encriptación a la derecha proceso de desencriptación .............................................. 69 Figura 20: Ejecución en GPU con CUDA, Maquina 3: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. ............................................. 70 Figura 21: Ejecución en GPU con CUDA, Maquina 4: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. ............................................. 70 Figura 22: Ejecución en CPU con múltiples núcleos, Maquina 1: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. .......................... 71 Figura 23: Ejecución en CPU con múltiples núcleos, Maquina 2: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. .......................... 72 Figura 24: Ejecución en CPU con múltiples núcleos, Maquina 3: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. .......................... 72 Figura 25: Ejecución en CPU con múltiples núcleos, Maquina 4: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. .......................... 73 5 RESUMEN Hoy en día el cifrado de información es un campo que requiere de mucha capacidad computacional, los algoritmos de cifrado de datos utilizan más recursos computacionales según el tamaño de las claves que usan y de la cantidad de información a cifrar, surgiendo la problemática del tiempo de respuesta de estos algoritmos, la cual puede verse solucionada utilizando técnicas de alto desempeño. En esta tesis se trabajó en la optimización del tiempo de respuesta en el cifrado de datos utilizando computación de alto desempeño por GPGPU (General Purpose Graphical Processing Unit), específicamente la tecnología CUDA de NVIDIA, logrando acelerar el proceso de codificación y decodificación, específicamente se realizó la implementación del algoritmo de encriptación RSA, consiguiendo una mejora en el tiempo de procesamiento que se comparó con la implementación en CPU y la implementación de CPU por múltiple núcleo usando la librería TBB de INTEL. Además se propuso una implementación que permite realizar el proceso de encriptación y des-encriptación utilizando como entrada un conjunto de archivos de texto plano, ésta propone componentes de software que usan tecnología CUDA. Palabras Claves. Algoritmo de encriptación, RSA, TBB, Computación de alto desempeño GPGPU, CUDA. 6 ABSTRACT Today encryption of information is a field that requires a lot of computing capacity, data encryption algorithms use more computing resources according to the size of the keys used and the amount of information to be encrypted, raising the issue of time response of these algorithms, which can be solved using techniques with high performance. In this thesis we worked on optimizing the response time data encryption using high performance computing for GPGPU (General Purpose Graphical processing Unit), specifically the NVIDIA CUDA technology, achieving accelerate the process of encoding and decoding, specifically implementation performed RSA encryption algorithm, achieving an improvement in processing time compared with the CPU implementation and deployment of multi-core CPU using INTEL TBB library. In addition an implementation that allows the encryption process and de-encryption using as input a set of plain text files, it proposes software components using CUDA technology is proposed. Keywords. Encryption algorithm, RSA, TBB, High Performance Computing GPGPU, CUDA. 7 INTRODUCCIÓN En el campo de la investigación de encriptación, la utilización de diversos métodos de procesamiento de texto plano, ha demostrado ser una opción confiable para resguardar información que no debe de ser pública, sin embargo la principal falencia de las implementaciones actuales de estos algoritmos requieren de un costo de procesamiento muy alto, mejores implementaciones de estos algoritmos permitirían la codificación y decodificación de una forma más eficiente, pudiendo extender la capacidad de respuesta de procesamiento que es requerida en la actualidad. Existen muchos algoritmos para el cifrado y descifrado de información entre ellos los más utilizados según [1] son el RSA, el AES, el triple DES y el DES, estos algoritmos están basados en claves asimétricas (el RSA) y claves simétricas. En esta tesis se propone una optimización del tiempo de respuesta del algoritmo RSA por ser el algoritmo más utilizado en procesos de encriptación de clave asimétrica [1], Se ha elegido la tecnología de procesamiento de alto desempeño CUDA de NVIDIA, hoy en día los costos de este tipo de tecnología han bajado y su uso se ha expandido. CUDA es una arquitectura de computación paralela desarrollada por la empresa NVIDIA, dicha tecnología permite un incremento en el desempeño de cálculos computacionales aprovechando la capacidad computacional de la GPU. Teniendo en cuenta que hay millones de GPU vendidas que soportan la tecnología CUDA, desarrolladores de software, científicos e investigadores están encontrando usos de amplio alcance para ésta, incluyendo procesamiento de imágenes, video, biología, química computacional, simulación de fluidos dinámicos, reconstrucción de imágenes por computadora, análisis sísmico, etcétera. 8 La tecnología CUDA es parte de la evolución de las placas de video desde una arquitectura de pipeline de funciones fijas (entrada del pipeline, transformaciones del modelo, iluminación, simulación de cámara, rasterización, texturizado y superficies ocultas) dedicada exclusivamente al procesamiento de píxeles y vértices a una nueva era de GPU (Graphics Processing Unit) de Propósito General (GPGPU) que permiten la ejecución de cualquier aplicación que pueda ser paralelizada. Esta evolución no fue pensando directamente en aplicaciones de propósito general, sino que ésta arquitectura permite una significativa mejora en el balance de carga, aprovechándose mejor la potencia del dispositivo de GPU. Además provee una mayor flexibilidad para el desarrollador en conjunto con la reducción en la dificultad de programación para el desarrollador, dado que ahora se cuenta con un solo set de instrucciones mientras que antes se necesitaban dos sets, uno para procesar píxeles y otro para procesar vértices. Los dispositivos de GPU que fueron diseñadas para realizar grandes cantidades de cómputo, contienen múltiples procesadores que aprovechan la naturaleza paralela de las aplicaciones gráficas, y por lo tanto, gracias a CUDA, se pueden adaptar para realizar cualquier tarea que tome ventaja del paralelismo para lograr mayores velocidades de cómputo. El presente trabajo está organizado de la siguiente manera: En el capítulo I se realizó el planteamiento de la investigación, definiendo el problema, el alcance de la solución propuesta, objetivos, hipótesis, variables y lo referente al nivel y tipo de investigación que se propone. En el capítulo II se expone el estado del arte de los temas concernientes a la investigación, es decir, cifrado de datos y computación de alto desempeño. También 9 se describe el marco conceptual, los algoritmos y las técnicas empleadas para el desarrollo de la investigación. En el capítulo III se describe el Marco Metodológico que se ha seguido para completar la investigación, se proponen tres variantes de implementación del algoritmo RSA, la primera basada en una CPU, la segunda en varias CPU utilizando la tecnología TBB de la empresa INTEL, en la tercera variante se presenta la implementación del algoritmo RSA utilizando la tecnología de NVIDIA para GPU con CUDA. En el capítulo IV se presentan los resultados de la investigación, es decir, los cuadros de tiempo vs tamaño en bytes de la entrada del algoritmo RSA utilizando las tres variantes descritas en el capítulo III y utilizando cuatro máquinas con diferentes características en Hardware. 10 CAPITULO I: PLANTEAMIENTO DE LA INVESTIGACIÓN 1.1. TITULO “Optimización del tiempo de respuesta en el cifrado de datos utilizando computación de alto desempeño por GPGPU”. 1.2. Identificación del Problema El envío de información privada entre distintas entidades ha creado la necesidad de utilizar diversos mecanismos para evitar que esta información pueda ser accedida por alguien a quién no va dirigida, es así que nace la criptografía, que provee distintos mecanismos para la codificación y decodificación de información permitiendo un intercambio seguro de ésta. En la actualidad el volumen de información que debe de ser protegida es muy grande, requiriendo técnicas de encriptación muy eficientes en cuanto al tiempo de codificación y decodificación; es así que surgen técnicas cómo el algoritmo RSA, que es un algoritmo muy simple y eficiente en cuanto a las características antes mencionadas, sin embargo debido a la necesidad de procesamiento rápido es que se requiere acelerar las implementaciones que puede tener este algoritmo. 1.3. Descripción del problema Hoy en día el cifrado de información es un campo que requiere de mucha capacidad computacional, los algoritmos de cifrado de datos utilizan más recursos computacionales según el tamaño de las claves que usan y de la cantidad de información a cifrar, surgiendo la problemática del tiempo de respuesta de estos algoritmos, por ejemplo, en un sistema de envío de operaciones interbancarias en tiempo real se necesita cifrar y descifrar rápidamente esta información a fin de tener 11 tiempos de respuesta aceptables para las entidades usuarias, la problemática del tiempo de respuesta de los algoritmos de cifrado puede verse solucionada utilizando técnicas de alto desempeño, otro ejemplo, puede ser el tratamiento de grandes cantidades de datos como repositorios de libros electrónicos, para tener un mejor manejo de estos en cuanto a privacidad y seguridad. 1.4. Justificación Mejores implementaciones de algoritmos de encriptación permitirían la codificación y decodificación más rápida de información pudiendo extender la capacidad de respuesta de procesamiento que es requerida en la actualidad. Hoy en día los costos de estas arquitecturas de varios procesadores y clusters han bajado y su uso se ha expandido; también se le ha dado mucha importancia a los procesadores gráficos, ya que cuentan con centenas de procesadores que han sido usadas con mucho éxito para aplicaciones de propósito general, las investigaciones en el campo de computación de alto desempeño basados en GPGPU (General Purpose Graphical Processing Unit) han logrado que esta plataforma se convierta en robusta. La justificación comercial sería el aumento de la capacidad de procesamiento de información de operaciones en línea que pueden realizar las entidades financieras comprometidas en estas transacciones de información, ya que mientras más operaciones se puedan procesar más clientes se podrán atender. 12 1.5. Objetivos 1.5.1. General Optimización del tiempo de respuesta en el cifrado de datos utilizando computación de alto desempeño por GPGPU, logrando acelerar el proceso de codificación y decodificación de algoritmos de encriptación obteniendo mejores tiempos de respuesta para este tipo de proceso. 1.5.2. Específicos  Implementar el algoritmo RSA en CUDA, en una sola CPU y en múltiple CPU para el proceso de encriptación de archivos de texto plano, esta propuesta constará de una aplicación Stand-alone que tendrá como entrada archivos de texto plano y tendrá dos tipos de salida, archivos planos encriptados y desencriptados según la opción elegida.  Comparar el algoritmo RSA implementado con CUDA contra la implementación basada en CPU y en Multi-CPU en cuanto al tiempo requerido para la codificación y decodificación de información, demostrando que es superior.  Demostrar que aumentando el número de núcleos en la GPU podemos mejorar el tiempo de ejecución de algoritmo. 1.6 Hipótesis El uso de CUDA para la implementación del algoritmo de encriptación RSA mejoraría el tiempo del proceso de codificación y decodificación de información 13 comparada con la implementación en CPU simple y múltiple, para el procesamiento de archivos planos. 1.7 Variables 1.7.1. Independientes Computación de alto desempeño por GPGPU 1.7.1.1 Indicadores  Cantidad en Bytes del mensaje a cifrar  Número de núcleos de la GPU a utilizar.  Número de núcleos de la CPU a utilizar. 1.7.2. Dependientes Tiempo de respuesta en el cifrado de datos. 1.8 Área de Investigación Computación paralela. 1.9 Línea de investigación Computación de alto desempeño. 1.10 Tipo de investigación Según la finalidad de esta tesis, ésta se basa en una investigación aplicada, ya que se tiene como finalidad primordial, la optimización del funcionamiento de un algoritmo de encriptamiento como RSA aplicando la tecnología CUDA. 14 1.11 Nivel de investigación De acuerdo a la naturaleza del estudio de la investigación, el nivel de ésta reúne las características de un estudio descriptivo, explicativo y correlacionado. 15 CAPITULO II: FUNDAMENTOS TEÓRICOS 2.1 ESTADO DEL ARTE A continuación se lista investigaciones referentes al tema de propósito de esta tesis: a. En el trabajo realizado por Hao Wu de la Implementation of public key algorithms in CUDA, Department of Computer Science and Media Technology Gjøvik University College, 2010, Tesis Maestria, propone: [2] En el campo de la criptografía, los algoritmos de clave pública son ampliamente conocidos por ser más lentos que otras alternativas de clave simétrica por tener su base en la aritmética modular. La aritmética modular por ejemplo RSA y Diffie Hellman es pesado computacionalmente en comparación a los algoritmos simétricos que dependen de las operaciones simples como cambiar de bits y XOR. Por lo tanto, cómo hacer una aplicación más eficaz y más rápida de algoritmos de clave pública es de preocupación pública. Con el desarrollo del campo de la GPGPU (computación de propósito general en el procesamiento de unidades gráficas), más y más problemas informáticos se resuelven utilizando en paralelo la propiedad de la GPU (unidad de procesamiento gráfico). CUDA (Arquitectura Unificada de Dispositivos de Cómputo) es un marco de trabajo que hace que la GPGPU sea más accesible y fácil de aprender para los programadores en general. Esto es porque se basa en C y oculta muchos de los complicados detalles de cómo funciona la GPU de un desarrollador de CUDA. Utilizando únicamente las propiedades de la GPU a través de CUDA se ha 16 incrementado en gran medida la solución de muchos problemas computacionales. Multiplicación de enteros grandes es uno de los problemas en el momento de la construcción en aritmética modular. Ejecución de los algoritmos de clave pública mediante el uso de las propiedades paralelas de la GPU en la multiplicación modular y exponenciación modular puede ser una solución para este problema. El objetivo de esta investigación es estudiar y analizar la mayoría de los algoritmos relacionados a la multiplicación modular y exponenciación modular, para luego diseñar y hacer una implementación de un algoritmo de clave pública en CUDA. Por último, este proyecto comparará el rendimiento entre la aplicación de la GPU y la ejecución de la CPU con el fin de estudiar la posibilidad de mejorar el rendimiento de los algoritmos de clave pública. Las preguntas de investigación se dividen en cuatro grupos, el primero con respecto a la multiplicación modular y exponenciación modular de grandes enteros y su paralelismo, la segunda sobre la integración de la multiplicación modular paralelo y exponenciación modular en el algoritmo de clave pública, la tercera es relativa a la optimización del algoritmo, y finalmente con respecto a la comparación de rendimiento del algoritmo de clave pública entre la GPU, la implementación y la ejecución de la CPU. Discusión: Esta Tesis de maestría muestra los principios matemáticos de aritmética modular necesarios para implementar el algoritmo RSA en una computadora convencional, esta investigación es la base principal para la 17 presente tesis, ya que realiza un estudio de la utilización de la GPU contra la CPU, pero las pruebas no contemplan múltiples tamaños de los archivos de entrada para probar las implementaciones, así mismo, solo compara la GPU contra una implementación en CPU de un núcleo, la presente tesis agrega la comparación con la implementación de varios núcleos utilizando la tecnología TBB de INTEL. b. En el trabajo realizado por ADRIAN POUSA del Algoritmo de cifrado simétrico AES - aceleración de tiempo de cómputo sobre arquitecturas multicore, de la Universidad Nacional de la Plata, 2011, Tesis, propone: [1] AES es uno de los algoritmos de criptografía más usados en la actualidad, con el crecimiento de las redes y la información que se maneja hoy en día puede ser necesario cifrar un volumen muy grande de información para lo que se requiere mayor velocidad en los procesadores, pero esto actualmente no es posible debido a que los procesadores han llegado al límite de velocidad por problemas térmicos y de consumo, por esta razón se está incrementando la cantidad de procesadores en los equipos. Discusión: [1] El objetivo de esta tesis es demostrar la aceleración en el tiempo de cómputo del algoritmo criptográfico Advanced Encryption Standard (AES) con clave de tamaño 128bits, que se obtiene al aprovechar el paralelismo que proveen las arquitecturas multicores actuales utilizando herramientas de programación paralela, esta 18 investigación sirve como una base para la presente tesis porque expone la implementación de un algoritmo de encriptación en un ambiente paralelo, los resultados muestran que el aumento del número de procesadores mejoran el rendimiento de un algoritmo de encriptación. c. En el trabajo realizado por Pedro Miguel Costa Saraiva de OpenSSL acceleration using Graphics Processing Units, Técnico de Lisboa, 2013, Tesis Maestria, propone: [3] La criptografía se define como el estudio de las técnicas centradas en la seguridad de la información. Típicamente, una implementación de la criptografía es computacionalmente pesada, lo que lleva a problemas de rendimiento en sistemas de uso general, añadiendo la posibilidad de descarga de las operaciones criptográficas a una unidad de procesamiento gráfico (GPU) en un extenso, una biblioteca criptográfica de código abierto como OpenSSL sería extremadamente útil para aligerar la carga de la CPU para la lógica de la aplicación. Las GPUs, mientras que originalmente fueron diseñadas para acelerar el procesamiento de gráficos, ha sido recientemente adquirida por el uso no relacionado, la computación de propósito general, debido a su enorme potencia de cálculo paralelo. Como tal, dos marcos de trabajo principales se han diseñado para tomar ventaja de una GPU para la computación de propósito general se han desarrollado en los últimos años: CUDA propiedad de NVIDIA y OpenCL estándar abierto del Grupo Khronos. En este artículo presentamos la aceleración de alto rendimiento de la biblioteca OpenSSL utilizando tanto OpenCL y CUDA, específicamente 19 para los algoritmos RSA y AES. Nuestra evaluación demuestra que AES descifrado puede cuarenta veces más rápido que la ejecución de la CPU estándar, y que las claves RSA se pueden generar diez veces más rápido que en una CPU. También estudiamos las posibilidades de cifrado CBC y RSA de cifrado, y la conclusión y por qué esos algoritmos son inviables para funcionar en una GPU dentro de OpenSSL. Discusión: Este estudio muestra la comparación entre dos técnicas la implementación del algoritmo RSA, con CUDA y OPENCL, esta investigación muestra la inviabilidad de la implementación en OPENCL, es por eso que en la presente tesis se descartó el uso de esta tecnología, pero se tomó en cuenta porque la implementación en CUDA es diferente a la implementación de [2]. d. En el trabajo realizado por Maksim Bobrov de Cryptographic Algorithm Acceleration Using CUDA Enabled GPUs in Typical System Configuration, 2010, Tesis Maestría, propone: [4] La necesidad de cifrar los datos es cada vez más necesaria. A medida que el tamaño de los conjuntos de datos sigue creciendo, la velocidad de cifrado debe aumentar para mantener el ritmo o se convertirá en un cuello de botella. CUDA GPU ha demostrado ofrecer mejoras de rendimiento en comparación con las CPU convencionales para algunos problemas de datos intensos. Esta tesis evalúa la aplicabilidad de CUDA, GPU para acelerar la ejecución de algoritmos criptográficos, que se utilizan cada vez más para 20 el crecimiento de cantidades de datos y por lo tanto requerirá cifrado significativamente más rápido. Específicamente, el ambiente CUDA se utilizó para implementar y experimentar con tres algoritmos criptográficos distintos - AES, SHA-2, y Keccak, con el fin de mostrar la aplicabilidad para diversas clases de algoritmos criptográficos. Ellos se llevaron a cabo en un sistema que emula las condiciones presentes en un entorno real, se evaluaron los efectos de la descarga de estas tareas de la CPU a la GPU. Aceleraciones de hasta 2,6 veces con respecto a la CPU se observaron para single - kernel AES, pero SHA - 2 y Keccak no funcionan tan bien como en la GPU como en la CPU. Multi - kernel AES vio aceleraciones más de un solo núcleo AES de hasta 1.4x, 1.65x, y 1.8x para dos, tres y cuatro núcleos, respectivamente. Esto se traduce en aceleraciones entre 3,6x y 4,7x más implementaciones de CPU de AES. La introducción de una carga de la CPU tuvo un efecto mínimo en el rendimiento, mientras que una carga GPU disminuyo el rendimiento hasta en un 4%. En general, CUDA GPU parece tener tal potencial para mejorar rendimientos de cifrado si se selecciona un algoritmo que permita ser paralelizable. Discusión: Esta Tesis de maestría muestra la implementación de distintos algoritmos de cifrado en GPU utilizando CUDA, se muestra que no todos los algoritmos de cifrado son paralelizables en GPU es por eso que la presente tesis toma al algoritmo RSA como base para su estudio, al ser este un algoritmo altamente paralelizable por pertenecer al patrón paralelo 21 de algoritmos de Elementwise, es decir, algoritmos donde el procesamiento de un elemento no depende del resultado de otro. e. En el trabajo realizado por Carla Ramiro Sánchez sobre Algoritmos Paralelos para la resolución de problemas de mínimos cuadrados basados en transformaciones ortogonales sobre GPUs y multiprocesadores Presentado, UNIVERSIDAD DE VALENCIA, Tesis Maestría, 2010, propone: [5] La resolución de sistemas de ecuaciones lineales sobre determinados es un problema que se presenta con frecuencia en la computación científica. Algunos ejemplos pueden encontrarse en campos como el procesado de señal, resolución de problemas en electromagnetismo, simulación de dinámica molecular, econometría etc. La modelización de estos problemas da lugar a sistemas de ecuaciones lineales o problemas lineales de mínimos cuadrados con matrices densas, a veces enormes. Uno de los métodos que se utiliza habitualmente para resolver sistemas de ecuaciones lineales sobre determinados es el de mínimos cuadrados. Los procedimientos más fiables para resolver este problema conllevan la reducción de la matriz a alguna forma canónica mediante transformaciones ortogonales, como por ejemplo: la descomposición de Cholesky, descomposición en valores singulares o descomposición QR, siendo esta última la más comúnmente utilizada. En la actualidad, las plataformas de múltiple núcleo, entre ellas las GPUs, lideran el mercado de los computadores. El rápido avance, tanto en la programación de los procesadores gráficos como en su flexibilidad, ha 22 permitido utilizarlos para resolver un amplio rango de complejos problemas con altas necesidades computacionales. Es lo que se conoce como GPGPU (General-Purpose Computing on the GPU). Discusión: Esta Tesis de maestría propone el uso de GPU pero aplicado a la resolución de problemas de mínimos cuadrados basados en transformaciones ortogonales, este estudio sirve como una base para la implementación de la variante del algoritmo RSA en GPU propuesta en la presente Tesis. f. En el trabajo realizado por Hong Zhang de Comparison and analysis of GPGPU and parallel computing on Multi-Core CPU, et al, International Journal of Information and Education Technology, paper, 2012, propone: [17] Hay dos maneras de mejorar el rendimiento de un algoritmo de computación, de uso general en computación y el uso de computación paralela de CPU múltiple núcleo. De la comparación y análisis, contrastar la principal diferencia entre ellos, se llega a la conclusión de que la GPU es adecuado para el procesamiento a gran escala de carga de datos en paralelo de la computación de alta densidad pero la lógica de ramificación relativamente simple, sin embargo, la CPU es más adecuado para el procesamiento complejo cálculo de la lógica. Ahora, el aspecto de la arquitectura de la GPU CUDA hace más adecuado para uso general de la computación. 23 El algoritmo criptográfico es un algoritmo típico informático intensivo, este trabajo toma la exponenciación modular del algoritmo RSA, por ejemplo, a través de la comparación y el análisis de la implementación de la GPU y la ejecución de la CPU, los resultados del experimento demuestran: Que la aplicación GPU puede alcanzar más de 45 veces en tiempo de respuesta en comparación con la implementación de varios núcleos de CPU del RSA. Discusión: Este artículo muestra un estudio interesante de implementaciones del algoritmo RSA bajo el enfoque de CUDA, la presente Tesis se basa en el modelo de implementación para aritmética modular presente en este artículo. g. En el trabajo realizado por Yu-Shiang Lin et al de Efficient Parallel RSA Decryption Algorithm for Many-core GPUs with CUDA, Department of Computer Science and Information Engineering Chang Gung University Taoyuan 333, Taiwan, paper, propone: [20] La criptografía es una técnica importante entre varias aplicaciones. En las telecomunicaciones, la criptografía es necesaria cuando se comunica un medio que no se confía en la red. RSA es un algoritmo de criptografía de clave pública a utilizar un par (N, E) como la clave pública y D como la clave privada. El N es el producto de dos grandes números primos p y q que se mantiene en secreto. Es muy difícil y no hay algoritmos de tiempo polinómico conocido puede ser utilizado para extraer p y q de un gran número N. Hay muchos métodos de factorizar 24 números grandes que se han propuesto. Las ventajas de la potencia de cálculo y ancho de banda de memoria para las GPU modernas han hecho que las aplicaciones se conviertan en un tema muy importante. En este trabajo, hemos propuesto un algoritmo eficiente paralelo basado en la técnica RSA para las GPU con múltiples núcleos usando la tecnología CUDA. Los resultados experimentales mostraron que el algoritmo basado en GPU propuesto puede lograr 1197.5x aceleración media en comparación con el algoritmo basado en la CPU, y dentro de un plazo razonable para averiguar el resultado de factorizar números grandes. Discusión: Este artículo muestra la implementación del algoritmo RSA en GPU utilizando CUDA, la principal contribución del artículo es la implementación de técnicas de factorización de números grandes, los resultados han permitido llegar a una gran mejora en el tiempo de procesamiento de su implementación. h. En el trabajo realizado por Tomoiagă Radu Daniel de AES Algorithm Adapted on GPU Using CUDA for Small Data and Large Data Volume Encryption, Stratulat Mircea, 2011, International journal of applied mathematics and informatics, Paper, propone: [24] En este artículo se presenta una implementación de AES en NVIDIA GPU usando CUDA. Los resultados de nuestras pruebas muestran que la aplicación CUDA puede ofrecer aceleraciones de casi cuarenta veces en comparación con la CPU. Las pruebas se llevaron a cabo en dos direcciones: Ejecutando las pruebas en una pequeña cantidad de datos 25 que se encuentra en la memoria y una gran cantidad de información que se almacena en archivos en disco, el tiempo de acceso a la información en el disco duro es añadido a la vez al cifrado. Discusión: El objetivo de este trabajo es estudiar la posibilidad de usar una solución informática alternativa en la criptografía, el uso de una unidad de procesamiento gráfico para realizar cálculos de procesamiento no gráfico. Se utilizó la unidad de procesamiento gráfico como un coprocesador criptográfico para obtener más potencia de cálculo y mejorar el tiempo de ejecución para el algoritmo AES. 26 2.2 MARCO CONCEPTUAL 2.2.1. Algoritmo RSA Los sistemas de cifrado con clave pública tuvieron su inicio con la propuesta de Diffie y Hellman en noviembre del año 1976 para realizar un intercambio de clave computacionalmente seguro, usando para ello el problema del logaritmo discreto. Sin embargo, aunque dicha propuesta se convierte en un hito que revoluciona el mundo de la criptografía en aquellos años, hasta ese momento sólo de tipo simétrica y con una sola clave secreta, no permitía realizar una cifra real de información o la firma digital sobre un documento. En febrero de 1978, es decir poco más de un año después de aquel intercambio de clave propuesto por Whitfield Diffie y Martin Hellman, otros tres investigadores norteamericanos, Ron Rivest, Adi Shamir y Leonard Adleman, proponen un sistema de cifra que llevará las iniciales de sus apellidos y el algoritmo se patenta como RSA. A diferencia del intercambio de clave de DH, que basaba su fortaleza en la dificultad computacional de calcular logaritmos discretos en primos muy grandes, RSA basa su fortaleza en la dificultad computacional de factorizar un número compuesto muy grande, producto de dos primos grandes, y encontrar por tanto tales factores primos. Ambos problemas tienen una complejidad algorítmica similar y son inabordables para la capacidad mundial de cómputo en nuestros días cuando se trata de valores por encima de miles de bits. No fueron fáciles los primeros años de este algoritmo pues nadie creía en su utilidad. Sin embargo, el tiempo fue dándoles la razón a sus inventores y finalmente se convirtió en un estándar, más 27 precisamente PKCS #1 RSA Cryptography Standard. Sin embargo, aunque Rivest, Shamir y Adleman son los autores de RSA, el mismo algoritmo de cifra asimétrico basado en la dificultad de factorizar números grandes fue descubierto mucho antes. En el año 1969 el Government Communications Headquarters GCHQ en Gran Bretaña comienza a trabajar en la idea de poder distribuir claves a través de una cifra no simétrica, llegando en el año 1973 -cinco años antes- a la misma conclusión que los creadores de RSA. La seguridad del algoritmo RSA se basa en la dificultad computacional que conlleva encontrar los dos factores primos de un número compuesto muy grande, resultado del producto de éstos, donde sus primos también son números grandes. Esto es lo que matemáticamente se conoce como el problema de la factorización entera, uno de los problemas denominados No Polinomiales o de tipo NP, muy usados en la criptografía. Se trata de un problema que en un sentido el cálculo es muy fácil y rápido (por ejemplo multiplicar dos números primos) pero que en sentido contrario (por ejemplo, encontrar esos dos factores conocido el producto) se vuelve computacionalmente intratable a medida que la entrada es cada vez mayor. Es decir, requiere de unos recursos informáticos excesivos y, por tanto, de un tiempo de cálculo exorbitante. 28 2.3 Unidad de Procesamiento Grafico La unidad de procesamiento grafico (en sus siglas en Inglés GPU), es un dispositivo de co-procesamiento grafico que se encuentra localizado en las tarjetas gráficas de las computadoras actuales, que durante años ha estado asociado al sector de los videojuegos, una GPU tiene núcleos de procesamiento de datos tal como tienen las CPU, además cuentan con un BUS de datos y una memoria volátil de acceso dinámico (RAM). Las tarjetas gráficas realizan cálculos para renderizar imágenes en las pantallas de una computadora, pero hoy en día las GPU están siendo utilizadas para propósito general, es decir, sus unidades de procesamiento están siendo usadas para cálculos ya no solo de tipo gráfico. 2.4 Computación de alto desempeño basada en GPGPU (CUDA) La tecnología de CUDA es parte de la evolución de las placas de video desde una arquitectura de pipeline de funciones fijas (Entrada del pipeline, Transformaciones del modelo, Iluminación, Simulación de cámara, Rasterización, Texturizado y Superficies ocultas) dedicada exclusivamente al procesamiento de píxeles y vértices a una nueva era de GPU (Graphics Processing Unit) de Propósito General (GPGPU) que permiten la ejecución de cualquier aplicación que pueda ser paralelizada. Esta evolución no fue pensando directamente en aplicaciones de propósito general, sino que ésta arquitectura permite una significativa mejora en el balance de carga, aprovechándose mejor la potencia del dispositivo de GPU. Además provee una mayor flexibilidad para el desarrollador en conjunto con la reducción en la dificultad de programación para el desarrollador, dado que ahora se cuenta con un solo set de instrucciones mientras que antes se necesitaban dos sets, 29 uno para procesar píxeles y otro para procesar vértices. Los dispositivos de GPU que fueron diseñadas para realizar grandes cantidades de cómputo, contienen múltiples procesadores que aprovechan la naturaleza paralela de las aplicaciones gráficas, y por lo tanto, gracias a CUDA, se pueden adaptar para realizar cualquier tarea que tome ventaja del paralelismo para lograr mayores velocidades de cómputo. En Noviembre del 2006 NVIDIA lanzó la tarjeta gráfica GEFORCE 8800 GTX siendo la primera tarjeta que fue construida con la arquitectura CUDA. A diferencia de las generaciones anteriores no se dividían los recursos en renderización y propósito general, ya que la arquitectura CUDA incluye un pipeline de shaders unificado que permite a cada unidad lógica aritmética (ALU) ser utilizada para propósitos generales, estos dispositivos ALU han sido construidos siguiendo los estándares de la IEEE para operaciones de punto flotante, y pueden escribir en una zona de memoria conocida como “memoria compartida” [9]. Para alcanzar el máximo número de programadores posible NVIDIA tomó el Estándar C y le agregó algunas palabras clave para la utilización de las características de la arquitectura CUDA, es así como surge CUDA C debido a que la computación está cambiando de un procesamiento central en la CPU a un co- procesamiento entre la CPU y la GPU; para establecer este nuevo paradigma computacional NVIDIA invento la arquitectura de computación paralela CUDA que es soportada en las líneas de GPU de GEFORCE, ION, QUADRO, y TESLA. La tecnología de CUDA ha sido bien recibida en el área de investigación científica, por ejemplo CUDA ahora acelera AMBER un programa de simulación molecular dinámica utilizado por más de sesenta mil investigadores académicos y de compañías farmacéuticas para acelerar el descubrimiento de nuevas medicinas. En 30 el ámbito financiero, NUMERIX and COMPATIBLE anunció el soporte de CUDA para una nueva aplicación de simulación de riesgos y alcanzó una mejora de dieciocho veces el tiempo de ejecución. NUMERIX es utilizado por cerca de 400 instituciones financieras [9]. 2.5 CUDA como una Plataforma de Programación A los pocos meses del lanzamiento de la tarjeta de video GEFORCE 8800 GTX, la corporación NVIDIA hizo pública la primera versión de un compilador para el lenguaje CUDA C, así CUDA C se convirtió en el primer lenguaje específicamente diseñado por una empresa de desarrollo de gráficas para facilitar la computación de carácter general en sus chips [9]. La corporación NVIDIA también provee los controladores necesarios para explotar el enorme potencial de la arquitectura de computación masiva CUDA, siendo CUDA C una extensión de ANSI C que la corporación NVIDIA ha creado para compilar programas que contienen código de CUDA y así poder generar ejecutables que permitan acceder a los recursos del dispositivo de GPU [10]. Para compilar programas que utilicen esta tecnología NVIDIA desarrolló un compilador “NVCC” [10], dicho compilador es específicamente un wrapper que se ejecuta junto a un compilador convencional de C++, básicamente realiza el trabajo de un preprocesador que transforma la sintaxis de CUDA en algo que pueda ser comprendido por el compilador. 31 2.6 Comparativa entre el uso de la CPU y la GPU La primera diferencia es la cantidad de unidades de procesamiento aritmético que tiene una GPU moderna, contra una CPU convencional, permitiendo a la GPU alcanzar varios Giga FLOPS, para medir la potencia de un procesador se suele contabilizar el número de operaciones (por ejemplo de coma flotante, o sea, de números decimales) que realiza por segundo [9]. Cuantas más operaciones pueda realizar en un segundo, más potente será y más rápido se ejecutarán las aplicaciones (obviando que pueden haber otros factores que limiten la ejecución de la aplicación como los accesos a memoria u otros), en la Figura 1 se puede apreciar la diferencia entre los Giga FLOPS teóricos entre diferentes dispositivos de GPU y de CPU en simple y doble precisión. Figura 1: CPU vs GPU GFLOP/s Fuente: [10] 32 El ancho de banda de la memoria es otro punto muy importante, los chips gráficos han estado operando con aproximadamente diez veces el ancho de banda que las CPU contemporáneas, permitiendo velocidades de varios Gigabytes por segundo [9], tal como se muestra en la Figura 2, el ancho de banda de la memoria de una tarjeta de video hasta el año 2013 es diez veces que el de una CPU contemporánea. Figura 2: CPU vs GPU GB/s Fuente: [10] El problema está en que sólo un rango limitado de aplicaciones es altamente paralelizable y pueden aprovechar las facilidades que ofrecen los dispositivos de GPU, el resto es muy dependiente de los accesos a memoria y dependen de los datos que se van generando secuencialmente en las distintas instrucciones [9]. Hacer programas que aprovechen la ejecución paralela es bastante complejo, requiere de un buen análisis del problema y de la partición de datos además son 33 más complicados de depurar y mantener. Un programa que se abstrae de la arquitectura subyacente no logra aprovechar el verdadero poder de cómputo, e incluso puede llegar a generar peores tiempos de ejecución que un programa secuencial. Un dispositivo de CPU contemporáneo está diseñado para ser utilizado con múltiples propósitos, mientras que el de GPU (aunque ahora soporta diversas funcionalidades) su uso es muy restringido, es decir, las unidades de procesamiento en el dispositivo de GPU (núcleos) son altamente especializadas, mientras las unidades de procesamiento en la CPU son de uso muy general [10]. El procesamiento que realiza el dispositivo de CPU es autónomo, mientras el procesamiento que se realiza en el dispositivo de GPU se basa en un co- procesamiento [9]. Un proceso que está basado en la CPU tiene cuellos de botella (Acceso a dispositivos, acceso a memoria principal, núcleos de la CPU, etcétera), si el procesamiento está basado en la GPU tendríamos que agregar el acceso a la memoria de la tarjeta de video [11]. Al utilizar un dispositivo de GPU los problemas a optimizar deben de ser del tipo matricial, ya que contamos con cientos de núcleos especializados en realizar operaciones matemáticas a conjuntos de datos con este tipo de organización, pero la CPU está especializada en bucles y operaciones condicionales. 2.7 Arquitectura de CUDA La arquitectura de CUDA se basa en un arreglo escalable de Multiprocesadores (SM) cada uno con múltiples hilos [11] (La paralelización se logra creando hilos, no procesos, debido a que estos presentan menor costo en los cambios de contexto y accesos a memoria). Cada SM es capaz de manejar 768 34 contextos de hilos activos simultáneamente y un multiprocesador consiste de ocho núcleos de procesadores escalares (SP), dos unidades de funciones especiales básicas, una unidad de instrucción con múltiples hilos y una memoria compartida dentro del chip [11]. La arquitectura CUDA permite abrir al programador la tarjeta gráfica y así poderla utilizar como una especie de co-procesador matemático, antes de esta tecnología, si se quería programar algo que no fueran operaciones gráficas utilizando el dispositivo de GPU se debía de utilizar interfaces de programación como OpenGL o DirectX y asumir las restricciones que impone el dispositivo de GPU [9]. Ahora con la tecnología CUDA podemos programar aplicaciones utilizando el dispositivo de GPU utilizando una extensión del lenguaje C. La tarjeta gráfica se presenta como un procesador masivamente paralelo que consta de varios multiprocesadores, cada uno de los cuales está formado a su vez por varios procesadores como se observa en la Figura 3. Estos procesadores son los que se encargan de ejecutar los hilos que vienen agrupados en bloques. Así se estará ejecutando la misma aplicación en todo el multiprocesador pero actuando sobre datos diferentes. La tarjeta GEFORCE 8800 GTX, está diseñada con 16 multiprocesadores, cada uno de los cuales lleva 8 procesadores, por tanto contiene 128 núcleos para procesamiento paralelo. 35 Figura 3: Arquitectura de CUDA Fuente: [9] En [9] se describen los siguientes componentes de la arquitectura de CUDA:  Motores de computación paralela dentro de las GPU de NVIDIA.  Soporte a nivel de “kernel” de Sistema operativo para la inicialización y configuración de Hardware.  Drivers los cuales permiten la manipulación de la tarjeta de video por parte de los desarrolladores.  Un conjunto de instrucciones para los kernel paralelos y diversas funciones. También se cuenta con un ambiente de desarrollo que provee herramientas, ejemplos y la documentación necesaria que tomen ventaja para el desarrollo de software con esta tecnología, En [10] se describen las más resaltantes y entre ellas tenemos a:  Avanzadas Librerías como BLAS, FFT, y otras con funcionalidades para la optimización de la arquitectura de CUDA.  C RUNTIME para CUDA provee soporte para la ejecución de funciones 36 estándar en C en la GPU y permite enlaces nativos para otros lenguajes de alto nivel como FORTRAN, Java o Python.  Herramientas como el compilador de C de NVIDIA (NVCC), el DEBUGGER de CUDA (CUDAGDB), el PROFILER visual (CUDAPROF) y otras herramientas. La base fundamental para la ejecución paralela en CUDA son los hilos, un kernel crea una grilla de hilos y todos ellos se ejecutan en la función del kernel, en esta función se especifican las sentencias que son ejecutadas por cada hilo individual creado cuando el kernel es lanzado en tiempo de ejecución. La organización de hilos es estrictamente un concepto de implementación y así debe de ser discutido en el contexto de implementaciones específicas, en la Figura 4 se aprecia la organización de hilos en la tarjeta de video GEFORCE 8800 GTX, una vez que un bloque es asignado a la cadena de multiprocesadores es dividido en unidades de 32 hilos llamadas WARPS, el tamaño de un WARP es una implementación específica y puede variar de una implementación a otra. De hecho los WARPS aún no son parte de la definición del lenguaje de CUDA, sin embargo el conocimiento de los WARPS puede ser muy beneficioso en la comprensión y optimización del desempeño de aplicaciones en CUDA, los WARPS son más que unidades de organización de hilos. 37 Figura 4: Organización de Hilos Basada en WARPS – Tarjeta de Video GEFORCE 8800GTX. Fuente: [9] Desde que todos los hilos en una grilla ejecutan la misma función Kernel, ellos se relacionan sobre coordenadas únicas para distinguirlos de ellos mismos y para identificar la porción apropiada de datos a procesar. Estos hilos están organizados en dos niveles de jerarquía usando coordenadas únicas llamadas “blockId” y “threadId” asignados a ellos por el sistema de tiempo de ejecución de CUDA, el primero es el identificador del bloque y el segundo es el identificador del hilo, estas coordenadas pueden ser utilizadas en las funciones del kernel y con ellas se puede obtener el hilo necesario. Se puede apreciar en la Figura 5 que en el nivel más alto de la jerarquía es una grilla organizada como un arreglo de bloques. El número de bloques en cada dimensión es especificado como el primer parámetro que se necesita para lanzar al kernel, siendo el segundo parámetro el número de hilos necesarios por bloque. En el nivel más bajo de la jerarquía todos los bloques de la grilla están organizados en arreglos de tres dimensiones, como se aprecia en la Figura 5, todos los bloques en 38 una grilla tienen las mismas dimensiones, cada identificador de hilo consiste en tres componentes, sus coordenadas (x, y, z) en ese arreglo tridimensional. El tamaño total del bloque es limitado a 512 hilos no importando la configuración en tres dimensiones que se asigne. Figura 5: Organización de Hilos en la Arquitectura de CUDA. Fuente: [9] Si se requiere lanzar un kernel, el primer paso sería crear una grilla. Por ejemplo para crear una grilla de una dimensión con cien bloques se especificaría en el lenguaje CUDA C: dim3 dimGrid (100, 1, 1); (1) El segundo paso es definir el número de hilos que tendrá cada bloque, por ejemplo si cada bloque tendría 16x16 hilos se debe definir: dim3 dimBlock (16, 16, 1); (2) El lanzamiento del kernel necesita ambas variables, que definen la estructura de organización de la grilla y el lanzamiento sería así: KernelFunction<<>>(….); (3) 39 2.7.1. Escalabilidad Transparente CUDA permite que los hilos de un mismo bloque puedan coordinar sus actividades usando una función de sincronización llamada “syncthreads” [9], cuando una función kernel llama a syncthreads() todos los hilos en un bloque son retenidos en el lugar de llamada de esta función hasta que todos los demás hilos en el bloque la hayan alcanzado esto asegura que todos los demás hilos del bloque hayan completado la fase de su ejecución antes que ellos sean movidos a una siguiente fase. A esta técnica de sincronización se le denomina sincronización por barrera, la habilidad de sincronizarse con otros impone restricciones sobre los hilos de un bloque, estos hilos deberían ejecutarse en un tiempo muy cercano para evitar tiempos de espera excesivos [11]. En la Figura 6 se puede observar que la ejecución de los bloques no tiene un orden especifico, ya que los sistemas de ejecución de CUDA satisfacen la restricción de escalabilidad transparente asignando recursos de ejecución a todos los hilos de un bloque como una unidad, se crea una compensación en el diseño de la sincronización por barrera pero la coordinación entre bloques no existe, es decir, no se puede realizar una sincronización a un nivel más alto que el de hilos, siendo esta una restricción necesaria para que el diseño del kernel sea transparente. 40 Figura 6: La falta de Sincronización entre Bloques permite Escalabilidad Transparente. Fuente: [9] 2.7.2. Asignación de hilos Una vez que un kernel es lanzado, el sistema de tiempo de ejecución de CUDA genera la correspondiente grilla de hilos, estos hilos son asignados a la ejecución de recursos de bloque en bloque. En la serie de tarjetas de video GeForce-8, la ejecución de recursos está organizada en multiprocesadores encadenados, un ejemplo es la tarjeta de video GEFORCE 8800GTX, diseñado para contener muchos recursos (16 multiprocesadores ), cada uno con la capacidad de contener 8 bloques, dando un total de 128 bloques pero la mayoría de veces este es un número pequeño de recursos en una grilla, el sistema de tiempo de ejecución de CUDA mantiene una lista de todos los bloques que pueden ser ejecutados y asignados a estos multiprocesadores. 2.7.3. Acceso a memoria El procesamiento en la arquitectura de CUDA está basado en el procesamiento de hilos, los datos a ser procesados deben ser pasados primero de la memoria del HOST a la memoria del DEVICE, los hilos acceden a su porción de datos en la memoria del DEVICE utilizando los identificadores de bloques y de hilos, este modelo de trabajo es muy bueno pero no permite a los 41 kernel de CUDA acceder a su verdadero potencial de velocidad, esto es debido a que la memoria global esta típicamente implementada con memoria de acceso aleatorio dinámico (DRAM), tendiendo a tener largas latencias de acceso ( cientos de ciclos de reloj ), y acceso limitado de banda ancha [12]. 2.7.4. Otros tipos de memoria Cada dispositivo CUDA tiene muchas memorias que pueden ser usadas para alcanzar un gran ratio de velocidad de ejecución en el kernel, esto depende del tipo de situación que se necesite.  Memoria Compartida La arquitectura de CUDA provee una región de memoria llamada “Memoria Compartida” [9]. En CUDA C para tener acceso a dicha memoria se utiliza la palabra clave “__shared__” para poder declarar variables residentes en la memoria compartida, el compilador de CUDA C trata a este tipo de variables de una forma diferente creando una copia de variable por cada bloque lanzado en la invocación al Kernel, cada hilo en ese bloque comparte la variable, pero no pueden acceder o modificar la copia de la variable de otros bloques, esto permite crear un excelente canal de comunicación entre los hilos de un mismo bloque además que la memoria compartida reside físicamente dentro de la GPU opuestamente a la memoria global. El prospecto de comunicación entre hilos permite hacer grandes mejoras pero esta comunicación necesita un mecanismo para realizar una sincronización entre los hilos del bloque, por ejemplo si un hilo A escribe un valor en la memoria compartida y queremos que un hilo B realice una 42 operación con este valor, no se debe lanzar el hilo B hasta saber si la escritura hecha por el hilo A ha sido completada, sin una forma de sincronización se crearía una condición de carrera [9] donde la correcta ejecución de resultados depende de detalles no determinísticos del hardware.  Memoria constante Existen formas en las cuales se puede explotar regiones especiales de la memoria de la GPU para acelerar las aplicaciones en CUDA C, una de esas formas es utilizando una región en la GPU llamada “Memoria constante” [9], en CUDA C para declarar una variable dentro de la memoria constante se utiliza la palabra clave “__constant__”, la utilización de esta región que permite mejorar el desempeño en la aplicaciones que utilizan la arquitectura CUDA. Con cientos de unidades aritméticas el cuello de botella del cómputo no es el cálculo de operaciones sino el ancho de banda de la memoria del CHIP. La memoria constante se utiliza para almacenar datos que no serán modificados a lo largo de la ejecución del kernel. El hardware provee 64 Kb de memoria de solo lectura, en algunas situaciones la memoria constante es más usada que la memoria global, en estos casos, la latencia de memoria global es muy reducida y la aceleración se ve incrementada. 43  Memoria de textura Al igual que la memoria constante la memoria de textura es otro tipo de memoria de solo lectura que su uso puede mejorar el desempeño y reducir el tráfico de memoria cuando las lecturas tienen ciertos patrones de acceso, sin embargo la memoria de textura fue originalmente diseñada para aplicaciones gráficas tradicionales, esto también puede ser utilizado efectivamente en aplicaciones de computo con la GPU [9]. En efecto los dispositivos de GPU sofisticados brindan una memoria de textura que puede ser utilizada para cómputo de propósito general, aunque NVIDIA diseñó las unidades de textura para los pipelines de renderización de OPENGL y DIRECTX. Como la memoria constante la memoria de textura puede ser utilizada para reducir el tráfico de requerimientos de memoria en la memoria global. Específicamente los caches de textura son diseñados para aplicaciones gráficas donde existan patrones de acceso a memoria que exhiben un gran acceso a localidades espaciales, en una aplicación de cómputo de propósito general esto implica que un hilo lea desde una dirección de memoria cercana a la dirección leída por un hilo continuo. 44 2.7.5. Acceso a memoria en CUDA En la Figura 7 podemos observar encima de los hilos en ejecución a los registros y sus memorias compartidas, las variables que residen en estas memorias pueden ser accedidas de una forma muy rápida y paralela. Los registros son separados para hilos individuales ya que cada hilo solo puede acceder a sus propios registros. Una función kernel típicamente usa registros para guardar accesos a variables frecuentes que son privadas para cada hilo. Las memorias compartidas son separadas para bloques de hilos; todos los hilos de un bloque pueden acceder a variables almacenadas en locaciones de la memoria compartida, siendo las memorias compartidas una manera eficiente para que los hilos cooperen y compartan los resultados de su procesamiento. Figura 7: Implementación de memorias en CUDA - GEFORCE 8800GTX, Imagen. Fuente: [9] Cada hilo puede:  Leer y escribir sus propios registros.  Leer y escribir su propia memoria local.  Leer y escribir la memoria compartida del bloque al cual pertenece. 45  Leer y escribir la memoria global por grilla.  Leer la memoria constante El alcance identifica el rango en el que todos los hilos pueden acceder a la variable, de acuerdo a [9] estos rangos son:  Por un solo hilo, si este es el caso, una versión privada de la variable será creada por cada hilo, por ejemplo si el kernel declara una de sus variables con este alcance y son lanzados un millón de hilos entonces un millón de versiones privadas de la variable serán creadas.  Por todos los hilos del bloque, una variable puede ser accedida por todos los hilos del bloque si es declarada como una variable compartida, las variables deben de residir en una función kernel, el tiempo de vida de estas variables va arraigado al tiempo de ejecución del kernel, es decir, si el kernel termina la instancia de la variable termina, estas variables compartidas son una forma eficiente para que los hilos de un mismo bloque colaboren en conjunto.  Por todos los hilos de la grilla entera. Una variable puede ser accedida por todos los hilos de una grilla si es declarada como constante, la declaración de esta variable debe de estar fuera del cuerpo de la función kernel, el alcance de las variables constantes es toda la grilla de ejecución, el tiempo de vida de una variable constante es la ejecución de toda la aplicación, para mejorar la eficiencia de acceso a estas variables estas son almacenadas en la memoria global pero son insertadas en una memoria caché para un eficiente acceso, creando una restricción de 65,536 bytes de variables constantes. 46 El alcance global definido en [11] especifica que si una variable se ha declarado de forma global esta es almacenada en la memoria global, y su acceso es muy lento, sin embargo estas variables son visibles por todos los hilos de todos los kernel en la aplicación, de esta forma estas variables pueden ser utilizadas para compartir información entre hilos de diferentes bloques, o para compartir información entre diferentes kernel. El tiempo de vida especifica la porción de duración en el cual la variable está disponible para uso en una invocación de kernel o a través de una aplicación entera según [11] las consideraciones que se deben de tener son:  Si el tiempo de vida de la variable es para una invocación de kernel, esta debe ser declarada dentro del cuerpo de la declaración del kernel y será disponible solo para el uso del código del kernel, si el kernel es invocado varias veces el contenido de la variable no es mantenido a través de esas invocaciones, en este caso cada invocación debe inicializar la variable para usarla.  En el caso que el tiempo de vida es en toda la aplicación, esta variable debe ser declarada fuera del cuerpo de la función. Los contenidos de la variable son mantenidos a través de la ejecución de la aplicación y disponible para todos los kernel. 47 Tabla 1: Velocidad de memoria Global vs Local. Memory Speed Read/Write Block Size (GB/sec) Local 32 190/181 Local 64 288/328 Local 128 299/388 Local 256 289/385 Local 512 277/368 Global 32 7.4/3.7 Global 64 5.8/3.5 Global 128 4.8/3.4 Global 256 4.3/3.4 Global 512 4.1/3.3 Fuente: [22] Todas las variables automáticas exceptuando arreglos son guardadas dentro de los registros y se debe referir a las variables que no son arreglos como variables escalares, los alcances de estas variables automáticas están dentro de hilos individuales. Cuando una función kernel declara una variable automática, una copia privada de esa variable es generada para todos los hilos que ejecutan la función kernel, cuando un hilo termina todas sus variables automáticas dejan de existir [12]. Las variables de arreglo automáticas no son guardadas en registros más bien son guardadas en la memoria global e incurren en accesos lentos y potencialmente congestiones de acceso. Los alcances de estos arreglos son como en las variables escalares en los hilos individuales. Es decir una versión privada del arreglo es creada por cada hilo, y una vez que el hilo 48 termina su ejecución el contenido del arreglo deja de existir. Debido a la naturaleza lenta del uso de variables de arreglo, se debería evitar su uso. Hay que notar que existe una limitación en el uso de punteros en CUDA, ya que estos punteros solo pueden ser utilizados para apuntar a datos en la memoria global, existen dos típicos usos de estos punteros, por ejemplo si un objeto es almacenado por una función HOST utilizando la función cudaMalloc() se puede pasar a la función kernel como un parámetro., el segundo uso es la asignación de direcciones de una variable declarada en la memoria global. Tenemos una compensación intrínseca en el uso de las memorias: la memoria global es larga, pero es lenta, la memoria compartida es pequeña pero es rápida. Una estrategia común es la partición de los datos en subconjuntos llamados tiles, para que cada tile encaje en la memoria compartida [12]. El concepto de “tiling” puede ser ilustrado con el ejemplo de multiplicación de matrices, en este ejemplo se asume que se está utilizando 4 bloques de 2x2 para calcular la matriz resultante [9]. En la Figura 8 podemos ver los accesos a memoria global hechos por todos los hilos en el bloque (0,0) se puede notar que cada hilo accede a cuatro elementos de Md y a cuatro elementos de Nd durante su ejecución, existen accesos similares a Md y a Nd por ejemplo el hilo (0,0) y el hilo (1,0) utilizan la fila 0 de la matriz Md, si se hace colaborar a estos dos hilos para que esta fila sea accedida desde la memoria global podemos reducir a la mitad el número de accesos a memoria global, el potencial de reducción del tráfico 49 de memoria en la multiplicación es proporcional a la dimensión del tamaño de bloque en uso, con NxN bloques, el potencial de reducción del tráfico de memoria global debería ser N. Figura 8: Multiplicación de matrices con varios bloques. Fuente: [9] En la Figura 9 se aprecia el Tiling dividiendo las matrices en tiles de 2x2, los cálculos del producto punto es desempeñado por cada hilo y estos cálculos son ahora divididos en fases. En cada fase todos los hilos de un bloque colaboran para cargar un tile Md y un tile de Nd en la memoria compartida, estos es hecho haciendo que cada hilo en un bloque cargue un elemento de Md y Nd a la vez. Figura 9: Tiling en la multiplicación de matrices con CUDA. Fuente: [9] 50 Después de que dos tiles de Md y Nd son cargados dentro de la memoria compartida, estos valores son usados en el cálculo del producto punto. En la Figura 10 se nota que cada valor en la memoria compartida es usada dos veces, por ejemplo el valor de Md(1,1) es cargado por el Hilo(1,1) en Mds(1,1) . Figura 10: Fases de ejecución del algoritmo de multiplicación en tiles. Fuente: [9] Según [13] Un programa en GPU tiene una característica que puede ser considerada su mayor obstáculo: “Las memorias de la GPU y del HOST están típicamente disjuntas, requiriendo ambas la transferencia de los datos entre las dos”.  Aplicación en problemas reales Las GPU han evolucionado al punto que muchas aplicaciones del mundo real se están implementando fácilmente en ellas y se ejecutan muchísimo más rápido que en sistemas con múltiples núcleos. Las arquitecturas de computación del futuro serán sistemas híbridos con GPU de núcleos paralelos trabajando en tándem con CPU de múltiples núcleos. 51  Identificar la placa oculta en las arterias: Los infartos son la principal causa de muerte en todo el mundo. Harvard Engineering, Harvard Medical School y Brigham & Women's Hospital se han unido para usar las GPU para simular el flujo sanguíneo e identificar la placa arterial oculta sin las técnicas invasivas de diagnóstico por imágenes o la cirugía exploratoria [14].  Analizar el flujo del tráfico aéreo: El National Airspace System administra la coordinación del flujo del tráfico aéreo en todo el país. Los modelos de computación ayudan a identificar nuevas formar de mejorar la congestión y mantener el movimiento del tráfico aéreo eficiente. Usando la potencia computacional de las GPU, un equipo de la NASA obtuvo un enorme aumento en el rendimiento y redujo el tiempo del análisis de diez minutos a tres segundos [14].  Visualizar moléculas: Una simulación molecular llamada NAMD (dinámica molecular a nanoescala) obtiene un gran aumento en el rendimiento con las GPU. La aceleración es resultado de la arquitectura paralela de las GPU, que les permite a los desarrolladores de NAMD llevar a la GPU partes de la aplicación con uso intensivo de la computación usando el kit de herramientas CUDA [14]. 52 CAPITULO III: MARCO METODOLÓGICO 3.1. Selección del Algoritmo Existen muchos algoritmos para el cifrado y descifrado de información entre ellos los más utilizados según [1] son el RSA, el AES, el triple DES y el DES, estos algoritmos están basados en claves asimétricas y claves simétricas. Se sabe además que no todos los algoritmos de cifrado son paralelizables en GPU es por eso que la presente tesis toma al algoritmo RSA como base para su estudio por ser el más utilizado en procesos de encriptación de clave asimétrica, al ser este un algoritmo altamente paralelizable por pertenecer al patrón paralelo de algoritmos de Elementwise, es decir, algoritmos donde el procesamiento de un elemento no depende del resultado de otro [1]. 3.2 La implementación del algoritmo La cual se realizó en 3 formas que se detallan a continuación: 3.2.1. Implementación del algoritmo RSA mono-núcleo. En la presente tesis se utilizó el algoritmo definido en el estándar de criptografía de clave pública (PKCS) publicado por RSA Laboratories en el año 2000. En este capítulo se enuncia el diseño e implementación del algoritmo RSA en CPU, la seguridad de este algoritmo está basada en la dificultad de factorizar un número muy grande producto de dos números primos grandes. En el 2004, el número más grande factorizado por métodos de propósito general fue de 174 dígitos decimales de largo (en binario fue de 576 bits). Típicamente, las claves RSA tienen 1024-2048 bits de longitud. Algunos expertos creen que 53 una clave de 1024 bits puede ser quebrada en el corto plazo pero nadie cree que la clave de 2048 bits pueda serlo en un futuro previsible. Aquí se muestra la organización interna bajo la cual se ha construido el programa que muestra la implementación en CPU, los algoritmos aplicados y otras consideraciones que se han debido tomar en cuenta para el desarrollo. Muchos casos son ilustrados con ejemplos y corridas de escritorio y para un mejor entendimiento también se adjuntan datos para prueba. La implementación se ha desarrollado en lenguaje C++ aplicando conceptos de programación orientada a objetos. a. Requerimientos de implementación: Para la implementación se han tenido en cuenta los siguientes requerimientos mínimos:  Permitir el manejo de números enteros de por lo menos 128 dígitos para incrementar la seguridad de la claves de encriptación.  Implementar consideraciones de seguridad mínimas en lo referente a características de los números primos y otros valores que intervienen en el cálculo de las claves.  Considerar los algoritmos más eficientes disponibles en la teoría matemática con el fin de que el uso de la herramienta computacional sea óptima.  Interface es por línea de comandos que realizará un procesamiento por lotes. 54 b. Algoritmos RSA – Mono núcleo El algoritmo RSA tiene tres etapas, la primera es la generación de las claves públicas y privadas, la segunda el proceso de encriptación y la tercera el proceso de des encriptación. Algoritmo RSA – Generación de claves, extraído de [16] 1. Elegir p y q 2. Calcular n = p * q 3. Calcular Fi(n) = (p - 1) * (q - 1) 4. Elegir e tal que 1 < e < Fi(n) y e, n son números coprimos 5. Calcular un valor para d tal que (d * e) % Fi(n) = 1. 6. La clave pública es (e, n) 7. La clave privada es (d, n) Algoritmo RSA – Encriptación, extraído de [16] 1. Para cada carácter m del mensaje de entrada 2. Calcular el valor del carácter encriptado c => c = me % n Algoritmo RSA – Des encriptación, extraído de [16] 1. Para cada carácter encriptado c del mensaje 2. Calcular el valor del carácter m del mensaje original => m = cd % n c. Proceso de encriptación – Ejemplo. En la implementación de la encriptación y des encriptación propuesta en el algoritmo RSA existe un inconveniente, al tratarse de potencias de números 55 muy grandes, ya que los números p y q deben de ser números enteros coprimos grandes y de estos dependen la generación de las variables d y e, el resultado puede ser muy grande, me indica la potencia del valor del mensaje al exponente “e”, que forma parte de la clave pública, si tomamos un ejemplo discreto en el cual se quiere cifrar el mensaje: “Mensaje a ser cifrado”, utilizando los parámetros de entrada al algoritmo con “p” = 31, “q” = 23, se obtienen “e” = 7 y “d” = 283: - Clave pública (7,713) - Clave privada (283,713) En la Tabla 2 se representa el mensaje con la siguiente configuración: En la primera fila se representan los índices de cada carácter en el arreglo, en la siguiente fila los caracteres del mensaje en formato UTF-8 y en la última fila el valor ASCII de cada carácter. Tabla 2: Mensaje a ser cifrado, cada carácter representado por su código ASCII. Fuente: Elaboración propia En este ejemplo para poder realizar una encriptación del mensaje se eleva a una potencia de 7 (valor obtenido de la clave pública) cada uno de los valores ASCII del mensaje y luego se procede a aplicar el módulo del mismo utilizando el valor de 713, obteniendo el siguiente resultado presentado en la Tabla 3. 56 Tabla 3: Mensaje cifrado utilizando el algoritmo RSA con clave pública (7,713) Fuente: Elaboración propia En la última fila resaltada de amarillo podemos apreciar el mensaje cifrado utilizando el algoritmo RSA. Para poder realizar el proceso de des encriptación del mensaje debemos utilizar la clave privada la cual es (283,713). Es aquí que surge un problema por el tamaño de los datos de entrada, por ejemplo elevar el número 426 (posición 0 en el mensaje cifrado) a la potencia 283 (clave privada) desbordaría el almacenamiento más grande en cualquier computadora con arquitectura menor a 64 bits, para esto es que se hace uso del principio de multiplicación modular. d. Principio de multiplicación modular El principio de multiplicación modular permite realizar el cálculo de la potencia de dos números y el módulo de su resultado con un tercer número. ab % c Este principio se aplica cuando el resultado de la potencia de los números ab es muy grande y desborda su almacenamiento en un sistema de 64 bits o menor. Según el principio de la multiplicación modular: an+m % c = ((an % c) * (am % c)) % c Si se utiliza el principio de la multiplicación modular para los procesos de encriptación y des encriptación no se tendrán problemas en las potencias de 57 números grandes ya que nunca se almacenan temporalmente éstos al aplicar en cada multiplicación el modulo del segundo parámetro, ver Figura 11. Figura 11: Procesamiento del mensaje de entrada en un solo núcleo, el cálculo de la encriptación de cada carácter es secuencial y realizado por un solo procesador. Fuente: Elaboración Propia. 3.2.2. Implementación del algoritmo RSA basada en CPU, múltiples núcleos. Para la propuesta basada en múltiples núcleos de CPU se ha utilizado la librería propuesta por INTEL Threading Building Blocks aplicada en [23]. Intel® Threading Building Blocks (Intel® TBB) es una biblioteca que soporta programación paralela escalable utilizando código estándar ISO C ++. No requiere de compiladores especiales. Está diseñada para promover los datos escalables de la programación paralela. Además, es totalmente compatible con el paralelismo anidado, para que pueda construir componentes paralelos más grandes de componentes paralelos más pequeños. Muchas de las interfaces de bibliotecas emplean programación genérica, en la que las interfaces se definen por los requisitos sobre los tipos y tipos no específicos. El Standard Template Library C++ (STL) es un ejemplo de programación genérica. Programación genérica permite Intel® TBB para ser flexible y 58 eficiente. Las interfaces genéricas que permiten personalizar los componentes a sus necesidades específicas. En el algoritmo de RSA existen dos momentos que pueden ser altamente paralelizables según [23], estos son: - Para encriptar el mensaje m se tiene => c = me % n - Para desencriptar el mensaje c se tiene => m = cd % n Se utiliza un for paralelo para procesar los mensajes, es así que la cadena a encriptar es dividida para poder ser procesada por todos los núcleos presentes en la máquina, ver Figura 12. Figura 12: Procesamiento del mensaje de entrada en una Core I7 (ocho núcleos) el cálculo de la encriptación de cada carácter es paralelo y realizado por los ocho procesadores. Fuente: Elaboración propia. 59 3.2.3. Implementación del algoritmo RSA basada en GPU. En la presente tesis se desarrolla una nueva implementación en tarjetas gráficas programables (GPUs) del algoritmo RSA, evaluando las prestaciones de dicha implementación en la tarea de encriptar y desencriptar archivos de texto (Para las pruebas se utiliza la base de datos del proyecto Gutenberg, que es una biblioteca de Libros electrónicos gratuitos). Con vistas a validar el algoritmo implementado en GPU, se ha evaluado el consenso obtenido en la clasificación con respecto a los resultados proporcionados por la implementación del algoritmo RSA en su versión en CPU. Dicha validación experimental revela que el algoritmo propuesto permite obtener resultados superiores, en particular, la implementación paralela del algoritmo propuesto (Desarrollada utilizando el lenguaje CUDA de la empresa NVidia) obtiene un speedup por encima de 10 unidades con respecto a la correspondiente versión en CPU, lo cual supone un importante aumento de las prestaciones computacionales del algoritmo que se preveen indispensables a la hora de procesar grandes cantidades de datos, tales como los disponibles en la base de datos de Wikipedia que se ha utilizado en el presente trabajo para validar el algoritmo paralelo desarrollado. a. Requerimientos de implementación Para implementación se han tenido en cuenta los siguientes requerimientos mínimos:  Contar con una tarjeta gráfica de NVIDIA que soporte CUDA.  Permitir el manejo de números enteros de por lo menos 128 dígitos para incrementar la seguridad de la claves de encriptación. 60  Implementar consideraciones de seguridad mínimas en lo referente a características de los números primos y otros valores que intervienen en el cálculo de las claves.  Considerar los algoritmos más eficientes disponibles en la teoría matemática con el fin de que el uso de la herramienta computacional sea óptima.  Interface es por línea de comandos que realizará un procesamiento por lotes.  Es deseable un adecuado tiempo de respuesta aunque los algoritmos son lentos debido a la gran cantidad de cálculos involucrados Algoritmo RSA en GPU: Encriptar, elaboración propia 1. Para encriptar el mensaje m se calcula el número de hilos necesarios para procesar el mensaje m de tamaño S. 2. Utilizamos un arreglo de hilos de GPU lineal de tamaño L 3. Realizamos el procesamiento de S/L caracteres del mensaje con cada hilo separado. Para encriptar el mensaje m se tiene => c = me % n Algoritmo RSA en GPU: Des encriptar, elaboración propia. 1. Para des encriptar el mensaje m se calcula el número de hilos necesarios para procesar el mensaje encriptado m de tamaño S. 2. Utilizamos un arreglo de hilos de GPU lineal de tamaño L 3. Realizamos el procesamiento de S/L caracteres del mensaje con cada hilo separado. Para des encriptar el mensaje c se tiene => m = cd % n 61 En la Figura 13 se muestra el procesamiento del proceso de encriptación del mensaje utilizando el arreglo de procesadores disponible en la GPU. Figura 13: Procesamiento del mensaje de entrada en una GPU NVIDIA (20 núcleos), el cálculo de la encriptación de cada carácter es paralelo y realizado por los veinte procesadores. Fuente: Elaboración propia. 3.3. Pruebas para la implementación del algoritmo Se hará uso de la base de datos de texto plano del proyecto Gutenberg, disponible en [15], éste ofrece copias libres de todo el contenido disponible para usuarios interesados, esta bases de datos puede ser descargadas desde cualquier fuente externa, para uso personal, copias de seguridad informales, usuarios desconectados o bases de datos de consulta. El Proyecto Gutenberg ofrece más de 46.000 libros electrónicos gratuitos, todo el contenido de texto es libre. Todos los libros electrónicos son de alta calidad, éstos fueron publicados previamente por editores digitalizando y dando diligencia a la ayuda de miles de voluntarios. 3.2.1. Criterios de inclusión. Para la realización de pruebas se hará uso de un muestreo estadístico, específicamente, un muestreo sistemático para la selección de las muestras. 62 Todas las muestras fueron obtenidas de la base de datos del proyecto Gutenberg descrita en [15], el universo lo conforman 46000 libros en formato UTF-8, se realizó una selección de 1000 muestras de entre todo el universo. 3.2.2. Criterios de exclusión.  No se tomaron en cuenta las muestras en otros formatos que no sean UTF-8.  No se tomaron en cuenta archivos de tamaño menor a 20 Kilobytes. 63 CAPITULO IV: RESULTADO A continuación se evalúan las implementaciones del algoritmo RSA bajo los tres enfoques empleados para la resolución del problema de encriptación de archivos de texto plano visto en los capítulos anteriores. Estas pruebas se han llevado a cabo en cuatro equipos con características diferentes, se ha comparado los tiempos de ejecución de las implementaciones secuenciales, multi CPU (utilizando la librería de paralelización TBB) y la implementación bajo la tecnología CUDA de NVIDIA. 4.1. Evaluación de la implementación en un solo núcleo de CPU. Para evaluar el algoritmo que resuelve el problema de encriptación de archivos planos de texto se ha comparado el tiempo de ejecución del algoritmo RSA, con variables p y q (entrada del algoritmo) de 32 bits de ancho y variando el tamaño de cada archivo de entrada, contra la función ya implementada en CPU utilizando el lenguaje de programación c++. Se Utilizó la base de datos de libros de Gutenberg descrita en [15]. 4.2. Evaluación de la implementación en varios núcleos de CPU utilizando la librería TBB de INTEL. Para evaluar la implementación del algoritmo RSA con múltiples núcleos se ha comparado el tiempo de ejecución del algoritmo, con variables p y q (entrada del algoritmo) de 32 bits de ancho y variando el tamaño de archivo de entrada, utilizando todos los núcleos disponibles en la máquina de pruebas, se utilizó el lenguaje de programación C++, la librería de INTEL TBB y la base de datos de libros de Gutenberg descrita en [15]. 64 4.3. Evaluación de la implementación con GPU, utilizando la tecnología CUDA de NVIDIA. Se ha realizado una versión del algoritmo basándose en GPU, variables p y q (entrada del algoritmo) de 32 bits de ancho y variando el tamaño de archivo de entrada, se utilizaron toda la capacidad computacional de la tarjeta de video presente en la máquina de pruebas, la versión en GPU está basada en las versiones propuestas en [17] y [18]. Las pruebas a la implementación del algoritmo se realizaron sobre cuatro equipos con las siguientes características: Tabla 4: Maquinas utilizadas para la realización de pruebas. Memoria Memoria Computadora CPU GPU RAM GPU Intel Core I7 Q740 - 1.73Ghz Geforce GT 330M #1 6.00 GB 1 GB 8 núcleos 48 núcleos Intel Core I5 2410M - 2.3Ghz Geforce GT 540M #2 6.00 GB 1 GB 4 núcleos 96 núcleos Intel Core I5 5287U - 2.3Ghz Geforce GT 480M #3 4.00 GB 1 GB 4 núcleos 48 núcleos Intel Core I5-5300U - 2.3Ghz Geforce GT 310M #4 4.00 GB 1 GB 4 núcleos 16 núcleos Fuente: Elaboración propia 65 4.4. Ejecución del algoritmo RSA en un solo núcleo.. La ejecución del algoritmo RSA implementado sobre un solo núcleo muestra un patrón de comportamiento común para los procesos de encriptación y desencriptación, el tiempo consumido por ambos procesos crece exponencialmente cuando el tamaño del archivo crece en número de bytes. A continuación se muestran los resultados de ejecución de la implementación en las cuatro máquinas de prueba. En la Figura 14 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #1, ver Tabla 4. Figura 14: Ejecución en CPU simple, Maquina 1: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. 66 En la Figura 15 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #2, ver Tabla 4. Figura 15: Ejecución en CPU simple, Maquina 2: a la izquierda proceso de encriptación a la derecha proceso de desencriptación Fuente: Elaboración propia. En la Figura 16 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #3, ver Tabla 4. Figura 16: Ejecución en CPU simple, Maquina 3: a la izquierda proceso de encriptación a la derecha proceso de desencriptación Fuente: Elaboración propia. 67 En la Figura 17 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #4, ver Tabla 4. Figura 17: Ejecución en CPU simple, Maquina 4: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. 4.5. Ejecución del algoritmo RSA en GPU (CUDA). La ejecución del algoritmo RSA implementado sobre GPU utilizando la tecnología CUDA muestra el mismo patrón de comportamiento común para los procesos de encriptación y desencriptación que mostraba la implementación sobre una sola CPU, el tiempo consumido por ambos procesos crece exponencialmente cuando el tamaño del archivo crece en número de bytes, además se observa una reducción significativa del tiempo consumido para ambos procesos, a continuación se muestran los resultados de ejecución de la implementación en las cuatro máquinas de prueba. 68 En la Figura 18 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #1, ver Tabla 4. Figura 18: Ejecución en GPU con CUDA, Maquina 1: a la izquierda proceso de encriptación a la derecha proceso de desencriptación Fuente: Elaboración propia. En la Figura 19 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #2, ver Tabla 4. Figura 19: Ejecución en GPU con CUDA, Maquina 2: a la izquierda proceso de encriptación a la derecha proceso de desencriptación Fuente: Elaboración propia. 69 En la Figura 20 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #3, ver Tabla 4. Figura 20: Ejecución en GPU con CUDA, Maquina 3: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. En la Figura 21 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #4, ver Tabla 4. Figura 21: Ejecución en GPU con CUDA, Maquina 4: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. 70 4.6. Ejecución del algoritmo en múltiples núcleos utilizando la librería de INTEL TBB. La ejecución del algoritmo RSA implementado sobre CPU multi núcleo utilizando la tecnología CUDA muestra el mismo patrón de comportamiento común para los procesos de encriptación y desencriptación que muestran las implementaciones sobre una sola CPU y sobre CUDA, el tiempo consumido por ambos procesos crece exponencialmente cuando el tamaño del archivo crece en número de bytes, además se observa una reducción significativa del tiempo consumido para ambos procesos, a continuación se muestran los resultados de ejecución de la implementación en las cuatro máquinas de prueba. En la Figura 22 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #1, ver Tabla 4. Figura 22: Ejecución en CPU con múltiples núcleos, Maquina 1: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. 71 En la Figura 23 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #2, ver Tabla 4. Figura 23: Ejecución en CPU con múltiples núcleos, Maquina 2: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. En la Figura 24 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #3, ver Tabla 4. Figura 24: Ejecución en CPU con múltiples núcleos, Maquina 3: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. 72 En la Figura 25 se muestra el tiempo de ejecución en segundos vs el tamaño en bytes de los archivos de texto empleados, para los procesos de encriptación y desencriptación ejecutados en la maquina #4, ver Tabla 4 Figura 25: Ejecución en CPU con múltiples núcleos, Maquina 4: a la izquierda proceso de encriptación a la derecha proceso de desencriptación. Fuente: Elaboración propia. Si comparamos los tiempos mínimos y máximos de los procesos de encriptación y des encriptación vemos que en la ejecución por CPU simple los tiempos son muy cercanos en las cuatro máquinas, esto debido a que se está utilizando un solo núcleo en cada máquina, ver Tablas 5 y 6. En los tiempos por GPU, la Maquina 2 presenta los mejores tiempos, esto debido a que se está utilizando 96 núcleos, la Maquina 4 por el contrario presenta los tiempos más grandes por solo contar con 16 núcleos, ver Tablas 5 y 6. En los tiempos por Múltiple-CPU (TBB), la Maquina 1, ofrece los mejores resultados al disponer de ocho núcleos, sin embargo las otras máquinas presentan tiempos parecidos al tener cuatro núcleos en CPU, ver Tablas 5,6. 73 Tabla 5: Tiempos mínimos y máximos del proceso de encriptación. Encriptación Simple-CPU GPU Múltiple-CPU Min Max Min Max Min Max Maquina 1 0.012000 5.396000 0.001165 0.564300 0.005000 1.483000 Maquina 2 0.014420 5.396500 0.000621 0.300900 0.007000 1.919400 Maquina 3 0.014434 5.492900 0.001272 0.616200 0.007007 1.921300 Maquina 4 0.014564 5.492920 0.003179 1.716600 0.007042 1.918200 Fuente: Elaboración propia Tabla 6: Tiempos mínimos y máximos del proceso de desencriptación. Desencriptación Simple-CPU GPU Múltiple-CPU Min Max Min Max Min Max Maquina 1 0.003000 1.574000 0.000487 0.262600 0.003000 1.335900 Maquina 2 0.010330 1.576800 0.000328 0.176500 0.004200 0.582400 Maquina 3 0.010340 1.578400 0.000532 0.286800 0.004204 0.583000 Maquina 4 0.011210 1.578420 0.001551 1.331400 0.005190 0.582000 Fuente: Elaboración propia 74 CONCLUSIONES 1. Se aprecia una diferencia significativa entre los tiempos consumidos por los procesos de encriptación y des encriptación, esto es debido a que el proceso de encriptación tiene que convertir cada carácter de la cadena a ser encriptada al arreglo de enteros para poderse aplicar la potencia modular. 2. Se puede implementar el algoritmo RSA en la tecnología de CUDA, ya que la estructura del algoritmo presenta etapas en las cuales es altamente paralelizable por ser composiciones de tareas sobre bloques independientes de información entre otros aspectos. 3. La implementación del algoritmo con la tecnología de INTEL TBB fue superior a la versión del algoritmo implementada en un solo núcleo. 4. La implementación del algoritmo en la estructura GPU usando la API 7.0 de CUDA, aumentó el rendimiento del algoritmo de exponenciación modular en comparación con la versión basada en la tecnología de INTEL TBB. 5. Las variables independientes fueron modificadas en distintos escenarios, se utilizó mil archivos de texto de la base de datos del proyecto GUTENBERG con diferentes tamaños en bytes, y se utilizó cuatro máquinas con características diferentes en GPU y CPU. Demostrando que el tiempo de procesamiento para los procesos de encriptación y desencriptación dependen significativamente del tamaño en bytes de los archivos de entrada y el número de procesadores utilizados en las ejecuciones. 6. En todas las ejecuciones el proceso de encriptación crece exponencialmente según el tamaño en bytes de los archivos. 75 7. En todas las ejecuciones el proceso de desencriptación crece exponencialmente según el tamaño en bytes de los archivos. 76 RECOMENDACIONES Y TRABAJOS FUTUROS 1. En futuras investigaciones se debe realizar implementaciones de CUDA para el algoritmos RSA que utilice llaves de gran tamaño esto aumentará drásticamente el nivel de seguridad del algoritmo. 2. La tesis se ha limitado a hacer una comparativa experimental de la ejecución del algoritmo RSA con tres implementaciones distintas, se demuestra que se mejora significativamente la implementación del algoritmo RSA utilizando la implementación de CUDA, se propone la utilización de esta técnica en un sistema informático real. 3. Se propone la implementación del algoritmo RSA bajo un esquema de múltiples GPU. 77 BIBLIOGRAFÍA [1] Adrian Pousa 2011, “ALGORITMO DE CIFRADO SIMÉTRICO AES ACELERACIÓN DE TIEMPO CÓMPUTO SOBRE ARQUITECTURAS MULTICORE”, Universidad Nacional de la Plata. [2] Hao Wu 2010, “Implementation of public key algorithms in CUDA”. Department of Computer Science and Media Technology Gjøvik University College. [3] Pedro Miguel Costa Saraiva 2013, "OpenSSL acceleration using Graphics Processing Units", Tecnico Lisboa. [4] Maksim Bobrov 2010,"Cryptographic Algorithm Acceleration Using CUDA Enabled GPUs in Typical System Configurations" Rochester Institute of Technology Rochester, New York. [5] Carla Ramiro Sánchez 2010, "Algoritmos Paralelos para la resolución de problemas de mínimos cuadrados basados en transformaciones ortogonales sobre GPUs y multiprocesadores" Universidad Politecnica de Valencia. [6] Anton Obukhov (2011). “NVIDIA Parallel Nsight”. GPU TECHNOLOGY 2011. [7] A. S. Tanenbaum (1993). “Sistemas Operativos Modernos”. Prentice Hall Hispanoamericana S.A. México, 1993. [8] H. M. Deitel (1987). “Introducción a los Sistemas Operativos”. Addison-Wesley Iberoamericana, México, 1987. [9] Sanders, J. and Kandrot, E. (2010). “CUDA by example: an introduction to general-purpose GPU programming”. Addison-Wesley Professional. [10] NVIDIA® (2011), “NVIDIA CUDA C Programming Guide Version 4.1”. NVIDIA Corporation. [11] Kirk, D. and Wen-mei, W.H. and Hwu, W. (2010). “Programming massively parallel processors: a hands-on approach”. Morgan Kaufmann publisher. [12] NVIDIA Corporation and Rob Farber (2011). “CUDA Application Design and Development”. Published by Elsevier Inc. [13] Shane Cook (2013). “CUDA Programming a Developer’s Guide to Parallel Computing with GPUs”. Morgan Kaufmann is an imprint of Elsevier 225 Wyman Street, Waltham, MA 02451, USA [14] https://developer.nvidia.com/cuda-zone (2015). NVIDIA Cuda Zone, NVIDIA Corporation. 78 [15] http://www.gutenberg.org/ebooks/search/?sort_order=release_date (2015), “Gutemberg Project”, Gutemberg Organization. [16] Yu-Shiang Lin et al (2010) “Efficient Parallel RSA Decryption Algorithm for Many- core GPUs with CUDA”, Department of Computer Science and Information Engineering Chang Gung University Taoyuan 333, Taiwan, ROC [17] Hong Zhang et al (2012), “Comparison and Analysis of GPGPU and Parallel Computing on Multi-Core CPU”, International Journal of Information and Education Technology, Vol. 2, No. 2, April 2012. [18] Qinjian Li et al (2012), “Implementation and Analysis of AES Encryption on GPU”, Center for High Performance Computing Northwestern Polytechnical University Xi’an, CHINA. [19] Luc Bouganim et al (2009), “Database Encryption”, INRIA Rocquencourt Le Chesnay, FRANCE. [20] Sonam Mahajan (2014), “EFFICIENT ALGORITHM FOR RSA TEXT ENCRYPTION USING CUDA-C”, Dhinaharan Nagamalai et al. (Eds) : ACITY, WiMoN, CSIA, AIAA, DPPR, NECO, InWeS – 2014. [21] Jonathan Steven Prieto C. et al (2011), “Optimización e Implementación en Paralelo del Algoritmo RSA en CUDA”, Universidad Sergio Arboleda Bogotá, Colombia. [22] Vaibhav Tuteja (2014), “Image Encryption Using Parallel RSA Algorithm on CUDA”, International Journal of Computer Networks and Communications Security VOL. 2, NO. 7, JULY 2014, 232–235. [23] Heba Mohammed Fadhil et al (2014), “Parallelizing RSA Algorithm on Multicore CPU and GPU”, International Journal of Computer Applications (0975 – 8887) Volume 87. [24] TOMOIAGĂ RADU DANIEL et al (2014), “AES ON GPU USING CUDA”, Faculty of Automatics and Computer Science “Politehnica” University of Timisoara. [25] Tomoiagă Radu Daniel, Stratulat Mircea (2011), “AES Algorithm Adapted on GPU Using CUDA for Small Data and Large Data Volume Encryption” 79 ANEXO A: Base de datos utilizada La base de datos de texto utilizado en las pruebas, es un subconjunto de mil archivos de libros en formato txt obtenido del sitio web del proyecto Gutenberg que son libros electrónicos gratuitos, este proyecto ofrece más de 49000 libros en distintos idiomas en formatos txt. Pdf y html; a continuación se muestran los libros con su respectivo tamaño en bytes: Tamaño # Archivo bytes 1 The Story of Miss Moppet by Beatrix Potter.txt 21707 2 Hey Diddle Diddle and Baby Bunting by Randolph Caldecott.txt 22674 3 Cecily Parsley's Nursery Rhymes by Beatrix Potter.txt 23889 4 The Tale of Tom Kitten by Beatrix Potter.txt 24788 5 The Tale of Mr. Jeremy Fisher by Beatrix Potter.txt 24794 6 The Anti-Slavery Alphabet by Anonymous.txt 25114 7 The Tale of Peter Rabbit by Beatrix Potter.txt 26017 8 The Tale of the Flopsy Bunnies by Beatrix Potter.txt 26566 9 Twas the Night before Christmas A Visit from St. Nicholas by Clement Clarke Moore.txt 26579 10 The House That Jack Built by Randolph Caldecott.txt 26922 11 The Tale of Benjamin Bunny by Beatrix Potter.txt 27141 12 Little Black Sambo by Helen Bannerman.txt 27164 13 The Tale of Ginger and Pickles by Beatrix Potter.txt 27384 14 The Tale of Johnny Town-Mouse by Beatrix Potter.txt 27624 15 The Tale of Squirrel Nutkin by Beatrix Potter.txt 27728 16 The Tale of Jemima Puddle-Duck by Beatrix Potter.txt 28055 17 The Babes in the Wood by Randolph Caldecott.txt 28134 18 The Book of Ornamental Alphabets, Ancient and Medieval, from the Eighth Century.txt 28447 19 The Bad Child's Book of Beasts by Hilaire Belloc.txt 28882 20 The Tale of Mrs. Tittlemouse by Beatrix Potter.txt 29039 21 Johann Sebastian Bach The story of the boy who sang in the streets by Tapper.txt 29133 22 The Little Red Hen by Florence White Williams.txt 29223 23 The Tale of Mrs. Tiggy-Winkle by Beatrix Potter.txt 29548 24 Mother Goose or the Old Nursery Rhymes by Kate Greenaway.txt 30810 25 The Sleeping Beauty Picture Book by Walter Crane.txt 31262 26 Moby Dick by Herman Melville.txt 31690 27 The Pied Piper of Hamelin by Robert Browning.txt 33601 28 Time Enough at Last by Lyn Venable.txt 33820 29 A New Species of Frog (Genus Tomodactylus) from Western México by Robert G. Webb.txt 34603 80 30 The Tale of Samuel Whiskers by Beatrix Potter.txt 36044 31 Struwwelpeter Merry Stories and Funny Pictures by Heinrich Hoffmann.txt 36071 32 Children's Hour with Red Riding Hood and Other Stories by pseud. Watty Piper.txt 36220 33 The Tale of the Pie and the Patty Pan by Beatrix Potter.txt 37162 34 The Tailor of Gloucester by Beatrix Potter.txt 37380 35 Beethoven The story of a little boy who was forced to practice by Thomas Tapper.txt 37471 36 Max und Moritz Eine Bubengeschichte in sieben Streichen by Wilhelm Busch.txt 37872 37 There Will Be School Tomorrow by V. E. Thiessen.txt 38739 38 Der Struwwelpeter by Heinrich Hoffmann.txt 40648 39 The Fairy Books of Andrew Lang by Andrew Lang.txt 41089 40 The Magic Fishbone by Charles Dickens.txt 42867 41 A Book of Nonsense by Edward Lear.txt 43036 42 My First Picture Book by Joseph Martin Kronheim.txt 45134 43 21 by Frank Crane.txt 47315 44 The Golden Goose Book by L. Leslie Brooke.txt 48005 45 The Tale of Mr. Tod by Beatrix Potter.txt 48592 46 The Book of Nonsense by Edward Lear.txt 48747 47 Disputation of Doctor Martin Luther on the Power and Efficacy of Indulgences.txt 49695 48 The Frog Prince and Other Stories by Walter Crane.txt 51112 49 The Sex Side of Life An Explanation for Young People by Mary Ware Dennett.txt 53621 50 Uncle Remus and Brer Rabbit by Joel Chandler Harris.txt 58273 51 More Russian Picture Tales by Valerian Viliamovich Karrik.txt 58722 52 A Child's Garden of Verses by Robert Louis Stevenson.txt 60897 53 Finger plays for nursery and kindergarten by Emilie Poulsson.txt 61934 54 The Fall of the House of Usher by Edgar Allan Poe.txt 63250 55 Fables de La Fontaine by Jean de La Fontaine.txt 63480 56 McGuffey's First Eclectic Reader, Revised Edition by William Holmes McGuffey.txt 63819 57 Sour Grapes A Book of Poems by William Carlos Williams.txt 64723 58 The Cat and the Mouse A Book of Persian Fairy Tales by James and Neill.txt 65675 59 A Primary Reader Old-time Stories, Fairy Tales and Myths Retold by Children.txt 68582 60 English as she is spoke; or, a jest in sober earnest by Carolino and Fonseca.txt 70149 61 The Peter Patter Book of Nursery Rhymes by Leroy F. Jackson.txt 79395 62 The Tao Teh King, or the Tao and its Characteristics by Laozi.txt 80227 63 The Botanical Magazine, Vol. 1 by William Curtis.txt 83147 64 The Book of the Dead by Sir E. A. Wallis Budge.txt 86131 65 Dhammapada, a Collection of Verses; Being One of the Canonical Books of the.txt 88062 66 The History Of The Decline And Fall Of The Roman Empire by Edward Gibbon.txt 89377 67 The Essence of Buddhism by Sir Edwin Arnold and Ernest M. Bowden.txt 91561 68 The National Nursery Book by Unknown.txt 93201 69 The Communist Manifesto by Friedrich Engels and Karl Marx.txt 94245 70 Short Stories by Khristo Botev.txt 100619 71 Mother Stories from the Old Testament by Anonymous.txt 100989 72 The Magna Carta by Anonymous.txt 101688 81 73 Mother Stories from the New Testament by Anonymous.txt 102051 74 Little Wars; a game for boys from twelve years of age to one hundred and fifty.txt 106529 75 Lysistrata by Aristophanes.txt 106643 76 Alice's Adventures Under Ground by Lewis Carroll.txt 107595 77 The Shanty Book, Part I, Sailor Shanties by Richard Runciman Terry.txt 109582 78 The Adventures of Buster Bear by Thornton W. Burgess.txt 109595 79 The Real Mother Goose by Blanche Fisher Wright.txt 111980 80 The Project Gutenberg eBook, Jussi Puranen, by Maiju Lassila.txt 114807 81 The Clouds by Aristophanes.txt 115716 82 My Knitting Book by Miss Lambert.txt 116471 83 McGuffey's Second Eclectic Reader by William Holmes McGuffey.txt 121597 84 Harper's Young People, August 9, 1881 by Various.txt 121634 85 The Tales of Mother Goose by Charles Perrault.txt 121767 86 Areopagitica by John Milton.txt 123147 87 Anno 7603, by Johan Herman Wessel.txt 124299 88 A Little Book of Filipino Riddles by Frederick Starr.txt 126421 89 The Book of Tea by Kakuzo Okakura.txt 126545 90 Birds and Nature, Vol. VIII, No. 5, December 1900 by Various.txt 129534 91 A Classification and Subject Index for Cataloguing and Arranging the Books and.txt 129773 92 Die Leiden des jungen Werther — Band 1 by Johann Wolfgang von Goethe.txt 132253 93 Birds and Nature Vol. VIII, No. 3, October 1900 by Various.txt 132471 94 Über Psychoanalyse Fünf Vorlesungen by Sigmund Freud.txt 137354 95 Mestari Nyke, by Maiju Lassila.txt 137534 96 The Big Book of Nursery Rhymes by Various.txt 137638 97 Metamorphosis Franz Kafka.txt 141419 98 The Beacon Second Reader by James H. Fassett.txt 142793 99 The Orphan's Home Mittens and George's Account of the Battle of Roanoke Island.txt 143276 100 USDOA Farmer's Bulletin, No. 59, Bee Keeping by Frank Benton.txt 144244 101 Essays in the Art of Writing by Robert Louis Stevenson.txt 144682 102 The Birds by Aristophanes.txt 145167 103 Medea of Euripides by Euripides.txt 146198 104 The Book of Wonder by Baron Edward John Moreton Drax Plunkett Dunsany.txt 146204 105 The Song Celestial; Or, Bhagavad-Gîtâ (from the Mahâbhârata) by Sir Edwin Arnold.txt 147174 106 The Book of War The Military Classic of the Far East by Sunzi and Wutzu.txt 148544 107 Reigen Zehn Dialoge by Arthur Schnitzler.txt 151094 108 Mental Efficiency, and Other Hints to Men and Women by Arnold Bennett.txt 154108 109 Die Leiden des jungen Werther — Band 2 by Johann Wolfgang von Goethe.txt 155783 110 A Collection of Beatrix Potter Stories by Beatrix Potter.txt 156391 111 Ett pennskaft som piga, by Anton Holtz.txt 157135 112 Ghosts by Henrik Ibsen.txt 159796 113 Meditationes de prima philosophia by René Descartes.txt 162106 114 The Strange Case of Dr. Jekyll and Mr. Hyde by Robert Louis Stevenson.txt 162811 115 A Doll's House a play by Henrik Ibsen.txt 165567 82 116 Carmen by Prosper Mérimée.txt 166015 117 McGuffey's Third Eclectic Reader by William Holmes McGuffey.txt 168148 118 A Doll's House by Henrik Ibsen.txt 169294 119 The Rural Magazine, and Literary Evening Fire-Side, Vol. 1 No. 10 (1820) by Various.txt 170083 120 Arbetarens hustru by Minna Canth.txt 170138 121 McGuffey's Eclectic Spelling Book by Alexander H. McGuffey.txt 170395 122 An Elementary Spanish Reader by Earl Stanley Harrison.txt 170846 123 A Field Book of the Stars by William Tyler Olcott.txt 172493 124 Spartacus by Konrad Lehtimäki.txt 172688 125 Die stählerne Mauer by Ludwig Ganghofer.txt 173065 126 The Blissylvania Post-Office by Marion Ames Taggart.txt 175044 127 Teatro galante by Eduardo Zamacois.txt 176272 128 The Missionary; vol. I by Lady Sidney Morgan.txt 177071 129 Alice's Adventures in Wonderland by Lewis Carroll.txt 177428 130 The Great Big Treasury of Beatrix Potter by Beatrix Potter.txt 179823 131 Othello, the Moor of Venice by William Shakespeare.txt 180537 132 Outlines of Lessons in Botany, Part I; from Seed to Leaf by Jane H. Newell.txt 182323 133 The Square Jaw by Henry Ruffin and André Tudesq.txt 182797 134 The Missionary; vol. III by Lady Sidney Morgan.txt 183428 135 Les Fleurs du Mal by Charles Baudelaire.txt 183596 136 Hamlet by William Shakespeare.txt 184150 137 Through the Looking-Glass by Lewis Carroll.txt 185936 138 King Lear by William Shakespeare.txt 186099 139 The Tragedy of King Lear by William Shakespeare.txt 186335 140 The Analects of Confucius (from the Chinese Classics) by Confucius.txt 188455 141 Fox Trapping A Book of Instruction Telling How to Trap, Snare, Poison and Shoot.txt 190427 142 Fifty Famous People A Book of Short Stories by James Baldwin.txt 191313 143 Der Held von Uganda by Carl Schneider.txt 192000 144 The Book of Old-Fashioned Flowers by Harry Roberts.txt 192427 145 Hamlet, Prince of Denmark by William Shakespeare.txt 193083 146 The War by James H. Wood.txt 193618 147 Historically Famous Lighthouses by United States Coast Guard.txt 194269 148 En piga bland pigor, by Ester Blenda Nordström.txt 194943 149 De complete werken van Joost van Vondel by Joost van den Vondel.txt 194983 150 The Missionary; vol. II by Lady Sidney Morgan.txt 197182 151 Doctrina Christiana by Edwin Wolf.txt 198291 152 The Call of the Wild by Jack London.txt 198520 153 Harper's Round Table, November 19, 1895 by Various.txt 199438 154 The Yoga Sutras of Patanjali The Book of the Spiritual Man by Patañjali.txt 199467 155 Zadig by Voltaire.txt 199960 156 The First Book of Adam and Eve by Rutherford Hayes Platt.txt 200931 157 The Time Machine by H. G. Wells.txt 201900 158 Iloinen poika by Bjørnstjerne Bjørnson.txt 203406 83 159 Take It From Dad by George G. Livermore.txt 204056 160 The Italian Cook Book by Maria Gentile.txt 206612 161 The Nursery Rhyme Book by Andrew Lang and L. Leslie Brooke.txt 207603 162 Tunturikertomuksia, by Arvi Järventaus.txt 207643 163 The Stag Cook Book by Carroll Mac Sheridan.txt 208230 164 English Embroidered Bookbindings by Cyril James Humphries Davenport.txt 208294 165 Motor Matt's Promise by Stanley R. Matthews.txt 209829 166 Motor Matt's Queer Find by Stanley R. Matthews.txt 210583 167 Women's Suffrage by Dame Millicent Garrett Fawcett.txt 210856 168 Berkshire by H. W. Monckton.txt 213822 169 Nonsense Books by Edward Lear.txt 214825 170 Stories and Letters From the Trenches by Various.txt 216086 171 My Book of Favourite Fairy Tales by Edric Vredenburg.txt 216531 172 Mrs. Warren's Profession by Bernard Shaw.txt 217355 173 New Royal Cook Book by New York Royal baking powder company.txt 217392 174 The Art of Illustration by Henry Blackburn.txt 217514 175 Le ore inutili by Amalia Guglielminetti.txt 218861 176 David Blaize and the Blue Door by E. F. Benson.txt 220040 177 Manual for the Solution of Military Ciphers, by.txt 220654 178 Pioneer Imprints From Fifty States by Roger J. Trienens.txt 220894 179 The Art of Candy Making by The Home Candy Makers.txt 220905 180 Steam Turbines by Hubert E. Collins.txt 221780 181 The Project Gutenberg EBook of 1000 Mythological Characters Briefly.txt 222865 182 Dumbells of Business by Proff. O. U. Bojack.txt 223157 183 Boys' Book of Model Boats by Raymond F. Yates.txt 224789 184 The Praise of Folly by Desiderius Erasmus.txt 225704 185 Faust — Part 1 by Johann Wolfgang von Goethe.txt 226465 186 Faust Der Tragödie erster Teil by Johann Wolfgang von Goethe.txt 229647 187 Candide by Voltaire.txt 229736 188 The Celtic Twilight by W. B. Yeats.txt 231273 189 Das Stuttgarter Hutzelmännlein by Eduard Mörike.txt 231756 190 Uncle Wiggily's Adventures by Howard Roger Garis.txt 231973 191 Faust Eine Tragödie by Johann Wolfgang von Goethe.txt 232542 192 The Suffrage Cook Book by Mrs. L. O. Kleber.txt 233501 193 Heart of Darkness by Joseph Conrad.txt 233502 194 Fables of Field and Staff by James Albert Frye.txt 233526 195 A Sentimental Journey Through France and Italy by Laurence Sterne.txt 235076 196 Bible Studies by J. M. Wheeler.txt 235357 197 The Mornin'-Glory Girl by Kathryn Pocklington and Alice Maud Winlow.txt 236286 198 The Negro Problem by Charles W. Chesnutt et al..txt 237128 199 Mein buntes Buch by Hermann Löns.txt 237592 200 Favorite Fairy Tales by Logan Marshall.txt 238740 201 From Headquarters by James Albert Frye.txt 238796 84 202 On The Stage-And Off by Jerome K. Jerome.txt 239172 203 The Women of Tomorrow by William Hard.txt 239570 204 Das Buch Henoch by Andreas Gottlieb Hoffmann.txt 239687 205 Hamlet, Prinz von Dännemark by William Shakespeare.txt 240159 206 The Thirty-Nine Steps by John Buchan.txt 240539 207 Plays of Sophocles Oedipus the King; Oedipus at Colonus; Antigone by Sophocles.txt 241607 208 Aesop's Fables; a new translation by Aesop.txt 243023 209 Human, All Too Human A Book for Free Spirits by Friedrich Wilhelm Nietzsche.txt 243917 210 Rasselas, Prince of Abyssinia by Samuel Johnson.txt 245949 211 The Mysterious Stranger, and Other Stories by Mark Twain.txt 246861 212 Haudan partaalla by E. Juncker.txt 247724 213 Dictionary of English Proverbs and Proverbial Phrases by Thomas Preston.txt 248429 214 Faust by Johann Wolfgang von Goethe.txt 249321 215 Yön lapsi by Jack London.txt 249629 216 Blood Brothers A Medic's Sketch Book by Eugene C. Jacobs.txt 250987 217 El Abate Constantin by Ludovic Halévy.txt 251368 218 An Old Babylonian Version of the Gilgamesh Epic by Clay and Jastrow.txt 251720 219 The Oriental Story Book A Collection of Tales by Wilhelm Hauff.txt 252064 220 The Battle of the Books, and other Short Pieces by Jonathan Swift.txt 252079 221 The Book of Dragons by E. Nesbit.txt 252407 222 The Turn of the Screw by Henry James.txt 252946 223 Döda fallet by Per Hallström.txt 255029 224 Secrets of the Woods by William J. Long.txt 255316 225 Den bergtagna by Victoria Benedictsson and Axel Lundegård.txt 255987 226 Lyrics from the Song-Books of the Elizabethan Age by A. H. Bullen.txt 256563 227 The Sorrows of Young Werther by Johann Wolfgang von Goethe.txt 259352 228 The Diary of a Nobody by George Grossmith and Weedon Grossmith.txt 259845 229 Moorland Idylls, by Grant Allen.txt 260882 230 Taras Bulba by Nikolai Vasilevich Gogol.txt 263193 231 Nuoruuteni muistelmia by Arvid Järnefelt.txt 265000 232 The Chinese Classics — Volume 1 Confucian Analects by James Legge.txt 266182 233 Dave Dashaway, Air Champion by Roy Rockwood.txt 266355 234 The Sea Fairies by L. Frank Baum.txt 267566 235 The Island of Doctor Moreau by H. G. Wells.txt 267689 236 Rannikon ratsastaja by Theodor Storm.txt 267836 237 The Century of Inventions of the Marquis of Worcester by Charles F. Partington.txt 268117 238 Straw Hats by Harry Inwards.txt 268478 239 Forty Years at El Paso by William Wallace Mills.txt 271296 240 The History of the Island of Dominica, by Thomas Atwood.txt 271860 241 Incesto by Eduardo Zamacois.txt 273483 242 Billy Bounce by Dudley A Bragdon and W. W. Denslow.txt 273569 243 Ritchie's Fabulae Faciles A First Latin Reader by Francis Ritchie.txt 275033 244 Electricity for Boys by James Slough Zerbe.txt 275247 85 245 Ghost Stories of an Antiquary by M. R. James.txt 275350 246 Early Lives of Charlemagne.txt 279385 247 The Khaki Boys At The Front by Gorden Bates.txt 279921 248 In Praise of Folly by Desiderius Erasmus.txt 279954 249 The Double Garden by Maurice Maeterlinck.txt 280693 250 Not that it Matters by A. A. Milne.txt 281370 251 Dutch Bulbs and Gardens by Sophie Lyall and Una Lucy Silberrad.txt 281927 252 Histoires insolites by Auguste de Villiers de L'Isle-Adam.txt 282765 253 La promessa sposa di Lammermoor, Tomo I (of 3) by Walter Scott.txt 283918 254 Peter Pan by J. M. Barrie.txt 284796 255 A Chinese Wonder Book by Norman Hinsdale Pitman.txt 285098 256 Sesame and Lilies by John Ruskin.txt 285499 257 The Wonder Book of Bible Stories by Logan Marshall.txt 285681 258 The Red Badge of Courage An Episode of the American Civil War by Stephen Crane.txt 285700 259 A Book of German Lyrics by Friedrich Bruns.txt 287276 260 Encyclopedia of Diet Vol. 2 (of 5) by Eugene Christian.txt 288492 261 Viaje a America, Tomo 1 de 2 by Rafael Puig y Valls.txt 289912 262 La Folle Journée ou le Mariage de Figaro by Pierre Augustin Caron de Beaumarchais.txt 290210 263 Il codice di Perelà by Aldo Palazzeschi.txt 290998 264 the Fire Dog, by Lily F. Wesselhoeft.txt 291073 265 The Sepoy by Edmund Candler.txt 291864 266 Electric Bells and All About Them by Selimo Romeo Bottone.txt 291959 267 A First Spanish Reader by Alfred Remy and Erwin W. Roessler.txt 292118 268 cClure's Magazine, Vol. 1, No. 6, November 1893 by Various.txt 292230 269 A Tale of a Tub by Jonathan Swift.txt 292388 270 Sun, Sand and Somals by H. Rayne.txt 292574 271 La promessa sposa di Lammermoor, Tomo III (of 3) by Walter Scott.txt 294513 272 English Grammar and Composition for Public Schools by George Armstrong.txt 295717 273 Art in Needlework A Book about Embroidery by Mary Buckle and Lewis Foreman Day.txt 298410 274 The Jungle Book by Rudyard Kipling.txt 298778 275 The Invisible Man A Grotesque Romance by H. G. Wells.txt 299025 276 The Ocean Wireless Boys on the Atlantic, by Wilbur Lawton.txt 299409 277 Különféle magyarok meg egyéb népek by István Tömörkény.txt 300421 278 Volks-Kochbuch by Hedwig Heyl.txt 300588 279 Old Cookery Books and Ancient Cuisine by William Carew Hazlitt.txt 300707 280 Just William by Richmal Crompton.txt 300823 281 The Land of Tomorrow by William B. Stephenson.txt 302306 282 Wild Animals I Have Known by Ernest Thompson Seton.txt 302413 283 The Prince by Niccolò Machiavelli.txt 305864 284 On a Chinese Screen by W. Somerset Maugham.txt 305896 285 Giardino di Ricreatione by John Florio.txt 305954 286 Skyttes på Munkeboda by Mathilda Malling.txt 306534 287 Del libro impreso al libro digital by Marie Lebert.txt 306923 86 288 English Translations From The Greek by.txt 307021 289 Émile; Or, Concerning Education; Extracts by Jean-Jacques Rousseau.txt 309430 290 The Robbers by Friedrich Schiller.txt 309990 291 The Orbis Pictus by Johann Amos Comenius.txt 310106 292 The Motor Boat Club in Florida by H. Irving Hancock.txt 310621 293 Gestalten der Wildnis by Sir Charles G. D. Roberts.txt 312113 294 Herraskartano ja legendoja by Selma Lagerlöf.txt 313128 295 The Border Boys on the Trail by John Henry Goldfrap.txt 313556 296 The Prisoner of Zenda by Anthony Hope.txt 314914 297 The Third Circle by Frank Norris.txt 315337 298 The Motor Boat Club Off Long Island, by H. Irving Hancock.txt 315611 299 Project Gutenberg's Three Apostles of Quakerism, by Benjamin Rhodes.txt 315649 300 Goethe und Werther, by Johann Wolfgang von Goethe.txt 315692 301 A Record of Buddhistic Kingdoms by Faxian.txt 317641 302 Boy Scouts on the Trail, by John Garth.txt 318373 303 Musk-Ox, Bison, Sheep and Goat by Grinnell, Whitney, and Wister.txt 319264 304 The St. Gregory Hymnal and Catholic Choir Book by Nicola A. Montani.txt 319375 305 La promessa sposa di Lammermoor, Tomo II (of 3) by Walter Scott.txt 320223 306 Captains Courageous A Story of the Grand Banks by Rudyard Kipling.txt 320322 307 Napoleon Bonaparte by John S. C. Abbott.txt 321743 308 Ratsmädelgeschichten by Helene Böhlau.txt 321783 309 Herland by Charlotte Perkins Gilman.txt 322608 310 The Story of Young Abraham Lincoln by Wayne Whipple.txt 323087 311 A Wonder Book for Girls & Boys by Nathaniel Hawthorne.txt 323169 312 The Motor Boys on the Border by Clarence Young.txt 323973 313 Andersen's Fairy Tales by H. C. Andersen.txt 324862 314 March Anson and Scoot Bailey of the U.S. Navy by Gregory Duncan.txt 324970 315 The Coming Race by Baron Edward Bulwer Lytton Lytton.txt 325336 316 Norma Kent of the WACS by Roy J. Snell.txt 326086 317 Punaiset ja valkoiset by Kössi Kaatra.txt 328199 318 Thirteen Stories by R. B. Cunninghame Graham.txt 328786 319 Cunnie Rabbit, Mr. Spider and the Other Beef by Cronise and Ward.txt 328920 320 Black Beauty by Anna Sewell.txt 329680 321 Flying Machines Construction and Operation by Chanute, Jackman, and Russell.txt 330187 322 Legendoja Kristuksesta by Selma Lagerlöf.txt 330862 323 The Last Days of Fort Vaux by Henry Bordeaux.txt 331428 324 Il Professore Romualdo by Enrico Castelnuovo.txt 332448 325 Anglo-Dutch Rivalry during the First Half of the Seventeenth Century by Edmundson.txt 332452 326 Bookbinding, and the Care of Books by Douglas Cockerell.txt 332517 327 Homes and Careers in Canada by Harry Jeffs.txt 333277 328 The Book of Camp-Lore and Woodcraft by Daniel Carter Beard.txt 333564 329 Onnelliset by Arvid Järnefelt.txt 334166 330 Il Re bello by Aldo Palazzeschi.txt 334675 87 331 The Bibliotaph, and Other People by Leon H. Vincent.txt 335756 332 Der Sinn und Wert des Lebens by Rudolf Eucken.txt 335773 333 De Lof der Zotheid by Desiderius Erasmus.txt 335911 334 Harry by Kaarlo August Järvi.txt 336055 335 Boys of Oakdale Academy by Morgan Scott.txt 336281 336 Your Child Today and Tomorrow by Sidonie Matsner Gruenberg.txt 337424 337 Kalatyttö by Bjørnstjerne Bjørnson.txt 337617 338 Viaje a America, Tomo 2 de 2 by Rafael Puig y Valls.txt 337726 339 Auringon poika, by Jack London.txt 337796 340 Èl Sgner Pirein by Antonio Fiacchi.txt 339169 341 Figuras americanas, by Miguel A. Pérez.txt 340403 342 El libro de las mil noches y una noche; t 3, by.txt 341768 343 Der Weltkrieg, I. Band (of 3) by Karl Helfferich.txt 343166 344 Opúsculos por Alexandre Herculano - Tomo 07 by Alexandre Herculano.txt 344192 345 Stories of Fortune by Various.txt 344727 346 Faust Der Tragödie zweiter Teil by Johann Wolfgang von Goethe.txt 344856 347 Briefe, die ihn nicht erreichten by Elisabeth Heyking.txt 346036 348 Colomba by Prosper Mérimée.txt 346870 349 The Man Who Was Thursday A Nightmare by G. K. Chesterton.txt 347940 350 A Year with the Birds by W. Warde Fowler.txt 348039 351 The Great Diamond Hoax by Asbury Harpending.txt 349658 352 Frank Armstrong, Drop Kicker, by Matthew M. Colton.txt 350275 353 The Wind in the Willows by Kenneth Grahame.txt 351483 354 Die Bibliothek meines Oheims by Rudolf Töpffer.txt 351940 355 chetsen uit Zeeland by Anonymous.txt 355314 356 Frank Armstrong at Queens, by Matthew M. Colton.txt 356062 357 The Ladies' Work-Book by Unknown.txt 357343 358 Vita di Guarino Veronese by Remigio Sabbadini.txt 357488 359 The Month of Mary, According to the Spirit.txt 357938 360 On the Trail An Outdoor Book for Girls by Adelia B. Beard and Lina Beard.txt 359170 361 Turkish Harems & Circassian Homes by Annie Jane Harvey.txt 359306 362 The Kama Sutra of Vatsyayana by Vatsyayana.txt 359508 363 Marianela by Benito Pérez Galdós.txt 359919 364 A Desk-Book of Errors in English by Frank H. Vizetelly.txt 360426 365 A Desk-Book of Errors in English, by Frank H. Vizetelly.txt 360426 366 Chez les passants by Auguste de Villiers de L'Isle-Adam.txt 362471 367 First Italian Readings by Various.txt 365273 368 The Young Captain, by Elijah Kellogg.txt 365349 369 The War of the Worlds by H. G. Wells.txt 365415 370 Opúsculos por Alexandre Herculano - Tomo 01 by Alexandre Herculano.txt 366071 371 Sult by Knut Hamsun.txt 366166 372 A Thief in the Night A Book of Raffles' Adventures by E. W. Hornung.txt 367081 373 Lendas e Narrativas (Tomo I) by Alexandre Herculano.txt 367617 88 374 Tomorrow by Victoria Cross.txt 368267 375 Rose, Linde und Silberner Stern, by Josephine Siebe.txt 368388 376 Religion and the War by Yale University. Divinity School.txt 369097 377 The Strand Magazine No. 97 (January, 1899) by Various.txt 369264 378 The Project Gutenberg EBook of Across Texas, by Edward Sylvester Ellis.txt 369956 379 Opúsculos por Alexandre Herculano - Tomo 04 by Alexandre Herculano.txt 369966 380 Text Book of Biology, Part 1 Vertebrata by H. G. Wells.txt 370189 381 Godey's Lady's Book, Vol. 42, January, 1851 by Various.txt 371448 382 The Children of Odin The Book of Northern Myths by Padraic Colum.txt 371998 383 Ludwig the Second by Clara Tschudi.txt 372309 384 Opúsculos por Alexandre Herculano - Tomo 06 by Alexandre Herculano.txt 372982 385 Dansen på Frötjärn by Hjalmar Bergman.txt 372989 386 Studien und Plaudereien. First Series by Sigmon Martin Stern.txt 373089 387 Eighteenth Century Vignettes by Austin Dobson.txt 374024 388 The Second Jungle Book by Rudyard Kipling.txt 374049 389 The Haunted Bookshop by Christopher Morley.txt 375209 390 Despertar Para Morir, by Concha Espina.txt 378038 391 Diane of Ville Marie by Blanche Lucile Macdonnell.txt 378139 392 The Kreutzer Sonata and Other Stories by graf Leo Tolstoy.txt 379239 393 The Beasts of Tarzan by Edgar Rice Burroughs.txt 380452 394 Within the Capes by Howard Pyle.txt 380815 395 The Revolt of Man by Walter Besant.txt 382221 396 Hunger by Knut Hamsun.txt 382801 397 Die Hexenrichter von Würzburg by Franz von Seeburg.txt 383012 398 Poems & Ballads (First Series) by Algernon Charles Swinburne.txt 383416 399 The Wit and Humor of America, Volume I. (of X.) by Marshall Pinckney Wilder.txt 383795 400 The Curse of Pocahontas, by Wenona Gilman.txt 385000 401 Woman in Sacred History, by Harriet Beecher Stowe.txt 385851 402 The Awakening, and Selected Short Stories by Kate Chopin.txt 386707 403 McGuffey's Fourth Eclectic Reader by William Holmes McGuffey.txt 388597 404 Joseph Andrews, Vol. 1 by Henry Fielding.txt 388605 405 Opúsculos por Alexandre Herculano - Tomo 08 by Alexandre Herculano.txt 389035 406 Opúsculos por Alexandre Herculano - Tomo 05 by Alexandre Herculano.txt 389315 407 The Book of Snobs by William Makepeace Thackeray.txt 390455 408 Three Men in a Boat by Jerome K. Jerome.txt 390849 409 Speaking of the Turks by bey K. Ziya Mufti-zada.txt 391343 410 Treasure Island by Robert Louis Stevenson.txt 391563 411 How to Write Letters (Formerly The Book of Letters) by Mary Owens Crowther.txt 392101 412 Colin Campbell by Archibald Forbes.txt 394957 413 El Comendador Mendoza by Juan Valera.txt 396196 414 The Mahabharata of Krishna-Dwaipayana Vyasa Translated into English Prose.txt 396421 415 The Critique of Practical Reason by Immanuel Kant.txt 397363 416 Mademoiselle de Maupin, Volume 2 (of 2), by.txt 398133 89 417 Dubliners by James Joyce.txt 398340 418 Around the World in Eighty Days by Jules Verne.txt 398631 419 The Russian Story Book by Frank C. Papé and Richard Wilson.txt 398732 420 A Princess of Mars by Edgar Rice Burroughs.txt 399120 421 Tarzan and the Jewels of Opar by Edgar Rice Burroughs.txt 399920 422 Arts and Crafts Essays by Arts and Crafts Exhibition Society.txt 401357 423 Ten Acres Enough by Edmund Morris.txt 402670 424 Front Lines, by Boyd Cable.txt 402791 425 Old Country Life by S. Baring-Gould.txt 403429 426 The Daughters of the Little Grey House by Marion Ames Taggart.txt 404479 427 THE WHITE CAT.txt 405528 428 Across the Andes by Charles Johnson Post.txt 406280 429 The First Men in the Moon by H. G. Wells.txt 406553 430 Mademoiselle de Maupin, Volume 1 (of 2), by.txt 407269 431 Novelle umoristiche by Adolfo Albertazzi.txt 408704 432 Mistress Spitfire by J. S. Fletcher.txt 408971 433 La dame aux camélias by Alexandre Dumas.txt 409470 434 Outings At Odd Times, by Charles Conrad Abbott.txt 411300 435 Sylvie and Bruno (Illustrated) by Lewis Carroll.txt 411693 436 Man and Superman A Comedy and a Philosophy by Bernard Shaw.txt 411847 437 Gargantua and Pantagruel, Illustrated, Book 1 by François Rabelais.txt 413150 438 Heleija, by Otto Ludwig.txt 414710 439 Further Chronicles of Avonlea by L. M. Montgomery.txt 416011 440 The great probability of a North West Passage by Thomas Jefferys.txt 416221 441 A Girl of the North by Susan Morrow Jones.txt 416260 442 The Alberta Public School Speller, by Anonymous.txt 416480 443 Captain of the Crew, by Ralph Henry Barbour.txt 416730 444 Opúsculos por Alexandre Herculano - Tomo 02 by Alexandre Herculano.txt 417763 445 Five Little Peppers and How They Grew by Margaret Sidney.txt 417790 446 Opúsculos por Alexandre Herculano - Tomo 03 by Alexandre Herculano.txt 418636 447 Social England under the Regency, Vol. 2 (of 2) by John Ashton.txt 419515 448 Fanny Burney by Austin Dobson.txt 419982 449 Translations of Shakuntala and Other Works by Kalidasa.txt 421454 450 Robinson in Australien by Amalia Schoppe.txt 421717 451 The Radio Amateur's Hand Book by A. Frederick Collins.txt 421784 452 The Adventures of Tom Sawyer by Mark Twain.txt 421884 453 Grettir the Outlaw by S. Baring-Gould.txt 422266 454 Winesburg, Ohio A Group of Tales of Ohio Small Town Life by Sherwood Anderson.txt 424192 455 The Indian Fairy Book by Henry Rowe Schoolcraft.txt 424205 456 The Burgess Bird Book for Children by Thornton W. Burgess.txt 425860 457 Risti ja noitarumpu by Arvi Järventaus.txt 427308 458 White Fang by Jack London.txt 427341 459 De zoon van Kazan by James Oliver Curwood.txt 427581 90 460 Joseph Andrews, Vol. 2 by Henry Fielding.txt 427702 461 Prester John by John Buchan.txt 428406 462 Notes on Railroad Accidents by Charles Francis Adams.txt 430332 463 Schools of to-morrow, by John Dewey and Evelyn Dewey.txt 430996 464 Husks by Marion Harland.txt 431220 465 Interpretations of Poetry and Religion, by.txt 431498 466 Kunnanlapsi by Marie von Ebner-Eschenbach.txt 431535 467 Library Cataloguing by J. Henry Quinn.txt 433245 468 The Writings of Thomas Paine — Volume 4 (1794-1796) The Age of Reason by Paine.txt 433358 469 The Brothers Dalziel by Edward Dalziel and George Dalziel.txt 438415 470 English Industries of the Middle Ages by Louis Francis Salzmann.txt 438767 471 The Burgess Animal Book for Children by Thornton W. Burgess.txt 439538 472 The Indian Fairy Book From the Original Legends by Cornelius Mathews.txt 442204 473 American Leaders and Heroes A preliminary text-book in United States History.txt 442262 474 Jungle Tales of Tarzan by Edgar Rice Burroughs.txt 443571 475 The Mikirs by Edward Stack.txt 444549 476 Der Doppelgänger by Fyodor Dostoyevsky.txt 446143 477 Gloria (segunda parte), by Benito Pérez Galdós.txt 446384 478 Up from Slavery An Autobiography by Booker T. Washington.txt 447021 479 Frankenstein; Or, The Modern Prometheus by Mary Wollstonecraft Shelley.txt 448689 480 Florens Abentheuer in Afrika, und ihre.txt 448758 481 A Journey into the Interior of the Earth by Jules Verne.txt 448780 482 Something New by P. G. Wodehouse.txt 448853 483 Kidnapped by Robert Louis Stevenson.txt 450807 484 pg48672.txt 452494 485 Procopius by Procopius.txt 452655 486 Ihmisruumiin substanssi suomalais-ugrilaisten kansojen taikuudessa by Hämäläinen.txt 453639 487 The History and Romance of Crime; Non-Criminal Prisons by Arthur Griffiths.txt 454510 488 A Hundred Years Hence by T. Baron Russell.txt 454792 489 The Food of the Gods and How It Came to Earth by H. G. Wells.txt 456451 490 Moonfleet by John Meade Falkner.txt 457602 491 La Gaviota by Fernán Caballero.txt 459924 492 Northanger Abbey by Jane Austen.txt 460999 493 The Picture of Dorian Gray by Oscar Wilde.txt 462075 494 The Complete Book of Cheese by Bob Brown.txt 462088 495 The Country of the Dwarfs by Paul B. Du Chaillu.txt 462895 496 The Golden Asse by Apuleius.txt 465658 497 The Black Arrow A Tale of Two Roses by Robert Louis Stevenson.txt 466416 498 Ginseng and Other Medicinal Plants by A. R. Harding.txt 472012 499 King Solomon's Mines by H. Rider Haggard.txt 473555 500 Meine Lebens-Erinnerungen - Band 3 (of 4) by Adam Gottlob Oehlenschläger.txt 474168 501 Calvary by Octave Mirbeau.txt 474330 502 Mustalaistytön ennustus, by Prosper Mérimée.txt 475682 91 503 A Book of Giants by Henry Wysham Lanier.txt 476098 504 Zuleika Dobson; Or, An Oxford Love Story by Sir Max Beerbohm.txt 476514 505 Matkustus maan keskipisteeseen by Jules Verne.txt 477074 506 Spies and Secret Service by Hamil Grant.txt 477713 507 Illuminated Manuscripts by John William Bradley.txt 478146 508 The Best Ghost Stories by Arthur B. Reeve and Joseph Lewis French.txt 478427 509 På Elghyttan by Elisabeth Beskow.txt 479755 510 Piccadilly Jim by P. G. Wodehouse.txt 480684 511 Rupert of Hentzau From The Memoirs of Fritz Von Tarlenheim by Anthony Hope.txt 481059 512 The Trial by Franz Kafka.txt 481098 513 Bouvard and Pécuchet A Tragi-comic Novel of Bourgeois Life by Gustave Flaubert.txt 481258 514 Countess Vera by Mrs. Alex. McVeigh Miller.txt 482308 515 Katy Gaumer by Elsie Singmaster.txt 482318 516 The Private Memoirs and Confessions of a Justified Sinner by James Hogg.txt 483097 517 Vikram and the Vampire by Richard F. Burton and F.R.G.S..txt 483748 518 renda's Cousin at Radcliffe by Helen Leah Reed.txt 489958 519 Sylvie and Bruno Concluded (Illustrated) by Lewis Carroll.txt 490280 520 Erewhon; Or, Over the Range by Samuel Butler.txt 491146 521 Memoirs Of Fanny Hill by John Cleland.txt 493683 522 A Concise Chronicle of Events of the Great War by R. P. P. Rowe.txt 493710 523 Meine Lebens-Erinnerungen - Band 2 (of 4) by Adam Gottlob Oehlenschläger.txt 494426 524 Spanish America, Its Romance, Reality and Future, Vol. 2 (of 2) by Enock.txt 494848 525 After London; Or, Wild England by Richard Jefferies.txt 495456 526 Aeneidos by Virgil.txt 495752 527 Household Stories by the Brothers Grimm by Jacob Grimm and Wilhelm Grimm.txt 496237 528 The Prairie Traveler by Randolph Barnes Marcy.txt 496765 529 Lucrecia Borja, by Wenceslao Ramírez de Villa-Urrutia.txt 497432 530 Elementary Composition by Dorothea F. Canfield and George R. Carpenter.txt 501118 531 Wieland; Or, The Transformation An American Tale by Charles Brockden Brown.txt 501311 532 Obras Completas de Luis de Camões, Tomo III by Luís de Camões.txt 501612 533 Leon Roch (vol. 1 of 2) by Benito Pérez Galdós.txt 501761 534 Le portrait de Dorian Gray by Oscar Wilde.txt 501929 535 Barracks, Bivouacs and Battles by Archibald Forbes.txt 502870 536 Mollie's Substitute Husband by Max McConn.txt 503892 537 The Irish Fairy Book by Alfred Perceval Graves and George Denham.txt 504135 538 A Text-Book of the History of Painting by John Charles Van Dyke.txt 504632 539 The Phantom of the Opera by Gaston Leroux.txt 504761 540 Spenser's The Faerie Queene, Book I by Edmund Spenser.txt 505585 541 Jumalat janoavat, by Anatole France.txt 506400 542 Paradise Lost by John Milton.txt 507105 543 Howard Pyle's Book of Pirates by Howard Pyle.txt 508911 544 Tarzan of the Apes by Edgar Rice Burroughs.txt 511788 545 Studien und Plaudereien im Vaterland. Second Series by Stern and Stern.txt 512540 92 546 The Oera Linda Book by J. G. Ottema and William R. Sandbach.txt 513878 547 The Ladies Book of Useful Information by Anonymous.txt 513907 548 The Scarlet Pimpernel by Baroness Emmuska Orczy Orczy.txt 514335 549 Meine Lebens-Erinnerungen - Vierter Band (of 4) by Adam Gottlob Oehlenschläger.txt 515050 550 The Scarlet Letter by Nathaniel Hawthorne.txt 516422 551 The Advancement of Learning by Francis Bacon.txt 516904 552 A Journey to the Centre of the Earth by Jules Verne.txt 517652 553 The Ladies' Book of Etiquette, and Manual of Politeness by Florence Hartley.txt 520612 554 Storia d'Italia dal 1789 al 1814, tomo II by Carlo Botta.txt 520615 555 The Romaunce of The Sowdone of Babylone and of Ferumbras his Sone who conquerede.txt 522281 556 Les Misérables, v. 3-5, by Victor Hugo.txt 523539 557 he Mystery of the Ravenspurs, by Fred M. White.txt 527172 558 By Blow and Kiss by Boyd Cable.txt 528668 559 Sentimental Education; Or, The History of a Young Man. Volume 1 by Gustave Flaubert.txt 529057 560 Germany before the war by baron Beyens.txt 530141 561 Meine Lebens-Erinnerungen - Band 1 (of 4) by Adam Gottlob Oehlenschläger.txt 531037 562 Outlines of Creation, by Elisha Noyce.txt 532501 563 A Vindication of the Rights of Woman by Mary Wollstonecraft.txt 533221 564 The Project Gutenberg EBook of Boots and Saddles, by Elizabeth Custer.txt 533254 565 The Olive Fairy Book by Andrew Lang and H. J. Ford.txt 533419 566 The Gentlemen's Book of Etiquette and Manual of Politeness by Cecil B. Hartley.txt 535045 567 The Quest of Glory by Marjorie Bowen.txt 535253 568 Human, All-Too-Human A Book For Free Spirits; Part II by Nietzsche.txt 537283 569 The Crimson Fairy Book by Andrew Lang.txt 537521 570 Mark Twain's Speeches by Mark Twain.txt 538872 571 he Scientific Tourist through Ireland by Thomas Walford.txt 539777 572 The Pink Fairy Book by Andrew Lang.txt 541478 573 The Wiving of Lance Cleaverage, by Alice MacGowan.txt 543120 574 Sport in the Crimea and Caucasus by Clive Phillipps-Wolley.txt 543558 575 A Book of Myths by Jeanie Lang.txt 545487 576 The Shogun's Daughter by Robert Ames Bennet.txt 550314 577 The Sixty-First Second by Owen Johnson.txt 553233 578 The Heart of the Red Firs by Ada Woodruff Anderson.txt 554570 579 The Son of Tarzan by Edgar Rice Burroughs.txt 554747 580 Greenmantle by John Buchan.txt 555158 581 Chap-books of the Eighteenth Century by John Ashton.txt 555730 582 Reminiscences of the King of Roumania by Mite Kremnitz.txt 555918 583 Tarzan the Terrible by Edgar Rice Burroughs.txt 558155 584 The Further Adventures of Robinson Crusoe by Daniel Defoe.txt 558554 585 Näkymättömiä siteitä by Selma Lagerlöf.txt 559489 586 The Chinese Fairy Book by Richard Wilhelm.txt 560537 587 A Voyage to Arcturus by David Lindsay.txt 560657 588 A Book of Remarkable Criminals by H. B. Irving.txt 561155 93 589 British and Foreign Arms and Armour by Charles Henry Ashdown.txt 563130 590 The Violet Fairy Book by Andrew Lang.txt 564227 591 History of the Wars, Books I and II by Procopius.txt 564961 592 The travels of Pedro de Cieza de Léon; part 2 by Pedro de Cieza de León.txt 566128 593 Five Weeks in a Balloon by Jules Verne.txt 566844 594 Homo sum by Georg Ebers.txt 569238 595 The Invasions of England, by Edward Foord and Gordon Home.txt 569708 596 Summer Provinces by the Sea by Intercontinental Railway.txt 571085 597 Boys and Girls Bookshelf; a Practical Plan of Character Building, Volume I (of.txt 571434 598 Modern Prose And Poetry; For Secondary Schools by Margaret Ashmun.txt 571814 599 The Writings of Thomas Paine — Volume 2 (1779-1792) The Rights of Man by Paine.txt 572290 600 Famous Frontiersmen and Heroes of the Border, by.txt 574541 601 Les Misérables, v. 2-5 by Victor Hugo.txt 575480 602 Historia de la literatura y del arte dramático en España, tomo V by Schack.txt 575821 603 The Green God's Pavilion, by Mabel Wood Martin.txt 579209 604 Kirkonlämmittäjä by Arvi Järventaus.txt 579343 605 From the Earth to the Moon; and, Round the Moon by Jules Verne.txt 580159 606 Beeton's Book of Needlework by Mrs. Beeton.txt 580361 607 Pioneers in Australasia by Sir Harry Hamilton Johnston.txt 580495 608 I primi due secoli della storia di Firenze,.txt 582626 609 Storia d'Italia dal 1789 al 1814, tomo III by Carlo Botta.txt 582708 610 My Life at Sea by W. Caius Crutchley.txt 582785 611 Storia delle repubbliche italiane dei secoli di mezzo, Tomo IV (of 16) by Sismondi.txt 585450 612 L'idolo by Gerolamo Rovetta.txt 585536 613 The Viper of Milan, by Marjorie Bowen.txt 586446 614 The World's Greatest Books — Volume 15 — Science by Hammerton and Mee.txt 587024 615 Jacques le fataliste et son maître by Denis Diderot.txt 589396 616 A Dictionary of Slang, Cant, and Vulgar Words by A London Antiquary.txt 589705 617 Dio's Rome, Volume 5, Books 61-76 (A.D. 54-211) by Cassius Dio Cocceianus.txt 590082 618 Storia d'Italia dal 1789 al 1814, tomo V by Carlo Botta.txt 593302 619 Phases of Irish History, by Eoin MacNeill.txt 594607 620 The adventures of Sherlock Holmes.txt 594933 621 Storia delle repubbliche italiane dei secoli di mezzo, Tomo I by Sismondi.txt 596146 622 The Satyricon — Complete by Petronius Arbiter.txt 597347 623 Father Goriot by Honoré de Balzac.txt 601940 624 A Servant of the Public by Anthony Hope.txt 603561 625 Japanese Literature by Epiphanius Wilson.txt 604814 626 Kerjäläissoturit by J. B. de Liefde.txt 604845 627 Storia delle repubbliche italiane dei secoli di mezzo, Tomo V (of 16) by Sismondi.txt 604940 628 McGuffey's Fifth Eclectic Reader by William Holmes McGuffey.txt 605267 629 Storia d'Italia dal 1789 al 1814, tomo VI by Carlo Botta.txt 605415 630 Allan Quatermain by H. Rider Haggard.txt 605624 631 Sixty Folk-Tales from Exclusively Slavonic Sources by Various.txt 609749 94 632 Adventures of Huckleberry Finn by Mark Twain.txt 610155 633 The Life and Letters of Lewis Carroll (Rev. C. L. Dodgson) by Collingwood.txt 611581 634 Gulliver's Travels into Several Remote Nations of the World by Jonathan Swift.txt 611864 635 The Age of Innocence by Edith Wharton.txt 612314 636 The Youngest Sister, by Bessie Marchant.txt 612415 637 The Ten Books on Architecture by Vitruvius Pollio.txt 612734 638 Kim by Rudyard Kipling.txt 615539 639 The Little Demon, by Feodor Sologub.txt 615687 640 The Yellow Fairy Book by Andrew Lang.txt 615930 641 The Present State of Hayti (Saint Domingo).txt 617261 642 La Divina Commedia di Dante by Dante Alighieri.txt 618423 643 Lucy Maud Montgomery Short Stories, 1909 to 1922 by L. M. Montgomery.txt 619468 644 The British Navy Book by Cyril Field.txt 621791 645 Campaigning in Kaffirland by W. R. King.txt 621834 646 The Literary World Seventh Reader by Browne, Metcalf, and Withers.txt 622031 647 A Study of Siouan Cults by James Owen Dorsey.txt 623310 648 The World's Greatest Books — Volume 08 — Fiction by Hammerton and Mee.txt 623805 649 A History of the Durham Miner's Association.txt 625591 650 The Works of Aristotle the Famous Philosopher by Aristotle.txt 633117 651 The World's Greatest Books — Volume 03 — Fiction by Hammerton and Mee.txt 633909 652 Tarzan the Untamed by Edgar Rice Burroughs.txt 636054 653 True Stories of The Great War Volume 2 (of 6), by Various.txt 636582 654 United States Steel by Arundel Cotter.txt 639031 655 Der Nibelunge liet, by Anonymous.txt 639234 656 The Divine Comedy by Dante, Illustrated by Dante Alighieri.txt 641414 657 Salammbo by Gustave Flaubert.txt 641681 658 Della scienza militare by Luigi Blanch.txt 643018 659 Racconti politici by Antonio Ghislanzoni.txt 643050 660 Les Misérables, v. 5-5 by Victor Hugo.txt 643257 661 Storia d'Italia dal 1789 al 1814, tomo I by Carlo Botta.txt 643546 662 Les Misérables, v. 1-5 by Victor Hugo.txt 643876 663 She by H. Rider Haggard.txt 644165 664 The House of the Seven Gables by Nathaniel Hawthorne.txt 646211 665 True Stories of The Great War, Volume 1 (of 6) by Various.txt 650303 666 The World's Greatest Books — Volume 02 — Fiction by Hammerton and Mee.txt 651033 667 Index Expurgatorius Anglicanus by W. H. Hart.txt 651047 668 Historia de la literatura y del arte dramático en España, tomo III by Schack.txt 656326 669 Fact and Fable in Psychology, by Joseph Jastrow.txt 656716 670 Ayesha, the Return of She by H. Rider Haggard.txt 658694 671 The World's Greatest Books — Volume 09 — Lives and Letters by Hammerton and Mee.txt 658719 672 Il Vino, by Various.txt 659505 673 The World's Greatest Books — Volume 01 — Fiction by Hammerton and Mee.txt 662420 674 Elias Lönnrots svenska skrifter by Elias Lönnrot.txt 663145 95 675 Pascal's Pensées by Blaise Pascal.txt 663171 676 Der Klosterjaeger by Ludwig Ganghofer.txt 663721 677 The Green Fairy Book by Andrew Lang.txt 668028 678 The Aeneid by Virgil.txt 668070 679 Storia delle repubbliche italiane dei secoli di mezzo, Tomo II by Sismondi.txt 671223 680 Historia de la literatura y del arte dramático en España, tomo IV by Schack.txt 671467 681 Storia d'Italia dal 1789 al 1814, tomo IV by Carlo Botta.txt 672207 682 Spinster of This Parish by W. B. Maxwell.txt 673608 683 Thus Spake Zarathustra A Book for All and None by Friedrich Wilhelm Nietzsche.txt 674700 684 Captain Blood by Rafael Sabatini.txt 675125 685 Storia delle repubbliche italiane dei secoli di mezzo, Tomo III (of 16) by Sismondi.txt 675128 686 The Blue Book of Chess by Howard Staunton.txt 679654 687 Wuthering Heights by Emily Brontë.txt 681641 688 Fauna der Nassauischen Mollusken, by Wilhelm Kobelt.txt 682251 689 The Book of the Damned by Charles Fort.txt 682616 690 Tales and Novels of J. de La Fontaine — Complete by Jean de La Fontaine.txt 682719 691 Madame Bovary by Gustave Flaubert.txt 685247 692 The Red Fairy Book by Andrew Lang.txt 686155 693 The World's Greatest Books — Volume 13 — Religion and Philosophy by Hammerton et al..txt 689617 694 Descripción Geografica, Histórica y Estadística de Bolivia, Tomo 1. by Orbigny.txt 690409 695 Petrarch, by James Harvey Robinson.txt 694892 696 The Sea-Hawk by Rafael Sabatini.txt 696240 697 Studies in the Psychology of Sex, Volume 4 by Havelock Ellis.txt 698107 698 The Story of the Champions of the Round Table by Howard Pyle.txt 703528 699 The Home Book of Verse — Volume 1 by Burton Egbert Stevenson.txt 706620 700 Bacteria by George A. Newman.txt 708819 701 Kruunu ja okaita, by Henrik af Trolle.txt 709363 702 Mr. Standfast by John Buchan.txt 713262 703 Pride and Prejudice by Jane Austen.txt 717575 704 The Man That Corrupted Hadleyburg, and Other Stories by Mark Twain.txt 720088 705 Studies in Judaism, First Series by Solomon.txt 721078 706 El Dorado An Adventure of the Scarlet Pimpernel by Baroness Emmuska Orczy Orczy.txt 723773 707 Barry Lyndon by William Makepeace Thackeray.txt 724677 708 EBook of OEuvres complètes de Gustave Flaubert,.txt 726753 709 The Odyssey by Homer.txt 730117 710 Philochristus by Edwin A. Abbott.txt 734029 711 Curiosities of Science, Past and Present by John Timbs.txt 734213 712 Short Stories for English Courses by Rosa Mary Redding Mikels.txt 738861 713 An Essay Concerning Human Understanding, Volume 2 by John Locke.txt 739471 714 Monsieur Lecoq, v. 2 by Emile Gaboriau.txt 739815 715 Lord Jim by Joseph Conrad.txt 740753 716 Scaramouche A Romance of the French Revolution by Rafael Sabatini.txt 741983 717 Les Misérables, v. 4-5 by Victor Hugo.txt 747734 96 718 Light-Fingered Gentry by David Graham Phillips.txt 748933 719 A Bibliographical, Antiquarian and Picturesque Tour in France and Germany,.txt 750819 720 The Book of Buried Treasure by Ralph Delahaye Paine.txt 751643 721 The suppressed Gospels and Epistles of the original New Testament of Jesus the.txt 757076 722 Historia General del Derecho Español, Tomo I by Eduardo de Hinojosa.txt 761142 723 The Blue Fairy Book by Andrew Lang.txt 763809 724 Esprit des lois by baron de Charles de Secondat Montesquieu.txt 767661 725 Psychological Warfare by Paul M. A. Linebarger.txt 771435 726 Leaves of Grass by Walt Whitman.txt 775617 727 The Sketch-Book of Geoffrey Crayon by Washington Irving.txt 777500 728 1914 by Earl of Ypres John Denton Pinkstone French.txt 780413 729 The Metamorphoses of Ovid, Books I-VII by Ovid.txt 780619 730 Studies in the Psychology of Sex, Volume 5 by Havelock Ellis.txt 783552 731 The Decameron, Volume I by Giovanni Boccaccio.txt 784469 732 Sea-gift by Edwin Wiley Fuller.txt 784903 733 The story of Burnt Njal From the Icelandic of the Njals Saga by Dasent.txt 786602 734 Frau Bovary by Gustave Flaubert.txt 786960 735 Tono-Bungay by H. G. Wells.txt 787856 736 A Half-Century of Conflict, Vol II by Francis Parkman.txt 796120 737 Comprising The Book of good counsels, Nala and Damayanti, The.txt 796873 738 Gloria (novela completa), by Benito Pérez Galdós.txt 806488 739 The Book of the Thousand Nights and One Night, Volume I by John Paynetxt.txt 809606 740 The Pirates Own Book by Charles Ellms.txt 820669 741 The Family among the Australian Aborigines, by.txt 822926 742 The Book-Hunter by John Hill Burton.txt 825173 743 The Monk A Romance by M. G. Lewis.txt 827539 744 The Black Diamond by Francis Brett Young.txt 827873 745 The Early Norman Castles of the British Isles. by Ella S. Armitage.txt 828338 746 The Oxford Book of Latin Verse by Various.txt 829839 747 A Text-Book of the History of Architecture by A. D. F. Hamlin.txt 834514 748 Compendio di psicologia by Wilhelm Max Wundt.txt 834975 749 McGuffey's Sixth Eclectic Reader by William Holmes McGuffey.txt 841511 750 Jude the Obscure by Thomas Hardy.txt 841916 751 The Jungle by Upton Sinclair.txt 843093 752 Dead Souls by Nikolai Vasilevich Gogol.txt 844630 753 Philosophiae Naturalis Principia Mathematica by Sir Isaac Newton.txt 851734 754 We and Our Neighbors by Harriet Beecher Stowe.txt 852646 755 The Metamorphoses of Ovid, Books VIII-XV by Ovid.txt 853980 756 Roman Legends by R. H. Busk.txt 855629 757 The Hungry Heart by David Graham Phillips.txt 856419 758 The Story of the Three Little Pigs by L. Leslie Brooke.txt 871077 759 The Fortunate Mistress (Parts 1 and 2) by Daniel Defoe.txt 872410 760 Historia de Venezuela, Tomo II by Pedro de Aguado.txt 873891 97 761 Deuterocanonical Books of the Bible by Anonymous.txt 874792 762 Legends of the Patriarchs and Prophets by S. Baring-Gould.txt 875130 763 Tess of the d'Urbervilles; A Pure Woman by Thomas Hardy.txt 875359 764 A Brief History of Forestry., by Bernhard E. Fernow.txt 877429 765 Dracula by Bram Stoker.txt 883156 766 The Expedition of Humphry Clinker by T. Smollett.txt 883577 767 Twenty Thousand Leagues Under the Seas An Underwater Tour of the World by Verne.txt 885151 768 With the Flag to Pretoria by H.W. Wilson.txt 887017 769 The History of the 36th (Ulster) Division by Cyril Falls.txt 894530 770 The Tragedies of Euripides, Volume I. by Euripides.txt 896167 771 The Book Lovers' Anthology by Various.txt 896328 772 Cole's Funny Picture Book No. 1 by E. W. Cole.txt 904780 773 La familia de León Roch by Benito Pérez Galdós.txt 906449 774 Studies in the Psychology of Sex, Volume 1 by Havelock Ellis.txt 907501 775 Literary and Philosophical Essays French, German and Italian by Immanuel Kant et al..txt 907930 776 Della guerra nazionale d'insurrezione per bande, applicata all'Italia by Jorioz.txt 911491 777 The Decameron, Volume II by Giovanni Boccaccio.txt 918091 778 Sister Carrie by Theodore Dreiser.txt 919371 779 Sons and Lovers by D. H. Lawrence.txt 923093 780 Endres Tuchers Baumeisterbuch der Stadt Nürnberg by Matthias Lexer.txt 926670 781 Common Sense in the Household by Marion Harland.txt 928412 782 Nana by Émile Zola.txt 933007 783 Big Game Shooting, volume 1 (of 2) by Clive Phillipps-Wolley.txt 934052 784 The Danish History, Books I-IX by Grammaticus Saxo.txt 939731 785 Histoire de la peinture en Italie, by Henri Beyle.txt 939977 786 Lion and Dragon in Northern China by Reginald Fleming Johnston.txt 963535 787 Chapters on the History of the Southern.txt 969848 788 On the Origin of Species By Means of Natural Selection by Charles Darwin.txt 970783 789 The Oxford Book of American Essays by W. C. Brownell et al..txt 973203 790 Studies in the Psychology of Sex, Volume 3 by Havelock Ellis.txt 979756 791 Suomen kansan muinaisia loitsurunoja by Elias Lönnrot.txt 982859 792 The Book of the Thousand Nights and a Night — Volume 01 by Burton.txt 986877 793 The Naval War of 1812 by Theodore Roosevelt.txt 986879 794 Hazlitt on English Literature An Introduction to the Appreciation of Literature.txt 995920 795 The Provinces of the Roman Empire, v. 1, by.txt 996562 796 The Emancipation of South America, by Bartolomé Mitre.txt 998876 797 Louise de la Valliere by Alexandre Dumas.txt 1001551 798 Nostromo A Tale of the Seaboard by Joseph Conrad.txt 1004634 799 Putnam's Word Book by Louis A. Flemming.txt 1005084 800 The Poems of John Donne [2 vols.] Volume I by John Donne.txt 1026633 801 The Wonder Book of Knowledge by Various.txt 1029482 802 Great Expectations by Charles Dickens.txt 1033768 803 Commentaries on the Laws of England, Book the First by Sir William Blackstone.txt 1036050 98 804 The Man in the Iron Mask by Alexandre Dumas.txt 1036593 805 Prefaces and Prologues to Famous Books by Francis Bacon et al..txt 1036620 806 Orlando Furioso, Tomo I. by Lodovico Ariosto.txt 1043961 807 Uncle Tom's Cabin by Harriet Beecher Stowe.txt 1046640 808 Hung Lou Meng, or, the Dream of the Red Chamber, a Chinese Novel, Book I by Cao.txt 1065961 809 Studies in the Psychology of Sex, Volume 2 by Havelock Ellis.txt 1066709 810 Women in Love by D. H. Lawrence.txt 1066987 811 Analectabiblion, Tome 2 (of 2) by Auguste François Louis Du Roure.txt 1068730 812 The Life and Opinions of Tristram Shandy, Gentleman by Laurence Sterne.txt 1070197 813 The Works of the Emperor Julian, Vol. 1 by Emperor of Rome Julian.txt 1073156 814 The Rainbow by D. H. Lawrence.txt 1074448 815 The Poems of John Donne, Volume II (of 2) by John Donne.txt 1075359 816 Le Rouge et le noir chronique du XIXe siècle by Stendhal.txt 1075974 817 Cassell's Book of Birds, Volume 1 by Alfred Edmund Brehm.txt 1098603 818 Notre-Dame De Paris by Victor Hugo.txt 1101753 819 Le parler populaire des Canadiens français by Narcisse Eutrope Dionne.txt 1102344 820 The Adventures of Roderick Random by T. Smollett.txt 1110812 821 Ten Years Later by Alexandre Dumas.txt 1122565 822 Chroniques de J. Froissart, Tome Premier, 2ème partie. (1307-1340) by Froissart.txt 1125277 823 The travels of Pedro de Cieza de Léon, A.D. 1532-50, by Pedro de Cieza de León.txt 1129105 824 Oeuvres de P. Corneille, Tome 06 by Pierre Corneille.txt 1134559 825 he Odysseys of Homer, by Homer.txt 1137521 826 Ben-Hur; a tale of the Christ by Lew Wallace.txt 1145129 827 La Chartreuse De Parme by Stendhal.txt 1146978 828 Analectabiblion, Tome 1 (of 2) by Auguste François Louis Du Roure.txt 1147477 829 The Jargon File, Version 2.9.10, 01 Jul 1992 by Eric S. Raymond and Guy L. Steele.txt 1147783 830 Ivanhoe A Romance by Walter Scott.txt 1147962 831 Nigelin vaiheet by Walter Scott.txt 1150147 832 The Project Gutenberg EBook of Travels in Brazil, by Henry Koster.txt 1166229 833 The History of Don Quixote, Volume 2, Complete by Miguel de Cervantes Saavedra.txt 1168472 834 Crime and Punishment by Fyodor Dostoyevsky.txt 1177123 835 Historia de Venezuela, Tomo I by Pedro de Aguado.txt 1183271 836 Die Reden Gotamo Buddhos, by Karl Eugen Neumann.txt 1186496 837 Project Gutenberg's Mythology among the Hebrews, by Ignaz Goldziher.txt 1187902 838 Pamela, or Virtue Rewarded by Samuel Richardson.txt 1189721 839 Handbuch der deutschen Kunstdenkmäler, Bd.1, Mitteldeutschland, 1914 by Georg Dehio.txt 1193165 840 Adam Bede by George Eliot.txt 1195615 841 The History of Don Quixote, Volume 1, Complete by Miguel de Cervantes Saavedra.txt 1200139 842 Quo Vadis A Narrative of the Time of Nero by Henryk Sienkiewicz.txt 1205686 843 Life of Napoleon Bonaparte, Volume I. by Walter Scott.txt 1219488 844 Life of Napoleon Bonaparte, Volume IV. by Walter Scott.txt 1231620 845 Quer Durch Borneo by Anton Willem Nieuwenhuis.txt 1238923 846 A Concise Dictionary of Middle English from A.D. 1150 to 1580 by Mayhew and Skeat.txt 1248077 99 847 Moby Dick; Or, The Whale by Herman Melville.txt 1257295 848 The Vedanta-Sutras with the Commentary by Sankaracarya by Sankaracarya and Thibaut.txt 1261074 849 Diccionario Ingles-Español-Tagalog by Sofronio G. Calderón.txt 1270587 850 The History of the Most Noble Order of the Garter by Unknown.txt 1270775 851 Kritik der reinen Vernunft by Immanuel Kant.txt 1273587 852 ife of Napoleon Bonaparte, Volume III. by Walter Scott.txt 1295853 853 The Complete Plays of Gilbert and Sullivan by W. S. Gilbert and Arthur Sullivan.txt 1295961 854 The Bible in Spain by George Borrow.txt 1296888 855 The History of Rome, Books 09 to 26 by Livy.txt 1307350 856 The Jargon File, Version 4.0.0, 24 Jul 1996 by Eric S. Raymond and Guy L. Steele.txt 1317743 857 The History of Don Quixote de la Mancha by Miguel de Cervantes Saavedra.txt 1321209 858 Life of Napoleon Bonaparte, Volume V. by Walter Scott.txt 1321273 859 Showell's Dictionary of Birmingham by Thomas T. Harman and Walter Showell.txt 1329007 860 Life of Napoleon Bonaparte, Volume II. by Walter Scott.txt 1350465 861 The Three Musketeers by Alexandre Dumas.txt 1354240 862 Character Sketches of Romance, Fiction and the Drama, Vol. 1 by Brewer.txt 1355897 863 The Boy Mechanic Volume 1 by Popular Mechanics Company.txt 1356667 864 Herra Oblomov by I. A. Gontsharov.txt 1365018 865 The History of Rome, Books 01 to 08 by Livy.txt 1392266 866 Character Sketches of Romance, Fiction and the Drama by Ebenezer Cobham Brewer.txt 1396116 867 The Idiot by Fyodor Dostoyevsky.txt 1396972 868 Early English Meals and Manners by Frederick James Furnivall.txt 1401166 869 Emile by Jean-Jacques Rousseau.txt 1411086 870 The Standard Electrical Dictionary by T. O'Conor Sloane.txt 1412442 871 The Lake-Dwellings of Europe by Robert Munroe.txt 1417848 872 Experimental Researches in Electricity, Volume 1 by Michael Faraday.txt 1428411 873 Twenty Years After by Alexandre Dumas.txt 1429309 874 Bible Animals; by J. G. Wood.txt 1449315 875 The Browning Cyclopædia A Guide to the Study of the Works of Robert Browning.txt 1464728 876 The Possessed (The Devils) by Fyodor Dostoyevsky.txt 1482966 877 Chaucer's Works, Volume 4 (of 7) — The Canterbury Tales by Geoffrey Chaucer.txt 1494373 878 A Short Biographical Dictionary of English Literature by John W. Cousin.txt 1500393 879 Principles Of Political Economy by John Stuart Mill.txt 1514112 880 Ada, the Betrayed, by John Malcolm Rymer.txt 1529557 881 Devonshire Characters and Strange Events by S. Baring-Gould.txt 1545669 882 Webster's Unabridged Dictionary (1st 100 Pages) by Noah Webster.txt 1552718 883 Bible Readings for the Home Circle.txt 1553717 884 Ulysses by James Joyce.txt 1573151 885 Fox's Book of Martyrs by John Foxe.txt 1581101 886 The Book of Mormon by Church of Jesus Christ of Latter-day Saints and Smith.txt 1595452 887 Buddenbrooks Verfall einer Familie by Thomas Mann.txt 1602177 888 The Complete Opera Book by Gustav Kobbé.txt 1632173 889 An Etymological Dictionary of the Scottish Language by John Jamieson.txt 1640010 100 890 A System of Pyrotechny by James Cutbush.txt 1653583 891 The Makers of Canada Index and Dictionary of Canadian History by Burpee et al..txt 1680643 892 De Aarde en haar Volken, Jaargang 1877 by Various.txt 1697280 893 The Canterbury Tales, and Other Poems by Geoffrey Chaucer.txt 1702167 894 The Genius by Theodore Dreiser.txt 1735466 895 Amenities of Literature by Isaac Disraeli.txt 1742932 896 The Decameron of Giovanni Boccaccio by Giovanni Boccaccio.txt 1750786 897 The Pickwick Papers by Charles Dickens.txt 1798172 898 Middlemarch by George Eliot.txt 1847696 899 The Cook and Housekeeper's Complete and Universal Dictionary; Including a System.txt 1882403 900 Gargantua and Pantagruel by François Rabelais.txt 1884034 901 A Concise Anglo-Saxon Dictionary by J. R. Clark Hall.txt 1928283 902 Martin Chuzzlewit by Charles Dickens.txt 1937505 903 Essais de Montaigne (self-edition) by Michel de Montaigne.txt 1941536 904 CIA FactBook 1990.txt 1970956 905 The Brothers Karamazov by Fyodor Dostoyevsky.txt 1996603 906 History of Tom Jones, a Foundling by Henry Fielding.txt 2016201 907 The Sailor's Word-Book by W. H. Smyth.txt 2037021 908 Anna Karenina by graf Leo Tolstoy.txt 2041122 909 Le Morte Darthur by Sir Thomas Malory.txt 2136831 910 Don Quijote by Miguel de Cervantes Saavedra.txt 2198927 911 A Dictionary of English Synonymes and Synonymous or Parallel Expressions by Soule.txt 2234887 912 CIA FactBook 1991.txt 2237079 913 An Inquiry into the Nature and Causes of the Wealth of Nations by Adam Smith.txt 2276935 914 Don Quixote by Miguel de Cervantes Saavedra.txt 2347796 915 The Jargon File, Version 4.2.2, 20 Aug 2000 by Eric S. Raymond and Guy L. Steele.txt 2474769 916 CIA FactBook 1992.txt 2482190 917 A System Of Logic, Ratiocinative And Inductive by John Stuart Mill.txt 2514451 918 CIA FactBook 1993.txt 2648285 919 The Count of Monte Cristo, Illustrated by Alexandre Dumas.txt 2685979 920 The Bible Story by Newton Marshall Hall and Irving Francis Wood.txt 2773517 921 CIA FactBook 1994.txt 2827563 922 CIA FactBook 1996.txt 2927448 923 Memoirs of Napoleon Bonaparte — Complete by Louis Antoine Fauvelet de Bourrienne.txt 2944159 924 The Catholic World, Volume 15, Nos. 85-90, April 1872-September 1872 by Various.txt 2987554 925 CIA FactBook 1995.txt 3013173 926 Catholic World, Vol. 14, October 1871-March.txt 3031048 927 Essays of Michel de Montaigne — Complete by Michel de Montaigne.txt 3085821 928 CIA FactBook 1997.txt 3099637 929 The Book of Household Management by Mrs. Beeton.txt 3117383 930 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg and Noah Webster.txt 3138754 931 War and Peace by graf Leo Tolstoy.txt 3291648 932 Les Misérables by Victor Hugo.txt 3322651 101 933 CIA FactBook 1999.txt 3453580 934 Austral English by Edward Ellis Morris.txt 3467733 935 CIA FactBook 1998.txt 3475998 936 CIA FactBook 2000.txt 3501173 937 Woordenboek der Grieksche en Romeinsche oudheid by Boer and Schlimmer.txt 3685826 938 The Mahabharata of Krishna-Dwaipayana Vyasa, Volume 1 by Kisari Mohan Ganguli.txt 3752814 939 CIA FactBook 2002.txt 3859601 940 Dictionary of Quotations from Ancient and Modern, English and Foreign Sources.txt 4069112 941 Encyclopaedia Britannica, 11th Edition, Capefigue to Carneades by Various.txt 4293873 942 Encyclopaedia Britannica, 11th Edition, Calhoun to Camoens by Various.txt 4393731 943 Encyclopaedia Britannica, 11th Edition, Bedlam to Benson, George by Various.txt 4398666 944 Encyclopaedia Britannica, 11th Edition, Apollodorus to Aral by Various.txt 4638548 945 Encyclopaedia Britannica, 11th Edition, Aram, Eugene to Arcueil by Various.txt 4685892 946 Encyclopaedia Britannica, 11th Edition, Bent, James to Bibirine by Various.txt 4725659 947 Encyclopaedia Britannica, 11th Edition, Bradford, William to Brequigny,.txt 4793389 948 Encyclopaedia Britannica, 11th Edition, Armour Plates to Arundel, Earls of.txt 4793864 949 Encyclopaedia Britannica, 11th Edition, Arculf to Armour, Philip by Various.txt 4878585 950 The Nuttall Encyclopædia by P. Austin Nuttall.txt 4932076 951 Encyclopaedia Britannica, 11th Edition, Atherstone to Austria by Various.txt 5013798 952 Encyclopaedia Britannica, 11th Edition, Arundel, Thomas to Athens by Various.txt 5249126 953 Encyclopaedia Britannica, 11th Edition, Bisharin to Bohea by Various.txt 5530823 954 Encyclopaedia Britannica, 11th Edition, Bohemia to Borgia, Francis by Various.txt 5572147 955 Encyclopaedia Britannica, 11th Edition, Basso-relievo to Bedfordshire.txt 5632362 956 Encyclopaedia Britannica, 11th Edition, Celtes, Konrad to Ceramics by Various.txt 5646815 957 The Bible, Douay-Rheims, 2010.txt 5649265 958 Encyclopaedia Britannica, 11th Edition, Anjar to Apollo by Various.txt 5664000 959 Encyclopaedia Britannica, 11th Edition, Carnegie Andrew to Casus Belli.txt 5703102 960 Encyclopaedia Britannica, 11th Edition, Châtelet to Chicago by Various.txt 5756908 961 Encyclopaedia Britannica, 11th Edition, Camorra to Cape Colony by Various.txt 5803867 962 Encyclopaedia Britannica, 11th Edition, Austria, Lower to Bacon by Various.txt 5847149 963 The Bible, Douay-Rheims, Complete.txt 5918239 964 Encyclopaedia Britannica, 11th Edition, Chariot to Chatelaine by Various.txt 6027482 965 The Circle of Knowledge by Various.txt 6139867 966 Encyclopaedia Britannica, 11th Edition, Baconthorpe to Bankruptcy by Various.txt 6372617 967 Encyclopaedia Britannica, 11th Edition, Borgia, Lucrezia to Bradford, John.txt 6529985 968 Encyclopaedia Britannica, 11th Edition, Cerargyrite to Charing Cross by Various.txt 6551750 969 A Dictionary of Arts, Manufactures and Mines by Andrew Ure.txt 6699599 970 The Memoirs of Jacques Casanova de Seingalt, 1725-1798. Complete by Casanova.txt 6842537 971 Encyclopaedia Britannica, 11th Edition, Bible to Bisectrix by Various.txt 6877023 972 CIA FactBook 2001.txt 7195004 973 Meyers Konversationslexikon Band 15 by Various .txt 7342653 974 Encyclopaedia Britannica, 11th Edition, Cat to Celt by Various.txt 7503122 975 Encyclopaedia Britannica, 11th Edition, Bréquigny, Louis Georges Oudard Feudrix.txt 7773179 102 976 The Works of the Emperor Julian, Vol. 2 by Emperor of Rome Julian.txt 7792138 977 CIA FactBook 2003.txt 8049730 978 The Project Gutenberg Encyclopedia by Project Gutenberg 2004.txt 8312587 979 CIA FactBook 2004.txt 8415174 980 Encyclopaedia Britannica, 11th Edition, Bulgaria to Calgary by Various.txt 8449089 981 CIA FactBook 2005.txt 8663711 982 CIA FactBook 2006.txt 9201334 983 CIA FactBook 2007.txt 9206424 984 CIA FactBook 2008.txt 10031328 985 CIA FactBook 2009.txt 12980247 986 CIA FactBook 2010.txt 13516870 987 Novo dicionário da língua portuguesa by Cândido de Figueiredo.txt 13640046 988 Webster's Unabridged Dictionary 1913 edition.txt 28956348 989 Chambers's Twentieth Century Dictionary (part 2 of 4 E-M) by Thomas Davidson.txt 29315009 990 Chambers's Twentieth Century Dictionary (part 3 of 4 N-R) by Thomas Davidson.txt 33194019 991 Chambers's Twentieth Century Dictionary (part 4 of 4 S-Z and supplements).txt 34637668 992 Chambers's Twentieth Century Dictionary part 1 of 4 A-D by Thomas Davidson.txt 36652182 993 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 1997.txt 45748820 994 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 1996.txt 45769833 995 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 1998.txt 46198119 996 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 1999.txt 46415985 997 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 2000.txt 46529668 998 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 2001.txt 46772304 999 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 2002.txt 48820788 1000 The Gutenberg Webster's Unabridged Dictionary by Project Gutenberg 2003.txt 49825626 103 ANEXO B: Implementaciones Realizadas Para las implementaciones de los procesos de encriptación y desencriptación se utilizó el lenguaje de programación C++ en su estándar 2011, en el entorno de programación de Visual Studio 2013, para la implementación en GPU con CUDA se utilizó la versión CUDA 7, para la implementación en múltiple CPU se utilizó la librería de Intel Threding Building Blocks en su versión 4.5.6, las implementaciones se muestran a continuación: 1. Implementación en CPU con un solo núcleo: ////////////////////////////////////////////////////////////////////////// // Nombre de Función: potenciaModular. // Párametros de función: // - a : Entrada, Base de la operación // - b : Entrada, Exponente // - c : Entrada, Modulo // Funcionalidad: Eleva a la potencia b el número a y luego // le saca modulo de c (Se usa para poder manejar números grandes) // Valor de retorno: (a^b)%c // Tipo de implementación del algoritmo: Recursivo ////////////////////////////////////////////////////////////////////////// static long long potenciaModular(long a, long b, long c) { if (b == 1) return a%c; else { if (b == 2) { long tmp = a%c; tmp = (tmp * tmp) % c; return tmp; } else return (potenciaModular(a,b/2,c)*potenciaModular(a,b-b/2,c))%c; } } } ////////////////////////////////////////////////////////////////////////// // Nombre de Función: Encriptar // Párametros de función: // - message : Mensaje a cifrar (Ya transformado de char a int) // - nroElementos : número de elementos del mensaje // Funcionalidad: Encripta un mensaje. // Tipo de implementación del algoritmo: Iterativa ////////////////////////////////////////////////////////////////////////// 104 int* AlgoritmoRSA::encriptar(int* message, int nroElementos) { //Almacena espacio para el mensaje encriptado int* messageEncriptado = new int[nroElementos]; //Realiza el proceso de encriptación del mensaje for (int index = 0; index < nroElementos; index++) { //Aplica el principio de potencia modular messageEncriptado[index] = AlgoritmosMatematicos::potenciaModular(message[index], e, n); } return messageEncriptado; } ////////////////////////////////////////////////////////////////////////// // Nombre de Función: Desencriptar // Párametros de función: // - message : Mensaje a decifrar // - nroElementos : número de elementos del mensaje // Funcionalidad: Desencripta un mensaje. // Tipo de implementación del algoritmo: Iterativa ////////////////////////////////////////////////////////////////////////// int* AlgoritmoRSA::desencriptar(int* message, int nroElementos) { //Almacena espacio para el mensaje desencriptado int* messageDesEncriptado = new int[nroElementos]; //Realiza el proceso de desencriptación del mensaje for (int index = 0; index < nroElementos; index++) { //Aplica el principio de potencia modular messageDesEncriptado[index] = AlgoritmosMatematicos::potenciaModular(message[index], d, n); } return messageDesEncriptado; } 105 2. Implementación en GPU con CUDA: ////////////////////////////////////////////////////////////////////////// // Nombre de Función: Encriptar en GPU // Párametros de función: // - message : Mensaje a cifrar (Ya transformado de char a int) // - nroElementos : número de elementos del mensaje // Funcionalidad: Encripta un mensaje. // Tipo de implementación del algoritmo: Iterativa en GPU, la palabra reservada // __global__ indica que la function correrá en la GPU ////////////////////////////////////////////////////////////////////////// __global__ void kernelEncriptar(int* message, int* messageEncriptado, int nroElementos, int e, int n) { int idx = blockIdx.x * blockDim.x + ThreadIdx.x; //Para procesar solamente elementos con hilos válidos, esto se hace por si el //mensaje tiene menos elementos que el número de hilos separados, ejm: si //separamos 2 bloques con 512 hilos cada uno pero el mensaje solo tiene 800 //elementos, habrán 224 hilos que no harán nada if(idx