Análise da Eficiência Energética de Algoritmos de Criptografia Baseados em Curvas Elípticas

Abstract

A criptografia de chaves públicas (PKC) ou criptografia assimétrica, uma das bases para a comunicação segura pela Internet, fornece as pri- mitivas para a troca de chaves, autenticação de usuários e assinatura digital. A maioria dos algoritmos de PKC usados atualmente são ba- seados em conjecturas de Teoria dos Números, como a dificuldade da fatoração de inteiros ou a dificuldade de alguma versão do logaritmo dis- creto. Este último, quando usado na versão de curvas elı́pticas, permite o uso de chaves e assinaturas menores para o mesmo nı́vel de segurança de outros algoritmos, o que é interessante em ambientes com recursos computacionais limitados. Recentemente, a escala dos dispositivos que estabelecem comunicação segura pela Internet está diminuindo consis- tentemente. Essa miniaturização, no entanto, veio acompanhada de restrições de processamento e de suprimento energético, o que conflita com o fato de que algoritmos de PKC são computacionalmente caros. O presente trabalho pretende, a partir de simulações, avaliar o gasto energético do sistema de memórias de processadores executando algo- ritmos de criptografia de curvas elı́pticas. Experimentos com diversas curvas e configurações de memória são feitos para medir a taxa de faltas nas caches de dados e de instruções e para avaliar como as localidades espacial e temporal são capturadas por cada cache. Deste modo, será explicado por que o acesso à instruções é responsável pela maior parcela do consumo energético e por que a parcela relativa ao acesso de dados é pouco promissora em relação a otimizações. Como um resultado, serão identificadas quais técnicas de otimização terão um maior impacto no consumo energético do subsistema de memória.

The realm of public-key (asymmetric) cryptography (PKC) is conside- red to be one the pillars of secure communication over the Internet, since it includes user authentication, key exchange and digital signa- tures. PKC algorithms in use are mostly based on certain number- theoretic conjectures, like the difficulty of integer factorization or the difficulty of some discrete-log problem. The latter, when used in the elliptic curve setting, allows for shorter keys and signatures while main- taining the same security level of other algorithms, which is interesting in a resource constrained computing environment. Recently, the scale of the devices partaking in secure communications over the Internet has been steadily decreasing. This downscaling is responsible for new constraints on the processing power and battery supply available to each node, which directly conflicts with the fact that PKC algorithms are computationally expensive. By means of simulations, this work will evaluate the amount of energy spent in the memory subsystem when processors execute elliptic curve algorithms. By taking into account different curves and memory con- figurations, it will be possible to evaluate parameters such as the miss rate of both data and instructions caches and to asses how temporal and spatial localities are captured by each cache. This, in turn, will reveal why instruction access accounts for the biggest share of energy consumption and why the contribution from data accesses is unlikely to be reduced. As a result, a class of optimization techniques which could significantly impact the energy efficiency of the memory subsystem will be identified.