Abstract
Optimal Prime Fields (OPFs) are considered to be one of the best choices for lightweight elliptic curve cryptography implementation on resource-constraint embedded processors. In this paper, we revisit efficient implementation of the modular arithmetic over the special prime fields, and present improved implementation of modular multiplication for OPFs, called Optimal Prime Field Coarsely Integrated Operand Caching (OPF-CIOC) method. OPF-CIOC method follows the general idea of (consecutive) operand caching technique, but has been carefully optimized and redesigned for Montgomery multiplication in an integrated fashion. We then evaluate the practical performance of proposed method on representative 8-bit AVR processor. Experimental results show that the proposed OPF-CIOC method outperforms the previous best known results in ACNS’14 by a factor of 5 %. Furthermore, our method is implemented in a regular way which helps to reduce the leakage of side-channel information.
This work was supported by the Industrial Strategic Technology Development Program (This work was supported by the ICT R&D program of MSIP/IITP. [10043907, Development of high performance IoT device and Open Platform with Intelligent Software]).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chu, D., Großschädl, J., Liu, Z., Müller, V., Zhang, Y.: Twisted edwards-form elliptic curve cryptography for 8-bit AVR-based sensor nodes. In: Proceedings of the first ACM workshop on Asia public-key cryptography, pp. 39–44. ACM (2013)
Comba, P.G.: Exponentiation cryptosystems on the IBM PC. IBM Syst. J. 29(4), 526–538 (1990)
Großschädl, J., Tinysa: A security architecture for wireless sensor networks. In: Proceedings of the 2006 ACM CoNEXT conference, p. 55. ACM (2006)
Großschädl, J., Hudler, M., Koschuch, M., Krüger, M., Szekely, A.: Smart elliptic curve cryptography for smart dust. In: Zhang, X., Qiao, D. (eds.) QShine 2010. LNICST, vol. 74, pp. 623–634. Springer, Heidelberg (2012)
Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 119–132. Springer, Heidelberg (2004)
Hankerson, D., Vanstone, S., Menezes, A.J.: Guide to Elliptic Curve Cryptography. Springer, New York (2004)
Hutter, M., Wenger, E.: Fast multi-precision multiplication for public-key cryptography on embedded microprocessors. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 459–474. Springer, Heidelberg (2011)
Koç, Ç.K., Acar, T., Kaliski Jr., B.S.: Analyzing and comparing montgomery multiplication algorithms. Micro IEEE 16(3), 26–33 (1996)
Liu, Z., Großschädl, J., Kizhvatov, I.: Efficient and side-channel resistant RSA implementation for 8-bit AVR microcontrollers. In: Proceedings of the 1st International Workshop on the Security of the Internet of Things (SECIOT 2010) (2010)
Liu, Z., Großschädl, J., Wong, D.S.: Low-weight primes for lightweight elliptic curve cryptography on 8-bit AVR processors. In: Lin, D., Xu, S., Yung, M. (eds.) The 9th China international Conference on Information Security and Cryptology–INSCRYPT 2013. LNCS. Springer, New York (2013)
Liu, Z., Großschädl, J.: New speed records for montgomery modular multiplication on 8-Bit AVR microcontrollers. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT. LNCS, vol. 8469, pp. 215–234. Springer, Heidelberg (2014)
Liu, Z., Seo, H., Großschädl, J., Kim, H.: Efficient implementation of NIST-compliant elliptic curve cryptography for sensor nodes. In: Qing, S., Zhou, J., Liu, D. (eds.) ICICS 2013. LNCS, vol. 8233, pp. 302–317. Springer, Heidelberg (2013)
Liu, Z., Wenger, E., Großschädl, J.: MoTE-ECC: energy-scalable elliptic curve cryptography for wireless sensor networks. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 361–379. Springer, Heidelberg (2014)
Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Scott, M.: Implementing cryptographic pairings. Lect. Notes Comput. Sci. 4575, 177 (2007)
Seo, H., Kim, H.: Multi-precision multiplication for public-key cryptography on embedded microprocessors. In: Lee, D.H., Yung, M. (eds.) WISA 2012. LNCS, vol. 7690, pp. 55–67. Springer, Heidelberg (2012)
Walter, C.D., Thompson, S.: Distinguishing exponent digits by observing modular subtractions. In: Topics in Cryptology CT RSA 2001, pp 192–207. Springer (2001)
Zhang, Y., Grossschadl, J.: Efficient prime-field arithmetic for elliptic curve cryptography on wireless sensor nodes. In: IEEE International Conference on Computer Science and Network Technology (ICCSNT), vol. 1, pp. 459–466 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Seo, H., Liu, Z., Nogami, Y., Choi, J., Kim, H. (2015). Improved Modular Multiplication for Optimal Prime Fields. In: Rhee, KH., Yi, J. (eds) Information Security Applications. WISA 2014. Lecture Notes in Computer Science(), vol 8909. Springer, Cham. https://doi.org/10.1007/978-3-319-15087-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-15087-1_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15086-4
Online ISBN: 978-3-319-15087-1
eBook Packages: Computer ScienceComputer Science (R0)