23 set 2022
15:00 Defesa de Doutorado Auditório IC3
Tema
Criptografia de Curvas Elípticas de Alto Desempenho: Uma Abordagem SIMD para Curvas Modernas
Aluno
Armando Faz Hernandez
Orientador / Docente
Julio Cesar Lopez Hernandez
Breve resumo
A criptografia baseada em curvas elípticas fornece métodos eficientes de chave pública usando chaves pequenas. Pesquisa recente sugere usar curvas de Montgomery e curvas de Edwards porque as suas operações aritméticas são mais eficientes do que usando curvas de Weierstrass. Neste contexto, a construção de algoritmos que usam estas curvas modernas traz consigo diversos desafios deixando em aberto novos alvos para otimizações.
Nossa pesquisa tem como objetivo 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 de conjuntos de instruções especializados que são extensões à arquitetura do computador. Além das extensões específicas para a criptografia, existem outras que seguem o paradigma de cômputo paralelo SIMD (do inglês, Single Instruction, Multiple Data). Neste modelo uma instrução executa-se sob um conjunto de dados de forma paralela. No entanto, usar tais recursos computacionais neste cenário requer de novas estruturas de dados e algoritmos para obter um melhor aproveitamento.
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 aplicação imediata 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 estas 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 é uma ferramenta efetiva para otimizar implementações de algoritmos criptográficos baseados em curvas elípticas. Seja isto um incentivo não só para aqueles que procuram acelerar os programas em geral, mas também esperamos que os fabricantes de computadores incluam extensões mais avançadas que suportem a crescente demanda de novos algoritmos criptográficos.
Banca examinadora
Titulares:
| Julio Cesar Lopez Hernandez | IC/UNICAMP |
| Ricardo Dahab | IC/UNICAMP |
| Marco Aurélio Amaral Henriques | FEEC/UNICAMP |
| Eduardo Moraes de Morais | Protocol Labs |
| Routo Terada | IME/USP |
| Sara Díaz Cardell | CMCC/UFABC |
Suplentes:
| Paulo Lício de Geus | IC/UNICAMP |
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Geovandro Carlos Crepaldi Firmino Pereira | IQC/U.Waterloo |
| Ricardo Dahab | IC/UNICAMP |