| dc.description.abstract | RESUMEN:
Hoy en día se tiene un gran avance tecnológico, en particular en los procesadores o CPU (del inglés, Central Processing Unit) y en las unidades de procesamiento gráfico o GPU (del inglés, Graphics Processing Unit), que en conjunto con las bibliotecas adecuadas, tales como OpenMP y CUDA (por sus siglas en inglés, Compute Unified Device Architecture), respectivamente, son una buena alternativa para resolver problemas computacionales de forma paralela, es decir, dividir el problema en tareas pequeñas, si es posible, para que sean asignadas a cada núcleo que compone un CPU o a cada hilo del GPU, con el fin de procesarlas en paralelo.
En esta tesis presentamos varias estrategias de paralelización con el fin de resolver dos casos de estudio importantes del área de criptografía.
El primero es el problema del logaritmo discreto, ayudamos a encontrar la solución, que se considera difícil de resolver sobre un campo finito, varios sistemas criptográficos basan su seguridad en este problema, sin embargo, existen estudios que demuestran que es factible encontrar la solución pero requieren resolver varios sistemas de ecuaciones lineales sobre un campo finito, los cuales son idóneos para aplicar diferentes estrategias de paralelización, tanto en CPU como para GPU, considerando varios factores que pueden influir en su procesamiento, tales como los elementos del campo son de varios cientos de bits, las matrices son altamente dispersas, es decir, solo una pequeña fracción de los elementos son diferentes a cero, entre otros. Las estrategias paralelas propuestas consideran todos los posibles factores que pueden influir, con el fin de obtener un buen rendimiento y hacer factible el procesamiento de una instancia del logaritmo discreto, logrando romper un récord criptográfico al ser los primeros en trabajar en dicha instancia.
El segundo es efectuar de manera eficiente el algoritmo RSA en el GPU, que pertenece al criptosistema de llave pública. RSA es ampliamente usado en aplicaciones de seguridad, tal como la firma y verificación de certificados digitales, sin embargo, RSA es un algoritmo relativamente lento, por lo tanto se debe diseñar una estrategia paralela cuidadosamente. La estrategia que se propone toma ventaja de las características que ofrece el GPU para obtener un rendimiento competitivo con respecto al estado del arte, logrando obtener un récord en rendimiento del RSA.
ABSTRACT:
Nowadays we are living great technological advancements. Processors in particular, also called CPU (Central Processing Unit) and the GPU (Graphics Processing Unit) in conjunction with the adequate libraries such as OpenMP and CUDA (Compute Unified Device Architecture), respectively. They are a good option to solve computational problems in parallel. In other words, break the problem into small tasks if possible so they can be assigned to each core of the CPU or each thread of the GPU to be executed in parallel.
In this thesis, we present several parallelization strategies in order to solve two important
case studies from cryptography.
The very first one is the Discrete Logarithm Problem. We helped on finding the solution that it is considered hard to solve over a finite field. Many cryptographic systems based their security on this problem. However, studies prove that it is feasible to find the solution but they require solving several systems of linear equations over a finite field, which are suitable to apply different parallelization strategies either to CPU or GPU taking into account many factors that can affect its processing. Like the elements of the field are several hundreds of bits, large sparse matrices, in other words, only a small fraction of the elements are non-zero, among others. Parallel strategies proposed consider all the possible factors that can affect in order to obtain a good performance and make feasible the processing of a discreet logarithm instance, breaking down a cryptographic record by being the first ones to work in this matter.
The second one is to efficiently perform the RSA algorithm on the GPU, which belongs to the pubic key cryptosystem. RSA is widely used in security applications, such as signing and verifying digital certificates. Nevertheless, RSA is a relatively slow algorithm; therefore, a parallel strategy must be designed very carefully. The proposed strategy takes advantage of all the features that the GPU offers to get a competitive performance concerning the state of the art, achieving a record in RSA performance. | |
