Departamento de Computación

Texto completo de la Tesis            Video del evento          

Resumen

En los últimos años el uso de curvas elípticas en criptografía ha ganado popularidad, debido a que permiten usar llaves criptográficas cortas. En particular, las curvas elípticas binarias ofrecen una característica adicional, pueden implementarse de forma eficiente en los procesadores actuales ya que la aritmética en campos binarios permite aprovechar su arquitectura. La operación fundamental en los protocolos criptográficos basados en curvas elípticas es la multiplicación escalar de puntos, la cual es también la más costosa. En esta tesis se realiza un análisis de eficiencia y seguridad de dicha operación en dos familias de curvas. La primera familia consiste de las llamadas curvas de Galbraith-Lin-Scot (GLS) binarias, que pueden ser equipadas con un endomorfismo eficiente para acelerar la multiplicación escalar. Para estas curvas presentamos dos construcciones de endomorfismos, la primera es una alternativa del endomorfismo GLS y la segunda es la construcción de una familia de endomorfismos, ambas construcciones permiten realizar el cálculo de la multiplicación escalar de una manera más rápida; la segunda familia que se presenta es la conformada por las curvas anómalas binarias, también llamadas de Koblitz, estas curvas se caracterizan por hacer uso del endomorfismo de Frobenius para acelerar la multiplicación escalar. En esta familia se presenta un nuevo endomorfismo sobre extensiones del campo F4, que requiere la mitad de las operaciones que el de Frobenius. Además, se presenta un análisis de seguridad de las posibles vulnerabilidades que surgen al usar endomorfismos para el cálculo de la multiplicación escalar.

Abstract

Nowadays, the use of elliptic curves in cryptography has gained popularity since they allow to use short cryptographic keys. In particular, binary elliptic curves can be implemented eficiently in current processors because their field arithmetic can take advantage of processor architecture. The most important operation in a elliptic curves based protocol is scalar point multiplication, which is also the most expensive. In this thesis we show an eficiency and security analysis of the scalar multiplication in two curve families. The first family is the binary Galbraith-Lin-Scot (GLS) family, which can be equipped with an eficient endomorphism to accelerate the scalar multiplication. We show two endomorphism constructions, at first we present an alternative to the GLS endomorphism followed by an endomorphism family propposed by us, both constructions allow acelerate the scalar multiplication; In addition, we present a security analysis due to the potential vulnerabilities of using endomorphism in scalar multiplication. The second family consist of the anomalous curves also know as Koblitz curves, these curves are characterized by the use of the Frobenius endomorphism to accelerate scalar multiplication. In this family we present a new endomorphism that works on the F4 finite field extensions, which requires half of the Frobenius operations.