Criptografia de curvas elípticas de alto desempenho : uma abordagem SIMD para curvas modernas

Orientador: Julio César López Hernández Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A criptografia baseada em curvas elípticas fornece métodos eficientes para a criptografia de chave pública. Pesquisa recente tem mostrado a superioridade das curvas de Montgomery e de Edwards sobre as curvas de Weierstrass pois elas precisam de menos operações aritméticas. O uso destas curvas modernas, porém, traz consigo diversos desafios na construção de algoritmos criptográficos deixando em aberto novos alvos de otimizações. Nosso objetivo principal é propor otimizações algorítmicas e técnicas de implementação para os algoritmos criptográficos baseados em curvas elípticas. Visando acelerar a execução destes algoritmos, nossa abordagem fundamenta-se na utilização extensões ao conjunto de instruções da arquitetura. Além daquelas específicas para a criptografia, nós usamos extensões que seguem o paradigma de cômputo paralelo SIMD (do inglês, Single Instruction, Multiple Data). Neste modelo, o processador executa a mesma operação sobre um conjunto de dados de forma paralela. Nós investigamos como aplicar o modelo SIMD na implementação de algoritmos de curvas elípticas. Como parte de nossas contribuições, projetamos algoritmos paralelos para a aritmética de corpos primos e de curvas elípticas. Projetamos também um algoritmo de multiplicação escalar para calcular P + kQ e uma fórmula otimizada para calcular 3P em curvas de Montgomery. Estes algoritmos encontraram aplicabilidade na criptografia baseada em isogenias. Usando extensões SIMD tais como SSE, AVX e AVX2, desenvolvemos implementações otimizadas dos seguintes algoritmos criptográficos: X25519, X448, SIDH, ECDH, ECDSA, EdDSA e qDSA. Testes de desempenho mostram que essas implementações são mais rápidas do que as implementações existentes no estado da arte. Nosso estudo confirma que o uso de extensões ao conjunto de instruções da arquitetura é uma ferramenta efetiva para otimizar implementações de algoritmos criptográficos baseados em curvas elípticas. Seja isto um incentivo não somente para aqueles que procuram acelerar os programas em geral, mas também para que os fabricantes de computadores adicionarem mais extensões avançadas para apoiar a demanda crescente da criptografia Abstract: Cryptography based on elliptic curves is endowed with efficient methods for public-key cryptography. Recent research has shown the superiority of the Montgomery and Edwards curves over the Weierstrass curves as they require fewer arithmetic operations. Using these modern curves has, however, introduced several challenges to the cryptographic algorithm’s design, opening up new opportunities for optimization. Our main objective is to propose algorithmic optimizations and implementation techniques for cryptographic algorithms based on elliptic curves. In order to speed up the execution of these algorithms, our approach relies on the use of extensions to the instruction set architecture. In addition to those specific for cryptography, we use extensions that follow the Single Instruction, Multiple Data (SIMD) parallel computing paradigm. In this model, the processor executes the same operation over a set of data in parallel. We investigated how to apply SIMD to the implementation of elliptic curve algorithms. As part of our contributions, we design parallel algorithms for prime field and elliptic curve arithmetic. We also design a new three-point ladder algorithm for the scalar multiplication P + kQ, and a faster formula for calculating 3P on Montgomery curves. These algorithms have found applicability in isogeny-based cryptography. Using SIMD extensions such as SSE, AVX, and AVX2, we develop optimized implementations of the following cryptographic algorithms: X25519, X448, SIDH, ECDH, ECDSA, EdDSA, and qDSA. Performance benchmarks show that these implementations are faster than existing implementations in the state of the art. Our study confirms that using extensions to the instruction set architecture is an effective tool for optimizing implementations of cryptographic algorithms based on elliptic curves. May this be an incentive not only for those seeking to speed up programs in general but also for computer manufacturers to include more advanced extensions that support the increasing demand for cryptography Doutorado Ciência da Computação Doutor em Ciência da Computação FAPESP 14/50704-7