FFT enabled ECC for WSN nodes without hardware multiplier support

ECC is a popular cryptographic algorithm for key distribution in wireless sensor networks where power efficiency is desirable. A power efficient implementation of ECC without using hardware multiplier support was proposed earlier for wireless sensor nodes. The proposed implementation utilized the number theoretic transform to carry operands to the frequency domain, and conducted Montgomery multiplication, in addition to other finite field operations, in that domain. With this work, we perform in the frequency domain only polynomial multiplication and use the fast Fourier transform to carry operands between the time and frequency domains. Our ECC implementation over GF((213 − 1)13) on the MSP430 microcontroller implements multiplications without using a hardware multiplier. It achieves scalar multiplication with fixed and random points in only 0.89 s and 1.74 s, respectively. Our implementation achieves ECC point multiplication of fixed and random points 10% and 13% faster, and consuming 12% and 15% less energy, in comparison to the existing work.

PDF

___

[1] Baronti P, Pillai P, Chook VWC, Chessa S, Gotta A et al. Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards. Computer Communications 2007; 30 (7): 1655–1695. doi: 10.1016/j.comcom.2006.12.020
[2] Pottie GJ, Kaiser WJ. Wireless integrated network sensors. Communications of the ACM 2000; 43 (5): 51–58. doi: 10.1145/332833.332838
[3] Chong CY, Kumar SP. Sensor networks: evolution, opportunities, and challenges. Proceedings of the IEEE 2003; 91 (8): 1247–1256. doi: 10.1109/JPROC.2003.814918
[4] de Souza RWR, Moreira LR, Rodrigues JJ, Moreira RR, de Albuquerque VHC. Deploying wireless sensor networks– based smart grid for smart meters monitoring and control. International Journal of Communication Systems 2018; 31 (10): e3557. doi: 10.1002/dac.3557
[5] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey. Computer Networks 2008; 52 (12): 2292–2330. doi: 10.1016/j.comnet.2008.04.002
[6] Feng D, Jiang C, Lim G, Cimini LJ, Feng G et al. A survey of energy-efficient wireless communications. IEEE Communications Surveys & Tutorials 2013; 15 (1): 167–178. doi: 10.1109/SURV.2012.020212.00049
[7] Li M, Lou W, Ren K. Data security and privacy in wireless body area networks. IEEE Wireless Communications 2010; 17 (1): 51–58. doi: 10.1109/MWC.2010.5416350
[8] Chen X, Makki K, Yen K, Pissinou N. Sensor network security: a survey. IEEE Communications Surveys & Tutorials 2009; 11 (2): 52–73. doi: 10.1109/SURV.2009.090205
[9] Diffie W, Hellman ME. New directions in cryptography. IEEE Transactions on Information Theory 1976; 22 (6): 644–654. doi: 10.1109/TIT.1976.1055638
[10] Koblitz N. Elliptic curve cryptosystems. Mathematics of Computation 1987; 48: 203–209. doi: 10.1090/S0025- 5718-1987-0866109-5
[11] Miller VS. Use of elliptic curves in cryptography. In:Conference on the Theory and Application of Cryptographic Techniques (CRYPTO); Santa Barbara, California, USA; 1985. pp. 417–426.
[12] Liu Z, Großschädl J, Li L, Xu Q. Energy-efficient elliptic curve cryptography for MSP430-based wireless sensor nodes. In: Australasian Conference on Information Security and Privacy; Melbourne, Australia; 2016. pp. 94–112.
[13] Gülen U, Baktır S. Elliptic curve cryptography on constrained microcontrollers using frequency domain arithmetic. In: International Conference on Computational Science and Its Applications (ISCIS); Guimaraes, Portugal; 2014. pp. 493–506.
[14] Gouvêa CPL, Oliveira LB, López J. Efficient software implementation of public-key cryptography on sensor networks using the MSP430X microcontroller. Journal of Cryptographic Engineering 2012; 2 (1): 19–29. doi: 10.1007/s13389- 012-0029-z
[15] Szczechowiak P, Oliveira LB, Scott M, Collier M, Dahab R. NanoECC: Testing the limits of elliptic curve cryptography in sensor networks. In: Wireless Sensor Networks (EWSN); Bologna, Italy; 2008. pp. 305–320.
[16] Gulen U, Baktir S. Elliptic-curve cryptography for wireless sensor network nodes without hardware multiplier support. Security and Communication Networks 2016; 9 (18): 4992–5002. doi: 10.1002/sec.1670
[17] MSP430x11x2, MSP430x12x2 Mixed Signal Microcontroller Datasheet, Texas Instrument Incorporated, 2004.
[18] MSP430F22x2, MSP430F22x4 Mixed Signal Microcontroller Datasheet, Texas Instrument Incorporated, 2012.
[19] MSP430G2x55 Mixed Signal Microcontroller Datasheet, Texas Instrument Incorporated, 2013.
[20] WiSense WSN1120L Datasheet, WiSense Technologies Private Limited, 2019.
[21] WiSense WSN1120CL Datasheet, WiSense Technologies Private Limited, 2019.
[22] WiSense WSN1101ANL Datasheet, WiSense Technologies Private Limited, 2019.
[23] WiSense WSN1101ACL Datasheet, WiSense Technologies Private Limited, 2019.
[24] eZ430-RF2500 Development Tool User’s Guide, Texas Instrument Incorporated, 2015.
[25] Adu-Manu K S, Adam N, Tapparello C, Ayatollahi H, Heinzelman W. Energy-Harvesting Wireless Sensor Networks (EH-WSNs): A Review. ACM Trans. Sen. Netw. 2018; 14 (2): 10. doi: 10.1145/3183338
[26] Bailey DV, Paar C. Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. Journal of Cryptology 2001; 14 (3): 153–176. doi: 10.1007/s001450010012
[27] Baktır S, Sunar B. Finite field polynomial multiplication in the frequency domain with application to elliptic curve cryptography. In: International Symposium on Computer and Information Sciences (ISCIS); Istanbul, Turkey; 2006. pp. 991–1001.
[28] Baktır S, Kumar S, Paar C, Sunar B. A state-of-the-art elliptic curve cryptographic processor operating in the frequency domain. Mobile Networks and Applications 2007; 12 (4): 259–270. doi: 10.1007/s11036-007-0022-4
[29] Montgomery PL. Modular multiplication without trial division. Mathematics of Computation 1985; 44 (170): 519–521. doi: 10.1090/S0025-5718-1985-0777282-X
[30] Cooley JW, Tukey JW. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 1965; 19 (90): 297–301. doi: 10.2307/2003354
[31] Hankerson D, Menezes AJ, Vanstone S. Guide to Elliptic Curve Cryptography. Secaucus, NJ, USA: Springer-Verlag New York, 2004.
[32] Mentens N, Batina L, Baktır S. An elliptic curve cryptographic processor using Edwards curves and the number theoretic transform. In: International Conference on Cryptography and Information Security in the Balkans (BalkanCryptSec); Istanbul, Turkey; 2014. pp. 94–102.
[33] McEliece RJ. Finite Fields for Computer Scientists and Engineers. Norwel, MA, USA: Kluwer Academic Publishers, 2003.
[34] Lidl R, Niederreiter H. Introduction to Finite Fields and their Applications. Cambridge, UK: Cambridge University Press, 1994.
[35] Pollard JM. The fast Fourier transform in a finite field. Mathematics of Computation 1971; 25: 365–374. doi: 10.1090/S0025-5718-1971-0301966-0
[36] Baktır S. Frequency domain finite field arithmetic for elliptic curve cryptography. PhD, Worcester Polytechnic Institute, Massachusetts, USA, 2008.
[37] Baktır S, Sunar B. Optimal extension field inversion in the frequency domain. In: International Workshop on the Arithmetic of Finite Fields (WAIFI); Siena, Italy; 2008. pp. 47–61.
[38] Rader CM. Discrete convolutions via Mersenne transforms. IEEE Transactions on Computers 1972; C-21(12): 1269–1273. doi: 10.1109/T-C.1972.223497
[39] Gulen U, Baktir S. Elliptic curve cryptography for wireless sensor networks using the number theoretic transform. Sensors 2020; 20 (5): 1507. doi: 10.3390/s20051507
[40] Edwards HM. A normal form for elliptic curves. Bulletin of the American Mathematical Society 2007; 44 (3): 393–422. doi: 10.1090/S0273-0979-07-01153-6
[41] Bernstein DJ, Lange T. Faster addition and doubling on elliptic curves. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT); Kuching, Sarawak, Malaysia; 2007. pp. 29-50.
[42] MSP430x1xx Family User’s Guide, Texas Instruments Incorporated, 2006.
[43] MSP430FG4618/F2013 Experimenter’s Board User’s Guide, Texas Instruments Incorporated, 2018.
[44] MSP Debuggers User’s Guide, Texas Instruments Incorporated, 2020.