Sobre la multiplicación escalar en curvas elípticas definidas en cuerpos de extensión óptimo

Abstract

La seguridad de los sistemas de encriptación de clave pública está basada en la intratabilidad de ciertos problemas matemáticos, tales como la factorización de enteros que son producto de dos o más primos muy grandes. La encriptación de curva elíptica es un sistema de clave pública cuya seguridad está basada en la dificultad de encontrar el logaritmo discreto de un punto aleatorio en la curva elíptica con respecto al punto base público conocido. Una de las ventajas de la Criptografía de Curva Elíptica (CCE) es que esta puede ofrecer un alto nivel de seguridad con claves mucho más pequeñas que los sistemas tradicionales tales como RSA. En muchas aplicaciones, los tiempos consumidos en la encriptación de datos pueden significar un gran problema. Por tanto, una tarea muy importante es optimizar el rendimiento de las operaciones en los sistemas de encriptación, así como una de las operaciones más importantes y de las que más tiempo consume en los sistemas de CCE que es la multiplicación escalar. La mayoría de los esfuerzos para optimizar las operaciones de CCE hasta aquí, han sido dirigidas hacia la optimización de operaciones sobre cuerpos finitos de orden un número primo o una potencia de 2. Se han hecho muy pocos trabajos para operaciones sobre cuerpos finitos de orden una potencia de un primo mayor que 2. Una excepción es el trabajo de Daniel Bailey y Christof Paar quienes introdujeron el concepto de Cuerpos de Extensión Optimo (CEO). Un CEO es un cuerpo Fpm de orden pm el cual puede ser definido por un binomio irreducible xm − ω y donde p es un tipo especial de primo llamado un primo seudo Mersenne. Estos cuerpos son bien adecuados para implementaciones de “software” de sistemas CCE sobre máquinas de arquitectura fija. En este trabajo consideramos sistemas CCE sobre una variación de CEOs que son más adecuadas para implementaciones de hardware e ilustramos nuestras ideas con una implementación en un FPGA. En vez de un primo seudo Mersenne requerimos primos de la forma 2n − (2i + 1), con tal primo p, la reducción módulo p puede ser llevada a cabo con un mínimo número de desplazamientos y sumas. Dado un tamaño de “bit” s, consideramos el problema de determinar un primo p de la forma dada, un m tal que pm es igual o cercano a s y un polinomio f(x) = xm −ω que sea irreducible sobre Fp que optimice el rendimiento de las operaciones sobre el cuerpo Fpm. Un interés particular es elegir m = 2 ´o m = 3 ya que en estos casos hay formulas simples para la reducción módulo f(x) e inversos en Fpm. Un cuerpo comúnmente usado para CCE es F2 163, cuyos elementos tienen el tamaño de 163 “bits”. Para un cuerpo de tamaño comparable, nosotros elegimos p = 254 − 33 y m = 3. Los elementos de F(254−33)3 tienen un tamaño de 162 “bits”. En este caso elegimos el binomio irreducible x3 − 2 de modo que las multiplicaciones en las reducciones módulo f(x) puedan ser remplazadas por desplazamientos izquierdos. Comparando nuestra implementación de la multiplicación escalar sobre un FPGA con otra implementación publicada sobre el cuerpo F2 163, observamos que nuestra implementación es en promedio 4 veces más rápida.

The security of public key encryption systems is based on the intractability of certain mathematical problems, such as factoring integers that are products of two or more very large primes. Elliptic curve cryptography (ECC) is a public key system whose security is based on the difficulty of finding the discrete logarithm of a random elliptic curve point with respect to a publicly known base point. One of the advantages of ECC is that it can yield a level of security with much smaller keys than traditional systems such as RSA. In many applications, the time spent on data encryption can be a significant bottleneck. A very important task is thus to optimize the performance of encryption system operations. The most important, as well as the most time consuming, operation in an ECC system is scalar multiplication. Most of the efforts at optimizing ECC operations so far have been directed toward optimizing operations over finite fields of order either a prime or a power of 2. Very little work has been done for operations over finite fields of order a power of a prime. An exception is the work of Daniel Bailey and Christof Paar who introduced the concept of optimal extension fields (OEFs). An OEF is a field Fpm of order pm which can be defined by an irreducible binomial xm −ω and where p is a special type of prime called a pseudo-Mersenne prime. These fields are well suited for software implementations of ECC systems on machines of fixed word size. In this work we consider ECC systems based on a variation of OEFs that is better suited for hardware implementations and we illustrate our ideas with an implementation in field programmable gate arrays (FPGAs). Instead of pseudoMersenne primes, we require primes of the form 2n − (2i + 1). With such a prime p reduction modulo p can be performed with a minimum number of shifts and sums. Given a bit size s we consider the problem of determining a prime of the given form, an m such that pm is equal to or nearly equal to s and an irreducible binomial f(x) = xm − ω over Fp that optimizes the performance of field operations over Fpm. Choosing m = 2 or m = 3 is of particular interest since in this case there are simple formulas for both reduction modulo f(x) and Fpm inverses. One commonly used field for ECC is F2 163, whose elements have bit size 163. For a comparable size Fpm, we choose p = 254 − 33 and m = 3. The elements of Fpm have bit size 162. In this case, we can choose the irreducible binomial to be f(x) = x3−2, so that the multiplications in reductions modulo f(x) can be replaced by left shifts. Comparing our FPGA implementation to that of another published FPGA implementation of scalar multiplication over the field F2 163, we see that our implementation is on the average more than four times faster.