Implementação eficiente de criptografia de curvas elípticas em sensores sem fio

• Diego Aranha UNICAMP
• Danilo Câmara UNICAMP
• Julio López UNICAMP
• Leonardo Oliveira UNICAMP
• Ricardo Dahab UNICAMP

DOI: https://doi.org/10.5753/sbseg.2008.20896

Abstract

The deployment of cryptography on sensor networks is a challenging task, given the limited computational power and resource-constrained nature of the sensoring devices. This paper presents the implementation of binary elliptic curves on the MICAz Mote. Optimization techniques for arithmetic algorithms on binary fields, including squaring, multiplication and modular reduction are presented. Our implementation of field multiplication and modular reduction algorithms focus on the minimization of memory accesses and appear as the most efficient algorithms published for this platform. This leads to an improvement of 39% over the best implementation for computing a point multiplication on a Koblitz curve. The results also show that binary elliptic curves can perform on this platform as well or better than elliptic curves defined over prime fields.

References

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.