›› 2016, Vol. 31 ›› Issue (2): 284-299.doi: 10.1007/s11390-016-1627-5

Special Issue: Surveys

• Theory and Algorithms • Previous Articles     Next Articles

A Synthesis of Multi-Precision Multiplication and Squaring Techniques for 8-Bit Sensor Nodes: State-of-the-Art Research and Future Challenges

Zhe Liu1, Hwajeong Seo2, and Howon Kim2, Member, IEEE   

  1. 1 Laboratory of Algorithmics, Cryptology and Security, University of Luxembourg, Kirchberg, L-1359, Luxembourg;
    2 School of Computer Science and Engineering, Pusan National University, Busan 609-735, Korea
  • Received:2014-06-10 Revised:2015-03-16 Online:2016-03-05 Published:2016-03-05
  • About author:Zhe Liu received his B.E. degree in software engineering from Shandong University, Jinan, with First Class Honors, M.S. degrees in computer science from University of Luxembourg and Shandong University in 2010 and 2011, respectively. Since 2011, he has been a Ph.D. student in the Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, Kirchberg. His research interests include computer arithmetics, with special focus on efficient implementation of public key cryptography (PKC) on wireless sensor networks (WSNs).
  • Supported by:

    This work has been supported by AFR (Aides `a la Formation-Recherche) Project of Luxembourg under Grant No. 1359142, MSIP (Ministry of Science, ICT and Future Planning) of Korea under the ITRC (Information Technology Research Center) Support Program under Grant No. NIPA-2014-H0301-14-1048 supervised by the NIPA (National IT Industry Promotion Agency) of Korea.

Multi-precision multiplication and squaring are the performance-critical operations for the implementation of public-key cryptography, such as exponentiation in RSA, and scalar multiplication in elliptic curve cryptography (ECC). In this paper, we provide a survey on the multi-precision multiplication and squaring techniques, and make special focus on the comparison of their performance and memory footprint on sensor nodes using 8-bit processors. Different from the previous work, our advantages are in at least three aspects. Firstly, this survey includes the existing techniques for multiprecision multiplication and squaring on sensor nodes over prime fields. Secondly, we analyze and evaluate each method in a systematic and objective way. Thirdly, this survey also provides suggestions for selecting appropriate multiplication and squaring techniques for concrete implementation of public-key cryptography. At the end of this survey, we propose the research challenges on efficient implementation of the multiplication and the squaring operations based on our observation.

[1] Uhsadel L, Poschmann A, Paar C. Enabling full-size publickey algorithms on 8-bit sensor nodes. In Proc. the 4th European Workshop on Security and Privacy in Ad-hoc and Sensor Networks, July 2007, pp.73-86.

[2] Watro R J, Kong D, Cuti S F, Gardiner C, Lynn C, Kruus P. TinyPK: Securing sensor networks with public key technology. In Proc. the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks, October 2004, pp.59-64.

[3] Liu A, Ning P. TinyECC: A configurable library for elliptic curve cryptography in wireless sensor networks. In Proc. the 7th International Conference on Information Processing in Sensor Networks, April 2008, pp.245-256.

[4] Hutter M, Schwabe P. NaCl on 8-bit AVR microcontrollers. In Proc. the 6th International Conference on Cryptology in Africa, June 2013, pp.156-172.

[5] Gura N, Patel A, Wander A S, Eberle H, Chang Shantz S. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Proc. the 6th International Workshop on Cryptographic Hardware and Embedded Systems, August 2004, pp.119-132.

[6] Hankerson D R, Menezes A J, Vanstone S A. Guide to Elliptic Curve Cryptography. New York, USA: Springer-Verlag, 2004.

[7] Großschädl J, Avanzi R M, Sav?s E, Tillich S. Energyefficient software implementation of long integer modular arithmetic. In Proc. the 7th International Workshop on Cryptographic Hardware and Embedded Systems, August 28-September 1,2005, pp.75-90.

[8] Knuth D E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition). Boston, MA, USA: Addison-Wesley, 1997.

[9] Comba P G. Exponentiation cryptosystems on the IBM PC. IBM Systems Journal, 1990, 29(4): 526-538.

[10] Karatsuba A A, Ofman Y P. Multiplication of multidigit numbers on automata. Soviet Physics — Doklady, 1963, 7: 595-596.

[11] Wang H, Li Q. Efficient implementation of public key cryptosystems on mote sensors. In Proc. the 8th International Conference on Information and Communications Security, December 2006, pp.519-528.

[12] Ugus O, Westhoff D, Laue R, Shoufan A, Huss S A. Optimized implementation of elliptic curve based additive homomorphic encryption for wireless sensor networks. In Proc. the 2nd Workshop on Embedded Systems Security, October 2007, pp.11-16.

[13] Szczechowiak P, Oliveira L B, Scott M, Collier M, Dahab R. NanoECC: Testing the limits of elliptic curve cryptography in sensor networks. In Proc. the 5th European Conference on Wireless Sensor Networks Wireless, January 30- February 1,2008, pp.305-320.

[14] Scott M, Szczechowiak P. Optimizing multiprecision multiplication for public key cryptography. Cryptology ePrint Archive, Report 2007/299, 2007. https://eprint.iacr.org/2007/299.pdf, August 2015.

[15] Lederer C, Mader R, Koschuch M, Großschädl J, Szekely A, Tillich S. Energy-efficient implementation of ECDH key exchange for wireless sensor networks. In Proc. the 3rd Workshop on Information Security Theory and Practice, September 2009, pp.112-127.

[16] Liu Z, Großschädl J, Kizhvatov I. Efficient and side-channel resistant RSA implementation for 8-bit AVR microcontrollers. In Proc. the 1st International Workshop on the Security of the Internet of Things, December 2010.

[17] Zhang Y, Großschädl J. Efficient prime-field arithmetic for elliptic curve cryptography on wireless sensor nodes. In Proc. the 2011 International Conference on Computer Science and Network Technology, December 2011, pp.459-466.

[18] Liu Z, Großschädl J. New speed records for Montgomery modular multiplication on 8-bit AVR microcontrollers. In Proc. the 7th International Conference on Cryptology in Africa, May 2014, pp.215-234.

[19] Hutter M,Wenger E. Fast multi-precision multiplication for public-key cryptography on embedded microprocessors. In Proc. the 13th International Workshop on Cryptographic Hardware and Embedded Systems, September 28-October 1,2011, pp.459-474.

[20] Seo H, Kim H. Multi-precision multiplication for publickey cryptography on embedded microprocessors. In Proc. the 13th International Workshop on Information Security Applications, August 2012, pp.55-67.

[21] Seo H, Kim H. Optimized multi-precision multiplication for public-key cryptography on embedded microprocessors. International Journal of Computer and Communication Engineering, 2013, 2(3): 255-259.

[22] Hutter M, Schwabe P. Multiprecision multiplication on AVR revisited. Cryptology ePrint Archive, Report 2014/592, 2014. https://eprint.iacr.org/2014/592, August 2015.

[23] Hsieh P Y, Laih C S. An exception handling model and its application to the multiple-precision integer library [Master Thesis]. Master of Science, Japan, December 2003.

[24] Lee Y, Kim I H, Park Y. Improved multi-precision squaring for low-end RISC microcontrollers. Journal of Systems and Software, 2013, 86(1): 60-71.

[25] Seo H, Liu Z, Choi J, Kim H. Multi-precision squaring for public-key cryptography on embedded microprocessors. In Proc. the 14th International Conference on Cryptology in India, December 2013, pp.227-243.

[26] Koç Ç K. High-speed RSA implementation. Technical Report, TR 201, RSA Laboratories, RSA Data Security, Inc., 1994. ftp://ftp.rsasecurity.com/pub/pdfs/tr201.pdf, August 2015.

[27] Kargl A, Pyka S, Seuschek H. Fast arithmetic on ATmega128 for elliptic curve cryptography. Cryptology ePrint Archive, Report 2008/442, 2008. https://eprint.iacr.org/2008/442.pdf, August 2015.

[28] Bernstein D J. Batch binary edwards. In Proc. the 29th International Cryptology Conference, August 2009, pp.317- 336.

[29] Montgomery P L. Modular multiplication without trial division. Mathematics of Computation, 1985, 44(170): 519-521.

[30] López J, Dahab R. High-speed software multiplication in F2m. In Proc. the 1st International Conference on Cryptology in India, December 2000, pp.203-212.

[31] Oliveira L B, Aranha D F, Gouvêa C P, Scott M, Câmara D F, López J, Dahab R. TinyPBC: Pairings for authenticated identity-based non-interactive key distribution in sensor networks. Computer Communications, 2011,34(3): 485-493.
No related articles found!
Full text



[1] Li Renwei;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[2] Song Maoqiang; Felix Grimm; Horst Bunke;. A Prototype Expert System for Automatic Generation of Image Processing Programs[J]. , 1991, 6(3): 296 -300 .
[3] Andrew I. Adamatzky;. Identification of Nonstationary Cellular Automata[J]. , 1992, 7(4): 379 -382 .
[4] Zhou Jianqiang; Xie Li; Dai Fei; Sun Zhongxiu;. Adaptive Memory Coherence Algorithms in DSVM[J]. , 1994, 9(4): 365 -372 .
[5] Xu Meihe; Tang Zesheng;. A Boundary Element Method for Simulation of Deformable Objects[J]. , 1996, 11(5): 497 -506 .
[6] wang Xuejun; Shi Chunyi;. A Multiagent Dynamic interaction Testbed:Theoretic Framework, System Architecture and Experimentation[J]. , 1997, 12(2): 121 -132 .
[7] Chen Yangjun;. Magic Sets Revisited[J]. , 1997, 12(4): 346 -365 .
[8] Sun Jizhou; Richard L;. A Radiosity Solution for Curved Surface Environments[J]. , 1997, 12(5): 414 -424 .
[9] Hao Ruibing; Wu Jianping;. A Formal Approach to Protocol Interoperability Testing[J]. , 1998, 13(1): 79 -90 .
[10] TING Jing'an;. A Neural Paradigm for Time-Varying Motion Segmentation[J]. , 1999, 14(6): 539 -550 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved