Fast FPGA implementations of elliptic curve point multiplication

Abstract

Elliptic curve cryptography is a variant of public key cryptography in which encryption and decryption processes involve operations on an algebraic structure defined on an elliptic curve over a finite field. Elliptic curve cryptographic schemes based on this variant are attractive because they can guarantee the same level of security as other systems such as RSA using much shorter key lengths. For example, for the recommended security with a 3072 bits RSA key, only 256 bits are necessary for a key in an elliptic curve cryptosystem. Two fundamental aspects of a study of these cryptosystems are security and efficiency. The security of an elliptic curve cryptosystem is based on the intractability of solving the mathematical problem called the “Elliptic Curve Discrete Logarithm Problem”. Interest in this problem is based on the fact that for sufficiently large group order, the solution of the discrete log problem is computationally in- tractable. On the other hand, the high demand for encryption of data and the constant changes in technology require that encryption schemes be ever more rapid and efficient. Because of the fact that elliptic curve point multiplication is both the most frequently used and the costliest operation used in elliptic curve encryption systems, efforts to improve the performance of these schemes have focused on this operation. We propose a fast FPGA implementation of elliptic curve point multiplication defined on a special type of field of the form GF(p3) and with a claimed level of security equal to 128 bits. We synthesized and simulated our implementation on Virtex-4, Virtex-5, and Virtex-6 FPGAs families. Comparing our running times with the best times currently found in the literature, we found that our times are up to 18 faster.

La criptografía de curva elíptica es una variante de la criptografía de clave pública en el cual los procesos de cifrado y descifrado envuelven operaciones en una estructura algebraica definida por una curva elíptica sobre un cuerpo finito. Los esquemas criptográficos de curva elíptica basados en esta variante son atractivos porque pueden garantizar el mismo nivel de seguridad que otros sistemas como RSA usando longitudes de clave mucho más cortas. Por ejemplo, para la seguridad recomendada con una clave de 3072 bits en RSA, solo se necesitan 256 bits para una clave en un criptosistema de curva elíptica. Dos aspectos fundamentales en el estudio de estos criptosistemas son, la seguri- dad y eficiencia. La seguridad de un criptosistema de curva elíptica se basa en la intratabilidad de resolver un problema matemático llamado “ Problema de logar- itmo discreto en curva elíptica ”. El interés en este problema se basa en el hecho de que, para un orden de grupo suficientemente grande, la solución del problema de logaritmo discreto es computacionalmente intratable. Por otro lado, la gran de- manda de cifrado de datos y los constantes cambios en la tecnología requieren que los esquemas de cifrado sean cada vez más rápidos y eficientes. Debido al hecho de que la multiplicación de punto en curvas elipticas es la operación más utilizada y costosa en los sistemas de encriptación de curva eliptica, los esfuerzos para mejorar el rendimiento de estos esquemas se han centrado en esta operación. Proponemos una implementación rápida de FPGA de multiplicación de punto de curva elíptica definida en un tipo especial de cuerpo de la forma GF(p3) y con un nivel de seguridad de 128 bits. Nosotros sintetizamos y simulamos nuestra im- plementación en tarjetas de las familias Virtex-4, Virtex-5 y Virtex-6. Comparando nuestros tiempos de ejecución con resultados recientes en la literatura, encontramos que nuestros resultados son hasta 18 veces más rápido.