Implementaç˜ao eficiente de criptografia de curvas el´ıpticas em
Transcrição
Implementaç˜ao eficiente de criptografia de curvas el´ıpticas em
Implementação eficiente de criptografia de curvas elı́pticas em sensores sem fio Diego Aranha, Danilo Câmara, Julio López, Leonardo Oliveira, Ricardo Dahab Instituto de Computação - UNICAMP Financiado por FAPESP, processo 2007/06950-0. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Redes de sensores sem fio Uma rede de sensores sem fio é uma rede ad hoc de dispositivos configurados para realizar monitoramento cooperativo. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio O problema Desafio Proteger uma rede de sensores sem fio, onde os nós são escassos em recursos e de natureza descartável. Contribuições Implementação eficiente de aritmética no corpo F2163 ; Implementação eficiente de criptografia de curvas elı́pticas. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio A plataforma Caracterı́sticas do MICAz Mote: Processador ATMega128, 7.3828 MHz; 4KB memória RAM, 128KB memória ROM; Pipeline de 2 estágios; Alto custo de instruções de acesso à memória. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Trabalhos relacionados Tabela: Tempos publicados para a multiplicação de ponto em um MICAz Mote para o nı́vel de segurança de 160 bits. Corpo Binário Primo Trabalho [Malan et al. 2004] [Yan and Shi 2006] [Eberle et al. 2005] [Szczechowiak et al. 2008] [Seo et al. 2008] [Wang and Li 2006] [Szczechowiak et al. 2008] [Gura et al. 2004] [Uhsadel et al. 2007] [GrobSchadl 2006] D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Tempo de execução (s) 34 13.9 4.14 2.16 1.14 1.35 1.27 0.81 0.76 0.745 Implementação eficiente de ECC em sensores em fio Frases para lembrar... “In this paper we consider only prime integer fields since binary polynomial field arithmetic, specifically multiplication, is insuficiently supported by current microprocessors and would thus lead to lower performance.” “This is not the case for arithmetic operations over fields GF(2m ). Though these operations could be implemented in hardware rather efficiently, executing them on standard processors is prohibitively slow.” D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Curvas elı́pticas Uma curva elı́ptica binária é o conjunto de soluções (x, y ) ∈ F2m × F2m que satisfazem a equação y 2 + xy = x 3 + ax 2 + b, onde a, b ∈ F2m com b 6= 0, e um ponto no infinito ∞. O conjunto de pontos sob a operação + (secante e tangente) forma um grupo aditivo. A multiplicação de ponto é definida pela relação de recorrência: se k = 0; ∞, kP = (−k)(−P) se k ≤ −1; (k − 1)P + P se k ≥ 1. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Corpo finito F2m Base polinomial: a(z) ∈ F2m = Pm−1 i=0 ai z i . Representação em software: vetor de dm/8e bytes. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Adição em F2m b 20 ... 9 8 7 6 5 4 3 2 1 0 a 20 ... 9 8 7 6 5 4 3 2 1 0 + + + + + + + + + + + + c 20 ... 9 8 5 6 7 D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab 4 3 0 1 2 Implementação eficiente de ECC em sensores em fio Quadrado em F2m a(z)2 = Pm−1 i=0 ai z 2i = am−1 z 2m−2 + · · · + a2 z 4 + a1 z 2 + a0 T 0 00000000 1 a 20 ... 9 8 7 6 5 3 4 0 1 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 01010101 2 a 41 40 ... 29 28 27 26 25 24 23 22 21 20 ... D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab 9 8 7 6 5 4 3 2 Implementação eficiente de ECC em sensores em fio 1 0 Multiplicação Karatsuba em F2m a(z)b(z) = a1b1z m +[(a1+a0)(b1+b0)+a1b1+a0b0]z m/2 +a0b0 a a1 a0 b b1 b0 a0b0 (a1 + a0)(b1 + b0) + a0b0 + a1b1 a1b1 c 41 40 ... 29 28 27 26 25 24 23 22 21 20 ... D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab 9 8 7 5 6 3 4 2 1 0 Implementação eficiente de ECC em sensores em fio Multiplicação López-Dahab em F2m T b 20 ... 9 8 7 6 5 4 3 2 1 0 0 a 20 ... 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 ... ... ... ... 7 8 9 4 10 11 12 13 D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab 9 8 7 ... 41 40 ... 29 28 27 26 25 24 23 22 21 20 ... ... ... ... c 6 5 4 3 2 14 1 0 Implementação eficiente de ECC em sensores em fio 15 Otimização proposta para Multiplicação López-Dahab T b 20 ... 9 8 7 6 5 4 3 2 1 0 0 a 20 ... 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 ... ... ... ... 7 8 9 4 10 11 12 13 D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab 9 8 7 ... 41 40 ... 29 28 27 26 25 24 23 22 21 20 ... ... ... ... c 6 5 4 3 2 14 1 0 Implementação eficiente de ECC em sensores em fio Análise da multiplicação em F2m Tabela: Custo em instruções dos algoritmos de multiplicação em F2m . Alg. LD LD reg. Karat+M Instruções em função do número de palavras n Leituras Escritas XOR 4n2 + 9n − 1 2t n + 2n2 + 6n − 2 2n2 + 13n 2n2 + 4n − 1 2t n + 5n − 1 2n2 + 11n 11n + 3M(n/2) 7n + 3M(n/2) 4n + 3M(n/2) Algoritmo López-Dahab LD com registradores Karatsuba+LD Karatsuba+LD com reg. Instruções em função Leituras Escritas 1952 1342 965 440 1977 1593 1086 837 D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab de n = 21 XOR 1155 1113 1239 1173 Implementação eficiente de ECC em sensores em fio 15 Redução modular Algoritmo 1 Redução rápida para f (z) = z 163 + z 7 + z 6 + z 3 + 1. Entrada: a(z) = a[0..2n − 1]. Saı́da: c(z) = a(z) mod f (z). 1: for i ← 41 to 21 do 2: t ← c[i] 3: c[i − 21] ← c[i − 21] ⊕ (t 5) 4: c[i − 20] ← c[i − 20] ⊕ (t 4) ⊕ (t 3) ⊕ t ⊕ (t 3) 5: c[i − 19] ← c[i − 19] ⊕ (t 4) ⊕ (t 5) 6: end for 7: t ← c[20] 3 8: c[0] ← c[0] ⊕ (t 7) ⊕ (t 6) ⊕ (t 3) ⊕ t 9: c[1] ← c[1] ⊕ (t 1) ⊕ ( 2) 10: c[20] ← c[20] & 0x07 11: return c D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Otimização para redução modular Algoritmo 2 Otimização proposta para redução modular rápida. Entrada: a(z) = a[0..2n − 1]. Saı́da: c(z) = a(z) mod f (z). 1: rb ← 0, rc ← 0 2: i ← 21, j ← 40 3: while i > 3 do 4: R(rb , rc , ra , c[j]), c[i] ← c[i] ⊕ rb 5: R(rc , ra , rb , c[j − 1]), c[i − 1] ← c[i − 1] ⊕ rc 6: R(ra , rb , rc , c[j − 2]), c[i − 2] ← c[i − 2] ⊕ ra 7: i ← i − 3, j ← j − 3 8: end while 9: R(rb , rc , ra , c[22]), c[3] ← c[3] ⊕ rb 10: R(rc , ra , rb , c[21]), c[2] ← c[2] ⊕ rc 11: c[1] ← c[1] ⊕ ra 12: c[0] ← c[0] ⊕ rb 13: return c D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Análise da redução modular em F2m Tabela: Custo em instruções dos algoritmos de redução modular. Algoritmo Original Otimização Instruções executadas Leituras Escritas 88 66 42 22 D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Inversão em F2m Duas alternativas: Algoritmo Estendido de Euclides; Modificação do Algoritmo de Quase Inverso. Segundo algoritmo executa apenas deslocamentos de 1 bit! D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Aritmética na curva elı́ptica A multiplicação de ponto foi implementada com os algoritmos: 4-TNAF em curvas de Koblitz; Método López-Dahab em curvas binárias genéricas. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Implementação Material: GCC 4.1.2 para ATMega128; MIRACL; AVR Simulator 4.14. Linguagens: C; Assembly. Curvas padronizadas: Curva de Koblitz sect163k1; Curva binária genérica sect163r2. D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Resultados Tabela: Custo dos algoritmos de aritmética em F2163 . Algoritmo Quadrado Mult. LD com reg. Mult. LD (variante) Mult. Karat+LD com reg. Redução Modular Inversão D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab C Ciclos 725 13838 9752 12246 621 365658 Assembly Ciclos 456 5433 9120 6968 609 231258 Ganho % 37 60 6 43 2 36 Implementação eficiente de ECC em sensores em fio Resultados Tabela: Custo da multiplicação de ponto. Algoritmo 4-TNAF na curva sect163k1 LD na curva sect163k1 LD na curva sect163r2 D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab C Tempo (s) 0.95 1.30 1.60 Assembly Tempo (s) 0.69 0.83 0.98 Ganho % 27 36 39 Implementação eficiente de ECC em sensores em fio Comparação - Eficiência Tabela: Comparação entre implementações distintas. Os tempos são fornecidos em quantidades de ciclos (c) ou segundos (s). Algoritmo Quadrado Multiplicação Redução Inversão 4-TNAF LD sect163k1 LD sect163r2 Proposta Linguagem C Assembly Tempo Ganho Tempo Ganho 725 c 12% 456 c 45% 9752 c 51% 5433 c 72% 621 c 67% 609 c 68% 365658 c 32% 231258 c 57% 0.95 s 17% 0.69 s 39% 1.30 s -12% 0.83 s 27% 1.60 s -29% 0.98 s 14% D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab TinyECCK C Tempo 825 c 19670 c 1904 c 539132 c 1.14 s – – Implementação eficiente de ECC em sensores em fio Comparação - Memória Tabela: Custo em bytes de memória para implementações distintas. 4-TNAF - versão C 4-TNAF - versão C+Assembly LD - versão C LD - versão C+Assembly TinyECCK D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Memória ROM 26668 32392 10714 16438 5592 Memória RAM 48 624 16 528 618 Implementação eficiente de ECC em sensores em fio Conclusões e Trabalhos Futuros Novo estado-da-arte para implementação de ECC em sensores: Implementação eficiente de aritmética no corpo F2163 : Implementações mais eficientes de quadrado, multiplicação e redução modular já publicadas para a plataforma; Implementação eficiente de criptografia de curvas elı́pticas: Multiplicação de ponto 39% mais rápida que a melhor implementação binária; Multiplicação de ponto 7% mais rápida que a melhor implementação prima. Trabalho futuro: implementação de emparelhamentos! D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Implementação eficiente de ECC em sensores em fio Conclusões Corpo Binário Primo Trabalho [Malan et al. 2004] [Yan and Shi 2006] [Eberle et al. 2005] [Szczechowiak et al. 2008] [Seo et al. 2008] Proposta [Wang and Li 2006] [Szczechowiak et al. 2008] [Gura et al. 2004] [Uhsadel et al. 2007] [GrobSchadl 2006] D. Aranha, D. Câmara, J. López, L. Oliveira, R. Dahab Tempo de execução (s) 34 13.9 4.14 2.16 1.14 0.69 1.35 1.27 0.81 0.76 0.745 Implementação eficiente de ECC em sensores em fio