Evaluación paralela de sumas de puntos recionales sobre curvas elípticas

Abstract

Los sistemas criptogr´aficos basados en curvas el´ıpticas fueron propuestos por vez primera de manera independiente por Miller [68] y Koblitz [49], despu´es del trabajo de Lenstra [56] en factorizaci´on de enteros. La caracter ´ıstica principal de los criptosistemas de curvas el´ıpticas (CCE) es la menor longitud de claves en relaci´on al RSA [82] as´ı como a otros sistemas basados en el logaritmo discreto sobre campos finitos. Se pueden construir sistemas criptogr´aficos basados en el logaritmo discreto sobre curvas el´ıpticas con longitudes de clave de 150 a 200 bits [64]. Actualmente se encuentra en proceso la estandarizaci´on de los CCE por la IEEE [52] as´ı como por otros organismos tales como ANSI [4] e ISO [45]. Los CCE pueden servir de base para varios servicios de seguridad tales como el intercambio de claves, privacidad mediante cifrado, y autenticaci´on e integridad de mensajes mediante firmas digitales [32]. Por las razones expuestas los CCE son crecientemente utilizados en aplicaciones de seguridad inform´atica. Por lo tanto, resulta de especial inter´es el tener implementaciones eficientes de CCE. Por otro lado, el paralelismo parece ser la alternativa m´as viable para aumentar la capacidad de procesamiento de las computadoras en un futuro cercano [44] [41] [11]. La posibilidad de construir multicomputadoras a partir de componentes com´unes, en arquitecturas de tipo Beowulf [11] as´ı como la existencia de software libre para el desarrollo de aplicaciones de programaci ´on paralela ha hecho que se popularice el uso del paralelismo. Hasta ahora sin embargo, el uso del paralelismo en criptolog´ıa se ha restringido a la b´usqueda de colisiones en paralelo [27] [103] para el criptoan´alisis de sistemas basados en logaritmos discretos. Por ejemplo, no existen a la fecha sistemas de criptograf´ıa de clave p´ublica que hayan sido especialmente desarrollados para arquitecturas multiprocesadores. La investigaci´on 9 de algoritmos para exponenciaci´on discreta, operaci´on b´asica en la mayor´ıa de los sistemas de criptograf´ıa de clave p´ublica, se centra exclusivamente en el caso secuencial [104]. Estos algoritmos son de complejidad lineal, aproximadamente, sobre el n´umero de bits del exponente. Es de esperarse entonces que, utilizando procesamiento paralelo, puedan encontrarse algoritmos para exponenciaci´on discreta cuya complejidad sea logar´ıtmica sobre la longitud de la clave. Esto permitir´ıa la creaci´on de sistema de criptograf´ıa de clave p´ublica para arquitecturas multiprocesadores. En este trabajo se presenta un algoritmo para la evaluaci´on de potencias de puntos sobre curvas el´ıpticas que haciendo uso del paralelismo logra reducir el tiempo de ejecuci´on respecto a los algoritmos secuenciales conocidos hasta ahora. Se evalua el desempe˜no de la implementaci´on del algoritmo sobre una multicomputadora de componentes comunes comparandola con implementaciones en software de CCE reportadas en la literatura y se muestra que el algoritmo es particularmente eficiente en el caso de las curvas de Koblitz.