Skip to main content
Top

2017 | OriginalPaper | Chapter

Multi-precision Squaring for Public-Key Cryptography on Embedded Microprocessors, a Step Forward

Authors : Hwajeong Seo, Taehwan Park, Shinwook Heo, Gyuwon Seo, Bongjin Bae, Lu Zhou, Howon Kim

Published in: Information Security Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Multi-precision squaring is one of the most performance-critical operations for implementations of public-key cryptography, e.g. RSA, ECC as well as Diffie-Hellman key exchange protocols. In this paper, we propose novel techniques to push the speed limits of multi-precision squaring on embedded processors. The method reduces the number of memory access operations and improves the previous Sliding Block Doubling method by 4.1% on 8-bit RISC processor.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
Pseudo code of sliding middle block doubling is available in Appendix A, and the triangle form in 160-bit is depicted in Fig. 6 in Appendix B.
 
Literature
1.
go back to reference Comba, P.G.: Exponentiation cryptosystems on the IBM PC. IBM Syst. J. 29(4), 526–538 (1990)CrossRef Comba, P.G.: Exponentiation cryptosystems on the IBM PC. IBM Syst. J. 29(4), 526–538 (1990)CrossRef
2.
go back to reference 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). doi:10.1007/978-3-540-28632-5_9 CrossRef 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). doi:10.​1007/​978-3-540-28632-5_​9 CrossRef
3.
go back to reference Hill, J.L., Culler, D.E.: Mica: a wireless platform for deeply embedded networks. Micro IEEE 22(6), 12–24 (2002)CrossRef Hill, J.L., Culler, D.E.: Mica: a wireless platform for deeply embedded networks. Micro IEEE 22(6), 12–24 (2002)CrossRef
4.
go back to reference Hutter, M., Schwabe, P.: Multiprecision multiplication on AVR revisited. J. Cryptogr. Eng. 5(3), 201–214 (2015)CrossRef Hutter, M., Schwabe, P.: Multiprecision multiplication on AVR revisited. J. Cryptogr. Eng. 5(3), 201–214 (2015)CrossRef
5.
go back to reference 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). doi:10.1007/978-3-642-23951-9_30 CrossRef 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). doi:10.​1007/​978-3-642-23951-9_​30 CrossRef
6.
go back to reference Lee, Y., Kim, I.-H., Park, Y.: Improved multi-precision squaring for low-end RISC microcontrollers. J. Syst. Softw. 86(1), 60–71 (2013)CrossRef Lee, Y., Kim, I.-H., Park, Y.: Improved multi-precision squaring for low-end RISC microcontrollers. J. Syst. Softw. 86(1), 60–71 (2013)CrossRef
7.
go back to reference Liu, Z., Huang, X., Hu, Z., Khan, M.K., Seo, H., Zhou, L.: On emerging family of elliptic curves to secure Internet of Things: ECC comes of age (2016) Liu, Z., Huang, X., Hu, Z., Khan, M.K., Seo, H., Zhou, L.: On emerging family of elliptic curves to secure Internet of Things: ECC comes of age (2016)
8.
go back to reference 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, Cham (2013). doi:10.1007/978-3-319-02726-5_22 CrossRef 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, Cham (2013). doi:10.​1007/​978-3-319-02726-5_​22 CrossRef
9.
go back to reference Liu, Z., Seo, H., Großschädl, J., Kim, H.: Reverse product-scanning multiplication and squaring on 8-bit AVR processors. In: Hui, L.C.K., Qing, S.H., Shi, E., Yiu, S.M. (eds.) ICICS 2014. LNCS, vol. 8958, pp. 158–175. Springer, Cham (2015). doi:10.1007/978-3-319-21966-0_12 CrossRef Liu, Z., Seo, H., Großschädl, J., Kim, H.: Reverse product-scanning multiplication and squaring on 8-bit AVR processors. In: Hui, L.C.K., Qing, S.H., Shi, E., Yiu, S.M. (eds.) ICICS 2014. LNCS, vol. 8958, pp. 158–175. Springer, Cham (2015). doi:10.​1007/​978-3-319-21966-0_​12 CrossRef
10.
go back to reference Liu, Z., Seo, H., Großschädl, J., Kim, H.: Efficient implementation of NIST-compliant elliptic curve cryptography for 8-bit AVR-based sensor nodes. IEEE Trans. Inf. Forensics Secur. 11(7), 1385–1397 (2016)CrossRef Liu, Z., Seo, H., Großschädl, J., Kim, H.: Efficient implementation of NIST-compliant elliptic curve cryptography for 8-bit AVR-based sensor nodes. IEEE Trans. Inf. Forensics Secur. 11(7), 1385–1397 (2016)CrossRef
11.
go back to reference Liu, Z., Seo, H., Hu, Z., Hunag, X., Großschädl, J.: Efficient implementation of ECDH key exchange for MSP430-based wireless sensor networks. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, pp. 145–153. ACM (2015) Liu, Z., Seo, H., Hu, Z., Hunag, X., Großschädl, J.: Efficient implementation of ECDH key exchange for MSP430-based wireless sensor networks. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, pp. 145–153. ACM (2015)
12.
go back to reference Liu, Z., Seo, H., Kim, H.: A synthesis of multi-precision multiplication and squaring techniques for 8-bit sensor nodes: state-of-the-art research and future challenges. J. Comput. Sci. Technol. 31(2), 284–299 (2016)MathSciNetCrossRef Liu, Z., Seo, H., Kim, H.: A synthesis of multi-precision multiplication and squaring techniques for 8-bit sensor nodes: state-of-the-art research and future challenges. J. Comput. Sci. Technol. 31(2), 284–299 (2016)MathSciNetCrossRef
13.
go back to reference Liu, Z., Seo, H., Xu, Q.: Performance evaluation of twisted Edwards-form elliptic curve cryptography for wireless sensor nodes. Secur. Commun. Netw. 8(18), 3301–3310 (2015)CrossRef Liu, Z., Seo, H., Xu, Q.: Performance evaluation of twisted Edwards-form elliptic curve cryptography for wireless sensor nodes. Secur. Commun. Netw. 8(18), 3301–3310 (2015)CrossRef
14.
go back to reference Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press Series on Discrete Mathematics and Its Applications. CRC Press, Boca Raton (1996)CrossRefMATH Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press Series on Discrete Mathematics and Its Applications. CRC Press, Boca Raton (1996)CrossRefMATH
15.
go back to reference Schirra, S.: Robustness and precision issues in geometric computation. Max-Planck-Institut für Informatik (1998) Schirra, S.: Robustness and precision issues in geometric computation. Max-Planck-Institut für Informatik (1998)
16.
go back to reference Scott, M., Szczechowiak, P.: Optimizing multiprecision multiplication for public key cryptography. Cryptology ePrint Archive, report 2007/299 (2007). http://eprint.iacr.org Scott, M., Szczechowiak, P.: Optimizing multiprecision multiplication for public key cryptography. Cryptology ePrint Archive, report 2007/299 (2007). http://​eprint.​iacr.​org
17.
go back to reference 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). doi:10.1007/978-3-642-35416-8_5 CrossRef 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). doi:10.​1007/​978-3-642-35416-8_​5 CrossRef
18.
go back to reference Seo, H., Kim, H.: Implementation of multi-precision multiplication over sensor networks with efficient instructions. J. Inf. Commun. Converg. Eng. 11(1), 12–16 (2013) Seo, H., Kim, H.: Implementation of multi-precision multiplication over sensor networks with efficient instructions. J. Inf. Commun. Converg. Eng. 11(1), 12–16 (2013)
19.
go back to reference Seo, H., Kim, H.: Optimized multi-precision multiplication for public-key cryptography on embedded microprocessors. Int. J. Comput. Commun. Eng. 2(3), 255 (2013)CrossRef Seo, H., Kim, H.: Optimized multi-precision multiplication for public-key cryptography on embedded microprocessors. Int. J. Comput. Commun. Eng. 2(3), 255 (2013)CrossRef
20.
go back to reference Seo, H., Kim, H.: Multi-precision squaring on MSP and ARM processors. In: 2014 International Conference on Information and Communication Technology Convergence (ICTC), pp. 356–361. IEEE (2014) Seo, H., Kim, H.: Multi-precision squaring on MSP and ARM processors. In: 2014 International Conference on Information and Communication Technology Convergence (ICTC), pp. 356–361. IEEE (2014)
21.
go back to reference Seo, H., Kim, H.: Study of modular multiplication methods for embedded processors. J. Inf. Commun. Converg. Eng. 12(3), 145–153 (2014) Seo, H., Kim, H.: Study of modular multiplication methods for embedded processors. J. Inf. Commun. Converg. Eng. 12(3), 145–153 (2014)
22.
go back to reference Seo, H., Lee, Y., Kim, H., Park, T., Kim, H.: Binary and prime field multiplication for public key cryptography on embedded microprocessors. Secur. Commun. Netw. 7(4), 774–787 (2014)CrossRef Seo, H., Lee, Y., Kim, H., Park, T., Kim, H.: Binary and prime field multiplication for public key cryptography on embedded microprocessors. Secur. Commun. Netw. 7(4), 774–787 (2014)CrossRef
23.
go back to reference Seo, H., Liu, Z., Choi, J., Kim, H.: Multi-precision squaring for public-key cryptography on embedded microprocessors. In: Paul, G., Vaudenay, S. (eds.) INDOCRYPT 2013. LNCS, vol. 8250, pp. 227–243. Springer, Cham (2013). doi:10.1007/978-3-319-03515-4_15 CrossRef Seo, H., Liu, Z., Choi, J., Kim, H.: Multi-precision squaring for public-key cryptography on embedded microprocessors. In: Paul, G., Vaudenay, S. (eds.) INDOCRYPT 2013. LNCS, vol. 8250, pp. 227–243. Springer, Cham (2013). doi:10.​1007/​978-3-319-03515-4_​15 CrossRef
24.
go back to reference Seo, H., Liu, Z., Choi, J., Kim, H.: Optimized Karatsuba squaring on 8-bit AVR processors. Secur. Commun. Netw. 8(18), 3546–3554 (2015)CrossRef Seo, H., Liu, Z., Choi, J., Kim, H.: Optimized Karatsuba squaring on 8-bit AVR processors. Secur. Commun. Netw. 8(18), 3546–3554 (2015)CrossRef
25.
go back to reference Seo, H., Liu, Z., Nogami, Y., Choi, J., Kim, H.: Improved modular multiplication for optimal prime fields. In: Rhee, K.-H., Yi, J.H. (eds.) WISA 2014. LNCS, vol. 8909, pp. 150–161. Springer, Cham (2015). doi:10.1007/978-3-319-15087-1_12 Seo, H., Liu, Z., Nogami, Y., Choi, J., Kim, H.: Improved modular multiplication for optimal prime fields. In: Rhee, K.-H., Yi, J.H. (eds.) WISA 2014. LNCS, vol. 8909, pp. 150–161. Springer, Cham (2015). doi:10.​1007/​978-3-319-15087-1_​12
26.
go back to reference Seo, H., Liu, Z., Nogami, Y., Choi, J., Kim, H.: Montgomery multiplication and squaring for optimal prime fields. Comput. Secur. (2015) Seo, H., Liu, Z., Nogami, Y., Choi, J., Kim, H.: Montgomery multiplication and squaring for optimal prime fields. Comput. Secur. (2015)
27.
go back to reference Seo, H., Shim, K.-A., Kim, H.: Performance enhancement of TinyECC based on multiplication optimizations. Secur. Commun. Netw. 6(2), 151–160 (2013)CrossRef Seo, H., Shim, K.-A., Kim, H.: Performance enhancement of TinyECC based on multiplication optimizations. Secur. Commun. Netw. 6(2), 151–160 (2013)CrossRef
Metadata
Title
Multi-precision Squaring for Public-Key Cryptography on Embedded Microprocessors, a Step Forward
Authors
Hwajeong Seo
Taehwan Park
Shinwook Heo
Gyuwon Seo
Bongjin Bae
Lu Zhou
Howon Kim
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-56549-1_28

Premium Partner