Departamento de Computación

La innovación tecnológica en las computadoras ha permitido que la Ley de Moore mantenga su vigencia hasta ahora, a más de 43 años que fuera propuesta por el co-fundador de Intel: Gordon E. Moore. Esta ley expresa que "aproximadamente cada 24 meses se duplica la capacidad de los procesadores digitales" [14]. Este hecho probablemente se ha visto influenciado debido a que desde la creación de la primera computadora, ha habido una demanda general por mayor capacidad de procesamiento. A medida que aumenta la demanda de velocidad y rendimiento, los diseñadores de procesadores enfrentan el desafío de requerir más energía para aumentar la capacidad de procesamiento. Sin embargo, el incremento en el consumo de energía tiene como consecuencia tener que administrar mayores niveles de disipación de calor y de potencia. La tecnología multi-núcleos surge como una alternativa para el diseño de procesadores de mayor rendimiento, ya que permite realizar múltiples operaciones en un mismo ciclo de reloj y permite incrementar la capacidad de cómputo sin tener que seguir creciendo en velocidad para lograrlo. Los procesadores "Dual-core" lanzados al mercado en 2005 y los "Quad-core" en 2007, son apenas el comienzo de la estrategia de este tipo de arquitecturas. Actualmente se continúan desarrollando nuevas tecnologías que multiplican la cantidad de núcleos contenidos en un procesador. Debido a esta tendencia tecnológica, resulta conveniente para las aplicaciones y algoritmos en diferentes áreas, tales como la criptografía, utilizar las características que ofrecen; ya que se busca que los algoritmos se ejecuten de manera rápida y eficiente. Esta tesis presenta la paralelización de un algoritmo criptográfico que permite utilizar los recursos y las ventajas que ofrecen las arquitecturas multinúcleo. El problema para poder paralelizar la multiplicación escalar en curvas binarias para punto P desconocido, es el hecho que se requiere de una recodificación del escalar k para poder hacer uso simultáneo del doblado y de la bisección de punto. Se realizó la implementación paralela de la multiplicación escalar en curvas elípticas binarias y se obtuvo una versión paralela que permite mejorar los tiempos de ejecución respecto a las versiones secuenciales. La importancia de los resultados obtenidos es que la multiplicación escalar es la operación básica en curvas elípticas y resulta ser la operación más costosa. Por tal motivo, al reducir los tiempos de ejecución de esta operación se reducen implícitamente los tiempos de ejecución de las aplicaciones que se basan en criptosistemas de curvas elípticas.

Abstract

Technological innovation in computers has enabled Moore's Law remain in force until now, more than 43 years it was proposed by the co-founder of Intel: Gordon E. Moore. This law states that "about every 24 months, the capacity of digital processors is doubled." This fact has probably been in uenced because since the creation of the first computer, there has been a huge demand for greater processing capacity. With the increasing need for speed and performance, processor designers are challenged to require more energy to increase processing capacity. However, more energy consumption results in having to manage higher levels of heat dissipation and power. Multi-core technology is emerging as an alternative for designing higher performance processors, because it allows multiple operations to be executed in one clock cycle and it also allows to increase computing capacity without having to continue increasing clock speed. "Dual-core processors released to the market" in 2005 and "Quad-cores" released in 2007, are just the beginning of a strategy that takes advantage of this kind of architectures. Nowadays processor vendors continue developing new technologies that multiply the number of cores within a processor. Due to this technological trend, it is convenient for applications and algorithms in different areas such as cryptography, to use the new features that they offer, as our goal is that algorithms run quickly and efficiently. This thesis presents the parallelization of a cryptographic algorithm that let us take advantage of multi-core architecture features. The problem to parallelize the scalar multiplication on binary curves for unknown point P is the fact that it requires a recoding of the scalar k in order to make it possible to use simultaneously the point doubling and point halving. We implemented a parallel version of the elliptic curve scalar multiplication over binary fields and we improved execution time compared with sequential versions. The importance of the results is that scalar multiplication is the basic operation in elliptic curves and it is also the most expensive operation. Therefore, reducing execution time of this operation also reduces execution time of applications based on elliptic curve cryptosystems.