Durante las últimas cuatro décadas, el paradigma de la criptografía de llave pública ha brindado soluciones elegantes a diversos problemas difíciles que surgen de aplicaciones contemporáneas de seguridad de la información. Ejemplos de estos problemas incluyen: autenticación de entidades, anonimato, no repudio, por nombrar sólo algunos. No obstante, la implementación eficiente de la criptografía de llave pública implica el cálculo de operaciones aritméticas no triviales sobre operandos extremadamente grandes. Por tal motivo, el objetivo principal de esta tesis es analizar cuidadosamente algunos de los protocolos criptográficos de llave pública más populares, con la finalidad de identificar las operaciones críticas que influyen significativamente en el costo computacional de dichos esquemas. Una vez identificadas estas operaciones, nuestro siguiente objetivo es proponer mejoras algorítmicas y/o de implementación que permitan reducir significativamente el tiempo de ejecución de estos protocolos, mientras se mantiene la seguridad en contra de ataques de canal lateral de los esquemas. Este trabajo de investigación examina tres subáreas diferentes de la criptografía de llave pública, es decir, esquemas basados en la factorización de números enteros, emparejamientos e isogenias. Las primeras dos subáreas se han utilizado e implementado intensamente en innumerables aplicaciones de seguridad de la información. Mientras que el último esquema es un candidato prometedor para realizar el intercambio de llaves secretas en un escenario post-cuántico, donde se supone que ya se encuentran disponibles computadoras cuánticas suficientemente poderosas. Nuestro estudio comienza realizando un análisis cuidadoso de la implementación eficiente de la aritmética entera y de campos finitos en las micro-arquitecturas de los procesadores más recientes. Este análisis nos permitió diseñar una biblioteca de software que es utilizada para implementar de manera segura el algoritmo de firma RSA. De la subárea de criptografía basada en emparejamientos, se aborda el problema general del "hashing" de tiempo constante hacia curvas elípticas, donde se proponen algoritmos prácticos, eficientes y seguros para realizar el "hashing" a los subgrupos de curva elíptica utilizados en este tipo de protocolos. Además, se diseño una biblioteca de software que implementa dos protocolos de autenticación de dos factores, los cuales son seguros contra ataques simples de canal lateral. Por otra parte, proponemos el uso de emparejamientos sobre curvas elípticas con grado de encajamiento uno para implementar el protocolo de firma corta propuesto por Boneh, Lynn y Shacham (BLS). Nuestro esquema aprovecha el hecho de que la mejora algorítmica para el cálculo de logaritmos discretos, reportado recientemente por Kim y Barbulescu, no se aplica al escenario cuando el "Discrete Logarithm Problem" (DLP) se calcula en campos finitos de orden primo. En el caso de la criptografía basada en isogenias, se proponen diversas optimizaciones algorítmicas cuyo objetivo es mejorar el desempeño de las operaciones aritméticas de curvas elípticas y campos finitos. Estas optimizaciones producen una aceleración importante del tiempo de ejecución del protocolo "Supersingular Isogeny Diffie-Hellman" (SIDH). Finalmente, se presenta una nueva construcción del protocolo SIDH, utilizando isogenias cuyo grado no es una potencia de un primo, la cual permite conseguir una aceleración considerable en su cálculo.
Abstract
During the last four decades, the public-key cryptography paradigm has provided elegant solutions to several difficult problems that arise in contemporary information security applications. Examples of these problems include, entity authentication, anonymity, nonrepudiation to name just a few. Nevertheless, the efficient implementation of public-key cryptography involves the computation of non-trivial arithmetic operations with extremely large operands. Accordingly, the main research goal of this thesis is to carefully analyze some of the most popular public key cryptographic protocols with the aim of identifying critical operations that significantly influence the whole computational cost of those schemes. Once that these operations were identified, our next objective was to propose algorithmic and/or implementation improvements that allow us to obtain significant speedups in the running time of those protocols, while keeping a sound security of those schemes against side-channel attacks. In this research work, we examine three different sub-areas of public-key cryptography, namely, Integer-factorization-based, pairing-based and isogeny-based cryptographic schemes. The first two sub-areas have been intensively used and deployed in innumerable information security applications. The last sub-area is a promising candidate for computing secret key-exchange in a post-quantum scenario, where it is assumed that powerful quantum computers are already available. Taking into account practical considerations, we started our study by performing a careful analysis of the efficient implementation of integer and finite field arithmetic over the newest desktop micro-architectures. In this study, different techniques for the efficient computation of modular multiplication were especially analyzed due to the large in influence of this operation in the performance achieved by the cryptographic schemes studied in this work. This study allows us to design a software library used for implementing the RSA signature algorithm in a secure way. In the case of pairing-based cryptography, we discuss the general problem of constant-time hashing into elliptic curves and we propose practical, efficient, and secure algorithms for hashing values to elliptic curve subgroups used in pairing-based cryptographic protocols. Moreover, we design a software library that implements two pairing-based two-factor authentication protocols, which allows to thwart simple side-channel attacks. Then, we also propose the usage of pairings over elliptic curves with embedding degree one to implement the Boneh, Lynn and Shacham (BLS) short signature protocol. Our scheme takes advantage of the fact that the algorithmic improvement for computing discrete logarithms recently reported by Kim and Barbulescu, do not apply to the scenario when the Discrete Logarithm Problem (DLP) is computed on prime-order fields Fp. In the case of isogeny-based cryptography, we proposed several algorithmic optimizations targeting both elliptic curve and finite field arithmetic operations. These optimizations yielded an important speedup in the runtime cost of the Supersingular Isogeny Diffie-Helmann (SIDH) protocol. Finally, we presented a new construction of the SIDH using non-prime power degree isogenies in the Bob's side, which allows us to achieve a considerable speedup in its computation.
