Implementação eficiente de criptografia de curvas elípticas em sensores sem fio
Resumo
O emprego de criptografia em redes de sensores é desafiante, dado o baixo poder computacional e os recursos limitados dos dispositivos de sensoriamento. Este trabalho apresenta a implementação de curvas elípticas binárias em dispositivos MICAz. São apresentadas técnicas de otimização para algoritmos de aritmética em corpos binários, incluindo cálculo de quadrado, multiplicação e redução modular. Os algoritmos de multiplicação e redução modular resultantes minimizam a quantidade de acessos à memória e se mostram como os algoritmos mais eficientes para a plataforma escolhida já publicados. A eficiência destes algoritmos culmina em uma multiplicação de ponto com desempenho superior em até 39% à melhor implementação conhecida para corpos binários para o mesmo nível de segurança. Os resultados também mostram que curvas definidas sobre corpos binários podem ter desempenho idêntico ou superior nesta plataforma a curvas definidas sobre corpos primos.Referências
Atmel Corporation (2005). AVR Studio 4.14. http://www.atmel.com/.
Eberle, H., Wander, A., Gura, N., Chang-Shantz, S., and Gupta, V. (2005). Architectural Extensions for Elliptic Curve Cryptography over GF(2m) on 8-bit Microprocessors. In Proceedings of ASAP ’05, pages 343–349, Washington, DC, USA. IEEE.
Estrin, D., Govindan, R., Heidemann, J. S., and Kumar, S. (1999). Next century challenges: Scalable coordination in sensor networks. In Mobile Computing and Networking (MobiCom’99), pages 263–270, Seattle, WA USA.
Großschädl, J. (2006). TinySA: a security architecture for wireless sensor networks. In Proceedings of CoNEXT ’06, New York, NY, USA. ACM.
Gura, N., Patel, A., Wander, A., Eberle, H., and Shantz, S. C. (2004). Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. In Proc. of CHES’04, pages 119–132.
Hankerson, D., López, J., and Menezes, A. (2000). Software Implementation of Elliptic Curve Cryptography over Binary Fields. In Proceedings of CHES ’00, pages 1–24. Springer-Verlag.
Hankerson, D., Menezes, A. J., and Vanstone, S. (2003). Guide to Elliptic Curve Cryptography. Springer-Verlag, Secaucus, NJ, USA.
Hill, J. L. and Culler, D. E. (2002). MICA: A Wireless Platform for Deeply Embedded Networks. IEEE Micro, 22(6):12–24.
Karlof, C., Sastry, N., and Wagner, D. (2004). TinySec: A link layer security architecture for wireless sensor networks. In 2nd ACM SenSys, pages 162–175.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48:203–9.
López, J. and Dahab, R. (2000). High-speed software multiplication in GF(2m). In INDOCRYPT ’00, pages 203–212.
López, J. and Dahab, R. (1999a). Fast Multiplication on Elliptic Curves over GF(2m) without Precomputation. In Proceedings of CHES ’99, pages 316–327, London, UK. Springer-Verlag.
López, J. and Dahab, R. (1999b). Improved algorithms for elliptic curve arithmetic in GF(2n). In SAC ’98, pages 201–212, London, UK. Springer-Verlag.
Malan, D. J., Welsh, M., and Smith, M. D. (2004). A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography. In Proceedings of SECON’04, Santa Clara, California.
Miller, V. (1986). Uses of elliptic curves in cryptography, Advances in Cryptology. In Crypto’85, Lecture Notes in Computer Science, volume 218, pages 417–426. Springer.
Perrig, A., Szewczyk, R., Wen, V., Culler, D., and Tygar, J. D. (2002). SPINS: Security protocols for sensor networks. Wireless Networks, 8(5):521–534.
Scott, M. (2008). MIRACL – Multiprecision Integer and Rational Arithmetic C/C++ Library. http://www.shamus.ie/.
SECG (2000). SEC 2: Recommended Elliptic Curve Domain Parameters. http://www.secg.org.
Seo, S. C., Han, D.-G., and Hong, S. (2008). TinyECCK: Efficient Elliptic Curve Cryptography Implementation over GF(2m) on 8-bit MICAz Mote. Cryptology ePrint Archive, Report 2008/122. http://eprint.iacr.org/.
Solinas, J. A. (2000). Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, 19(2-3):195–249.
Szczechowiak, P., Oliveira, L. B., Scott, M., Collier, M., and Dahab, R. (2008). NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks. In Verdone, R., editor, EWSN, volume 4913 of LNCS, pages 305–320. Springer.
Uhsadel, L., Poschmann, A., and Paar, C. (2007). Enabling Full-Size Public-Key Algorithms on 8-Bit Sensor Nodes. In Proceedings of ESAS ’07, pages 73–86.
Wang, H. and Li, Q. (2006). Efficient Implementation of Public Key Cryptosystems on Mote Sensors. In Proceedings of ICICS’06, LNCS 4307, pages 519–528, Raleigh, NC.
Watro, R. J., Kong, D., fen Cuti, S., Gardiner, C., Lynn, C., and Kruus, P. (2004). TinyPK: securing sensor networks with public key technology. In Proceedings of SASN’04, pages 59–64, Washington, DC.
Yan, H. and Shi, Z. J. (2006). Studying Software Implementations of Elliptic Curve Cryptography. In Proceedings of ITNG ’06, pages 78–83, Washington, USA. IEEE.
Eberle, H., Wander, A., Gura, N., Chang-Shantz, S., and Gupta, V. (2005). Architectural Extensions for Elliptic Curve Cryptography over GF(2m) on 8-bit Microprocessors. In Proceedings of ASAP ’05, pages 343–349, Washington, DC, USA. IEEE.
Estrin, D., Govindan, R., Heidemann, J. S., and Kumar, S. (1999). Next century challenges: Scalable coordination in sensor networks. In Mobile Computing and Networking (MobiCom’99), pages 263–270, Seattle, WA USA.
Großschädl, J. (2006). TinySA: a security architecture for wireless sensor networks. In Proceedings of CoNEXT ’06, New York, NY, USA. ACM.
Gura, N., Patel, A., Wander, A., Eberle, H., and Shantz, S. C. (2004). Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. In Proc. of CHES’04, pages 119–132.
Hankerson, D., López, J., and Menezes, A. (2000). Software Implementation of Elliptic Curve Cryptography over Binary Fields. In Proceedings of CHES ’00, pages 1–24. Springer-Verlag.
Hankerson, D., Menezes, A. J., and Vanstone, S. (2003). Guide to Elliptic Curve Cryptography. Springer-Verlag, Secaucus, NJ, USA.
Hill, J. L. and Culler, D. E. (2002). MICA: A Wireless Platform for Deeply Embedded Networks. IEEE Micro, 22(6):12–24.
Karlof, C., Sastry, N., and Wagner, D. (2004). TinySec: A link layer security architecture for wireless sensor networks. In 2nd ACM SenSys, pages 162–175.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48:203–9.
López, J. and Dahab, R. (2000). High-speed software multiplication in GF(2m). In INDOCRYPT ’00, pages 203–212.
López, J. and Dahab, R. (1999a). Fast Multiplication on Elliptic Curves over GF(2m) without Precomputation. In Proceedings of CHES ’99, pages 316–327, London, UK. Springer-Verlag.
López, J. and Dahab, R. (1999b). Improved algorithms for elliptic curve arithmetic in GF(2n). In SAC ’98, pages 201–212, London, UK. Springer-Verlag.
Malan, D. J., Welsh, M., and Smith, M. D. (2004). A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography. In Proceedings of SECON’04, Santa Clara, California.
Miller, V. (1986). Uses of elliptic curves in cryptography, Advances in Cryptology. In Crypto’85, Lecture Notes in Computer Science, volume 218, pages 417–426. Springer.
Perrig, A., Szewczyk, R., Wen, V., Culler, D., and Tygar, J. D. (2002). SPINS: Security protocols for sensor networks. Wireless Networks, 8(5):521–534.
Scott, M. (2008). MIRACL – Multiprecision Integer and Rational Arithmetic C/C++ Library. http://www.shamus.ie/.
SECG (2000). SEC 2: Recommended Elliptic Curve Domain Parameters. http://www.secg.org.
Seo, S. C., Han, D.-G., and Hong, S. (2008). TinyECCK: Efficient Elliptic Curve Cryptography Implementation over GF(2m) on 8-bit MICAz Mote. Cryptology ePrint Archive, Report 2008/122. http://eprint.iacr.org/.
Solinas, J. A. (2000). Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, 19(2-3):195–249.
Szczechowiak, P., Oliveira, L. B., Scott, M., Collier, M., and Dahab, R. (2008). NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks. In Verdone, R., editor, EWSN, volume 4913 of LNCS, pages 305–320. Springer.
Uhsadel, L., Poschmann, A., and Paar, C. (2007). Enabling Full-Size Public-Key Algorithms on 8-Bit Sensor Nodes. In Proceedings of ESAS ’07, pages 73–86.
Wang, H. and Li, Q. (2006). Efficient Implementation of Public Key Cryptosystems on Mote Sensors. In Proceedings of ICICS’06, LNCS 4307, pages 519–528, Raleigh, NC.
Watro, R. J., Kong, D., fen Cuti, S., Gardiner, C., Lynn, C., and Kruus, P. (2004). TinyPK: securing sensor networks with public key technology. In Proceedings of SASN’04, pages 59–64, Washington, DC.
Yan, H. and Shi, Z. J. (2006). Studying Software Implementations of Elliptic Curve Cryptography. In Proceedings of ITNG ’06, pages 78–83, Washington, USA. IEEE.
Publicado
01/09/2008
Como Citar
ARANHA, Diego; CÂMARA, Danilo; LÓPEZ, Julio; OLIVEIRA, Leonardo; DAHAB, Ricardo.
Implementação eficiente de criptografia de curvas elípticas em sensores sem fio. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 8. , 2008, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 173-186.
DOI: https://doi.org/10.5753/sbseg.2008.20896.
