Software Implementation Of Pairing-based Cryptography On Sensor Networks Using The Msp430 Microcontroller

The software implementation of cryptographic schemes for wireless sensor networks poses a challenge due to the limited capabilites of the platform. Nevertheless, its feasibility has been shown in recent papers. In this work we describe a software implementation of pairing-based cryptography and elliptic curve cryptography for the MSP430 microcontroller, which is used in some wireless sensors including the Tmote Sky and TelosB. We have implemented the pairing computation for the MNT and BN curves over prime fields along with the ECDSA scheme. The main result of this work is a platform-specific optimization for the multiplication and reduction routines that leads to a 28% speedup in the field multiplication compared to the best known timings published. This optimization consequently improves the speed of both pairing computation and point multiplication. © 2009 Springer-Verlag.5922 LNCS248262Comba, P., Exponentiation cryptosystems on the IBM PC (1990) IBM Systems Journal, 29 (4), pp. 526-538Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.: Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, 3156, pp. 925-943. Springer, Heidelberg (2004)Scott, M., Szczechowiak, P.: Optimizing multiprecision multiplication for public key cryptography. Cryptology ePrint Archive, Report 2007/299 (2007), http://eprint.iacr.org/Großschädl, J., Instruction Set Extension for Long Integer Modulo Arithmetic on RISC-Based Smart Cards (2002) Symposium on Computer Architecture and High Performance Computing, pp. 13-19Szczechowiak, P., Kargl, A., Scott, M., Collier, M., On the application of pairing based cryptography to wireless sensor networks (2009) Proceedings of the second ACM conference on Wireless network security, pp. 1-12. , ACM, New YorkMontgomery, P., Modular multiplication without trial division (1985) Mathematics of computation, 44 (170), pp. 519-521Barrett, P., Implementing the rivest shamir and adleman public key encryption algorithm on a standard digital signal processor (1987) LNCS, 263, pp. 311-323. , Odlyzko, A.M, ed, CRYPTO 1986, Springer, Heidelberg(2006) SEC 2: Recommended Elliptic Curve Domain Parameters, , http://www.secg.org, Certicom ResearchMenezes, A., Van Oorschot, P., Vanstone, S., (1997) Handbook of Applied Cryptography, , CRC Press, Boca Raton(2009) FIPS 186-3: Digital Signature Standard, , http://www.itl.nist.gov, DSSHankerson, D., Vanstone, S., Menezes, A., (2004) Guide to Elliptic Curve Cryptography, , Springer, HeidelbergOliveira, L., Aranha, D., Morais, E., Daguano, F., Lopez, J., Dahab, R.: TinyTate: computing the tate pairing in resource-constrained sensor nodes. In: Sixth IEEE International Symposium on Network Computing and Applications, NCA 2007, pp. 318-323 (2007)Sakai, R., Ohgishi, K., Kasahara, M., Cryptosystems based on pairing (2000) The 2000 Symposium on Cryptography and Information Security, , Okinawa, JapanDupont, R., Enge, A., Provably secure non-interactive key distribution based on pairings (2006) Discrete Applied Mathematics, 154 (2), pp. 270-276Oliveira, L., Scott, M., Lopez, J., Dahab, R., TinyPBC: Pairings for authenticated identity-based non-interactive key distribution in sensor networks (2008) 5th International Conference on Networked Sensing Systems, INSS, pp. 173-180Lenstra, A.K., Key Lengths (2004) Handbook of Information Security, , John Wiley & Sons, ChichesterLenstra, A., Verheul, E., Selecting Cryptographic Key Sizes (2001) Journal of Cryptology, 14 (4), pp. 255-293Barreto, P., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, 3897, pp. 319-331. Springer, Heidelberg (2006)Nogami, Y., Akane, M., Sakemi, Y., Kato, H., Morikawa, Y.: Integer Variable χ-Based Ate Pairing. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, 5209, pp. 178-191. Springer, Heidelberg (2008)Devegili, A., Scott, M., Dahab, R.: Implementing Cryptographic Pairings over Barreto-Naehrig Curves. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, 4575, pp. 197-207. Springer, Heidelberg (2007)Vercauteren, F., Optimal pairings. Cryptology ePrint Archive (2008), http://eprint.iacr.org, Report 2008/096Lee, E., Lee, H.S., Park, C.M., Efficient and generalized pairing computation on abelian varieties. Cryptology ePrint Archive (2008), http://eprint.iacr.org, Report 2008/040Scott, M., Benger, N., Charlemagne, M., Perez, L.J.D., Kachisa, E.J., On the final exponentiation for calculating pairings on ordinary elliptic curves. Cryptology ePrint Archive (2008), http://eprint.iacr.org, Report 2008/490Galbraith, S., Paterson, K., Smart, N., Pairings for cryptographers (2008) Discrete Applied Mathematics, 156 (16), pp. 3113-3121Wang, H., Li, Q., Efficient Implementation of Public Key Cryptosystems on Mote Sensors (Short Paper) (2006) LNCS, 4307, pp. 519-528. , Ning, P, Qing, S, Li, N, eds, ICICS 2006, Springer, HeidelbergMontgomery, P., Speeding the Pollard and elliptic curve methods of factorization (1987) Mathematics of Computation, 48 (177), pp. 243-264Szczechowiak, P., Oliveira, L., Scott, M., Collier, M., Dahab, R.: NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks. In: Verdone, R. (ed.) EWSN 2008. LNCS, 4913, pp. 305-320. Springer, Heidelberg (2008)Fan, J., Vercauteren, F., Verbauwhede, I.: Faster Fp-arithmetic for Cryptographic Pairings on Barreto-Naehrig Curves. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, 5747, pp. 240-253. Springer, Heidelberg (2009