En la actualidad, la criptografía de curvas elípticas está jugando un papel muy importante en lo que se refiere a diseños de esquemas criptográficos, cuya clave de cifrado es relativamente pequeña. No obstante, ante la inminente llegada de las computadoras cuánticas, la criptografía de curvas elípticas se ve impactada negativamente por la existencia de un algoritmo cuántico (el algoritmo de Shor), el cual tiene un tiempo de ejecución polinómico. Debido a esta problemática, la comunidad criptográfica ha sugerido el uso de la criptografía basada en isogenias, la cual sigue basándose en el uso de curvas elípticas pero con la diferencia de que el algoritmo de Shor no peligra su seguridad. Una de las ventajas del uso de isogenias es que permite claves de cifrado pequeñas, aunque son costosos (computacionalmente hablando) con respecto a otros esquemas criptográficos. Por su parte, mientras las computadoras cuánticas no cuenten con las características necesarias para quebrantar la criptografía de curvas elípticas, sigue siendo de interés determinar que tan segura es esta criptografía. Por ejemplo, el ataque gGHS es usado en la criptografía de curvas elípticas binarias para reducir instancias del Problema del Logaritmo Discreto en una curva elíptica hacia el jacobiano de una curva hiperelíptica; se dice que un criptosistema basado en curvas elípticas es vulnerable ante este ataque si es mucho más sencillo resolver esta nueva instancia del Problema del Logaritmo Discreto.
En esta tesis se presenta una implementación en Magma para resolver el problema del logaritmo discreto sobre una curva binaria GLS; construyendo así una curva vulnerable ante el ataque gGHS, junto con la aplicación de algoritmos basados en cálculo de índices, para la resolución del Problema del Logaritmo Discreto en el jaco- biano de una curva hiperelíptica de género grande; en particular, fue posible demostrar que el endomorfismo asociado a la curva GLS permite acelerar el ataque GHS del descenso de Weil. A su vez se presentan implementaciones eficientes en lenguaje C de i) ataques clásicos al protocolo SIDH, y ii) el protocolo CSIDH para intercambio de claves; ambos protocolos basados en isogenias.
Abstract
Nowadays, the elliptic curve cryptography is playing an important role in the design of cryptographic schemes. Nevertheless, the imminent arrival of quantum computers risk the security of elliptic curves cryptography; that is because Shor's algorithm allows to break it with a polynomial running-time. Due to this problematic, the cryptographic community has suggested the use of isogenies in cryptography, which is still using elliptic curves such that Shor's algorithm doesn't apply. Additionally, isogenybased cryptography allows small keys but it is slow compared with other cryptographic schemes. For its part, before quantum computers break elliptic curve cryptography, it is important to determine whether an elliptic curve is recommended for cryptographic usage. For example, one can use the gGHS Weil descent attack in order to reduce an instance of the Discrete Logarithm Problem on a binary elliptic curve into the Jacobian of a hyperelliptic curve of higher genus; in particular, a cryptosystem based on elliptic curves is called vulnerable against this attack if it is much easier to solve the new instance of the Discrete Logarithm Problem.
In this thesis, it is presented a Magma-code implementation for solving the DLP on a binary GLS curve. For this purpose, a vulnerable curve against the gGHS Weil descent attack was constructed, and then an index-calculus based algorithm was used in order to solve the Discrete Logarithm Problem on the Jacobian of a hyperelliptic curve of a higher genus; furthermore, it was possible to prove that the associated GLS endomorphism allows to speedup the GHS Weil descent attack. Additionally, it is presented efficient C-code implementations of i) classical attacks to SIDH protocol, and ii) CSIDH protocol for key-agreement algorithms; both protocols are based on isogenies.
