Departamento de Computación

Desde el inicio de la criptografía de llave pública, los campos finitos de característica chica han sido propuestos como estructuras matemáticas en implementación de protocolos de comunicación electrónica, cuyo objetivo es garantizar distintos atributos de seguridad. Estas estructuras son propuestas porque pueden ser implementadas eficientemente en sistemas numéricos binarios o ternarios, los cuales son intrínsecos de las arquitecturas computacionales modernas. En esta tesis se realiza un análisis de la seguridad y eficiencia de distintas primitivas basadas en estos campos finitos. En la primera parte de la tesis, presentamos la implementación eficiente en software del algoritmo para la multiplicación escalar de puntos en dos familias de curvas elípticas binarias, las cuales cuentan con endomorfismos eficientemente computables. La primera familia es la llamada de Galbraith-Lin-Scott (GLS). En estas curvas presentamos implementaciones construidas con los métodos de Gallant-Lambert-Vanstone y la escalera de Montgomery, con la finalidad de computar una multiplicación escalar eficiente y protegida contra ataques de canal lateral. La segunda familia es la denominada como curvas binarias anómalas o curvas de Koblitz. En esta familia presentamos, de manera inédita, la implementación del algoritmo de multiplicación escalar de puntos protegida contra ataques de canal lateral, basados en tiempo, mediante la técnica de recodificación regular. Además, introducimos una novedosa implementación de las curvas de Koblitz definidas sobre la extensión de campo F4, lo que resultó en una aritmética eficiente que toma ventaja del paralelismo ofrecido por los procesadores de escritorio más recientes. Todas las implementaciones mencionadas fueron basadas en el nuevo sistema de coordenadas proyectivas lambda que aportan formulas al “estado del arte" para el cómputo de la aritmética de puntos. En la segunda parte, realizamos un análisis del impacto de los avances recientes en la solución del problema del logaritmo discreto (PLD) en campos finitos de característica chica de interés criptográfico. También, realizamos ataques prácticos en campos finitos usados en protocolos basados en emparejamientos. Finalmente, implementamos métodos para mejorar la eficiencia del algoritmo de Enge y Gaudry para resolver el PLD en curvas hiperelípticas

Abstract

Since the beginning of public-key cryptography, small-characteristic finite fields have been proposed as basic mathematical structures for implementing electronic communication protocols and standardized algorithms that achieve different information security objectives. This is because the arithmetic on these fields can be efficiently realized in the binary and trinary number systems, which are fundamental in modern computer architectures. This thesis proposes a concrete analysis of the current security and performance of different primitives based on these fields. In the first part of this document, we introduce efficient software implementations of the point multiplication algorithm for two families of binary elliptic curves which are provided with efficiently computable endomorphisms. The first class is called Galbraith-Lin-Scott (GLS) curves. There, we present state-of-the-art implementations based on the Gallant-Lambert-Vanstone decomposition method and on the Montgomery ladder approach, in order to achieve a high-speed protected and non-protected code against timing attacks. The second family studied in this thesis is called anomalous binary curves or Koblitz curves. On these elliptic curves, we present, for the first time, a timing-attack protected scalar multiplication based on the regular recoding approach. In addition, we introduce a novel implementation of Koblitz curves defined over the extension field F4, which resulted in an efficient arithmetic that exploits the internal parallelism contained in the newest desktop processors. All of the previously mentioned implementations are supported by a new projective coordinate system, denoted lambda-coordinates, which provides state-of-the-art formulas for computing the basic point arithmetic operations. In the second part, we provide a concrete analysis of the impact of the recent approaches for solving the discrete logarithm problem (DLP) in small-characteristic fields of cryptographic interest. After that, we realize practical attacks against fields proposed in the literature to realize pairing-based protocols. Finally, we study the practical implications of the Gaudry-Hess-Smart attack against the binary GLS curves. For that purpose, we analyze and implement techniques to improve the efficiency of the Enge-Gaudry algorithm for solving the DLP over hyperelliptic curves.