Departamento de Computación

La criptografía de curvas elípticas tiene alta transcendencia en las aplicaciones de seguridad informática, puesto que provee mecanismos para asegurar la privacidad de la información, la autenticación entre entidades que se comunican, así como también la integridad de los mensajes que se transmiten por un medio inseguro. Actualmente existen algoritmos criptográficos que garantizan estos servicios de seguridad, sin embargo, algunos de ellos requieren una gran cantidad de procesamiento de cómputo. Tal es el caso de la multiplicación escalar, que es una operación fundamental para la implementación de la criptografía de curvas elípticas. Por consiguiente, es primordial que esta operación sea realizada de manera eficiente. Esta tesis se ha enfocado en el análisis de los algoritmos y técnicas de programación que reduzcan el tiempo de cómputo de la multiplicación escalar.Desde el punto de vista algorítmico, las curvas elípticas de Koblitz permiten que el cálculo de la multiplicación escalar pueda ser realizado rápidamente mediante la aplicación del endomorfismo de Frobenius, sin requerir el uso de doblados de puntos. La formulación de un algoritmo paralelo permitió su implementación en un procesador multinúcleo. Los conjuntos extendidos de instrucciones presentes en las recientes arquitecturas de computadoras habilitan el procesamiento en paralelo de múltiples conjuntos de datos. Dentro de estos conjuntos, el uso del multiplicador sin acarreo mejora el rendimiento de las operaciones sobre campos finitos, resultando por ende, en la aceleración del cálculo de la multiplicación escalar. Los resultados obtenidos de este trabajo de investigación ponen de manifiesto la aceleración obtenida en la paralelización de la multiplicación escalar, optimizando tanto algorítmicamente como con el uso de tecnologías recientes.

Abstract

Elliptic curve cryptography has a high significance on secure computer applications, it provides mechanisms to ensure privacy on data, authentication among communicating entities, as well as the integrity of a message sent by an insecure channel. Nowadays, there are cryptographic algorithms that ensure these security services, however, some of them require a large amount of computer processing. Such is the case of the scalar multiplication, which is a fundamental operation for the implementation of elliptic curve cryptography. It is, therefore, essential that this operation be performed efficiently. This thesis has focused on the analysis of algorithms and programming techniques to reduce the computation time of the scalar multiplication. From the algorithmic standpoint, Koblitz elliptic curves allow that the computation of the scalar multiplication can be quickly performed by applying the Frobenius’s endomorphism, without using point doublings. The formulation of a parallel algorithm allows its implementation in a multicore processor. Extended instruction sets included in the latest computer architectures enable parallel processing of multiple data sets. Within these sets, the use of the carry-less multiplier enhances the performance of operations over finite fields, thereby resulting in acceleration of computation of scalar multiplication. The results of this research show the speedup in the parallelization of the scalar multiplication, optimizing both algorithmically and with the use of recent technologies.