Implementação eficiente em software de curvas elípticas e emparelhamentos bilineares

  • Diego F. Aranha UNICAMP
  • Julio López UNICAMP

Resumo


O advento da criptografia assimétrica ou de chave pública possibilitou a aplicação de criptografia na forma de assinaturas digitais e comércio eletrônico. Dentre os vários métodos de criptografia assimétrica, a Criptografia de Curvas Elípticas destaca-se pelos baixos requisitos de armazenamento e custo computacional para execução. A descoberta relativamente recente da criptografia baseada em emparelhamentos bilineares permitiu ainda sua flexibilização e a construção de sistemas criptográficos com propriedades inovadoras. Porém, o custo computacional de sistemas baseados em emparelhamentos ainda permanece significativamente superior aos tradicionais, representando um obstáculo para sua adoção, especialmente em dispositivos com recursos limitados. As contribuições deste trabalho objetivaram aprimorar o desempenho de sistemas baseados em curvas elípticas e emparelhamentos bilineares e consistem em formulação e implementação eficientes de aritmética em corpos finitos em diversas plataformas computacionais; técnicas algorítmicas seriais e paralelas para aritmética em curvas elípticas e cálculo de emparelhamentos de interesse criptográfico. Estas contribuições permitiram obter significativos ganhos de desempenho e uma série de recordes de velocidade para o cálculo de diversos algoritmos criptográficos relevantes em arquiteturas modernas que vão de sistemas embarcados de 8 bits a processadores com 8 cores.

Referências

W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22:644–654, November 1976.

N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of computation, 48:203–9, 1987.

V. Miller. Uses of Elliptic Curves in Cryptography. In H. C. Williams, editor, CRYPTO 85, volume 218 of LNCS, pages 417–426. Springer, 1985.

R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.

D. F. Aranha, D. Câmara, J. López, L. B. Oliveira, and R. Dahab. Implementação eficiente de criptografia de curvas elípticas em sensores sem fio. In SBSEG 2008, pages 173–186.

D. F. Aranha, J. López, L. B. Oliveira, and R. Dahab. Efficient implementation of elliptic curves on sensor nodes. In CHiLE 2009, 2009.

D. F. Aranha, L. B. Oliveira, J. López, and R. Dahab. Efficient implementation of elliptic curve cryptography in wireless sensors. Adv. Math. Comm., 4(2):169–187, 2010.

D. F. Aranha, J. López, and D. Hankerson. Efficient Software Implementation of Binary Field Arithmetic Using Vector Instruction Sets. In LATINCRYPT 2010, volume 6212 of LNCS, pages 144–161, 2010.

J. Taverne, A. Faz-Hernández, D. F. Aranha, F. Rodríguez-Henríquez, D. Hankerson, and J. López. Software implementation of binary elliptic curves: Impact of the carry-less multiplier on scalar multiplication. In CHES 2011, volume 6917 of LNCS, pages 108–123. Springer, 2011.

J. Taverne, A. Faz-Hernández, D. F. Aranha, F. Rodríguez-Henríquez, D. Hankerson, and J. López. Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction. J. Cryptographic Engineering, 1(3):187–199, 2011.

D. F. Aranha, L. B. Oliveira, J. López, and R. Dahab. NanoPBC: implementing cryptographic pairings on an 8-bit platform. In CHiLE 2009, 2009.

L. B. Oliveira, D. F. Aranha, C. P. L. Gouvêa, M. Scott, D. F. Câmara, J. López, and R. Dahab. TinyPBC: Pairings for Authenticated Identity-Based Non-Interactive Key Distribution in Sensor Networks. Computer Communications, 4(2):169–187, 2011.

L. B. Oliveira, A. Kansal, C. P. L. Gouvêa, D. F. Aranha, J. López, B. Priyantha, M. Goraczko, and F. Zhao. Secure-TWS: Authenticating Node to Multi-user Communication in Shared Sensor Networks. The Computer Journal, 2011. To appear.

V. S. Miller. The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology, 17(4):235–261, 2004.

D. F. Aranha and J. López. Paralelização em software do Algoritmo de Miller. In SBSEG 2009, pages 27–40, 2009.

D. F. Aranha, J. López, and D. Hankerson. High-Speed Parallel Software Implementation of the ηT Pairing. In SPEED-CC 2009, pages 73–88, 2009.

D. F. Aranha, J. López, and D. Hankerson. High-Speed Parallel Software Implementation of the ηT Pairing. In CT-RSA 2010, volume 5985 of LNCS, pages 89–105. Springer, 2010.

D. F. Aranha, J.-L. Beuchat, J. Detrey, and N. Estibals. Optimal eta pairing on supersingular genus-2 binary hyperelliptic curves. In O. Dunkelman, editor, CT-RSA 2012, volume 7178 of LNCS, pages 98–115. Springer, 2012.

D. F. Aranha, K. Karabina, P. Longa, C. H. Gebotys, and J. López. Faster Explicit Formulas for Computing Pairings over Ordinary Curves. In EUROCRYPT 2011, volume 6632 of LNCS, pages 48–68. Springer, 2010.

D. F. Aranha, A. Menezes, E. Knapp, and F. Rodríguez-Henríquez. Parallelizing the Weil and Tate Pairings. In IMACC 2011, volume 7089 of LNCS, pages 275–295, 2011.

D. F. Aranha and C. P. L. Gouvêa. RELIC is an Efficient LIbrary for Cryptography. [link].
Publicado
16/07/2012
ARANHA, Diego F.; LÓPEZ, Julio. Implementação eficiente em software de curvas elípticas e emparelhamentos bilineares. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 15. , 2012, Curitiba/PR. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2012 . p. 7-12. ISSN 2763-8820.