Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Parallel Implementation of SM2 Elliptic Curve Cryptography on Intel Processors with AVX2
Huang, Junhao; Liu, Zhe; Hu, Zhiet al.
2020 • In Liu, Joseph K.; Cui, Hui (Eds.) Information Security and Privacy, 25th Australasian Conference, ACISP 2020, Perth, WA, Australia, November 30 - December 2, 2020, Proceedings
Elliptic Curve Cryptography; SM2 Standard; Co- Z Jacobian Point Arithmetic; Prime-Field Arithmetic; Single Instruction Multiple Data (SIMD); Advanced Vector Extension 2 (AVX2)
Abstract :
[en] This paper presents an efficient and secure implementation of SM2, the Chinese elliptic curve cryptography standard that has been adopted by the International Organization of Standardization (ISO) as ISO/IEC 14888-3:2018. Our SM2 implementation uses Intel’s Advanced Vector Extensions version 2.0 (AVX2), a family of three-operand SIMD instructions operating on vectors of 8, 16, 32, or 64-bit data elements in 256-bit registers, and is resistant against timing attacks. To exploit the parallel processing capabilities of AVX2, we studied the execution flows of Co-Z Jacobian point arithmetic operations and introduce a parallel 2-way Co-Z addition, Co-Z conjugate addition, and Co-Z ladder algorithm, which allow for fast Co-Z scalar multiplication. Furthermore, we developed an efficient 2-way prime-field arithmetic library using AVX2 to support our Co-Z Jacobian point operations. Both the field and the point operations utilize branch-free (i.e. constant-time) implementation techniques, which increase their ability to resist Simple Power Analysis (SPA) and timing attacks. Our software for scalar multiplication on the SM2 curve is, to our knowledge, the first constant-time implementation of the Co-Z based ladder that leverages the parallelism of AVX2.
Disciplines :
Computer science
Author, co-author :
Huang, Junhao; Nanjing University of Aeronautics and Astronautics > College of Computer Science and Technology
Liu, Zhe; Nanjing University of Aeronautics and Astronautics > College of Computer Science and Technology ; State Key Laboratory of Cryptology
Hu, Zhi; Central South University
Groszschädl, Johann ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
External co-authors :
yes
Language :
English
Title :
Parallel Implementation of SM2 Elliptic Curve Cryptography on Intel Processors with AVX2
Publication date :
November 2020
Event name :
25th Australasian Conference on Information Security and Privacy (ACISP 2020)
Event place :
Perth, Australia
Event date :
from 30-11-2020 to 02-12-2020
Audience :
International
Main work title :
Information Security and Privacy, 25th Australasian Conference, ACISP 2020, Perth, WA, Australia, November 30 - December 2, 2020, Proceedings
Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 207– 228. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853 14
Bernstein, D.J., Schwabe, P.: NEON crypto. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 320–339. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8 19
Brier, É., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45664-3 24
Cabrera Aldaya, A., Cabrera Sarmiento, A.J., Sánchez-Solano, S.: SPA vulnerabilities of the binary extended Euclidean algorithm. J. Cryptogr. Eng. 7(4), 273–285 (2017). https://doi.org/10.1007/s13389-016-0135-4
Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation using mixed coordinates. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1 6
Faz-Hernández, A., López, J.: Fast implementation of curve25519 using AVX2. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 329–345. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8 18
Faz-Hernández, A., López, J., Dahab, R.: High-performance implementation of elliptic curve cryptography using vector instructions. ACM Trans. Math. Softw. 45(3), 1–35 (2019)
Fog, A.: Instruction tables: lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD, and VIA CPUs. Manual (2019). http://www.agner.org/optimize/instruction tables.pdf
Gueron, S., Krasnov, V.: Software implementation of modular exponentiation, using advanced vector instructions architectures. In: Özbudak, F., Rodríguez-Henríquez, F. (eds.) WAIFI 2012. LNCS, vol. 7369, pp. 119–135. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31662-3 9
Gueron, S., Krasnov, V.: Fast prime field elliptic-curve cryptography with 256-bit primes. J. Cryptogr. Eng. 5(2), 141–151 (2015). https://doi.org/10.1007/s13389-014-0090-x
Hankerson, D.R., Menezes, A.J., Vanstone, S.A.: Guide to Elliptic Curve Cryptography. Springer, New York (2004). https://doi.org/10.1007/b97644
Hutter, M., Joye, M., Sierra, Y.: Memory-constrained implementations of elliptic curve cryptography in co-Z coordinate representation. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 170–187. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21969-6 11
Intel Corporation: Intel instruction set architecture extensions. Documentation (2013). http://software.intel.com/en-us/isa-extensions
International Organization for Standardization: ISO/IEC 14888–3:2018-IT security techniques-Digital signatures with appendix-Part 3: Discrete logarithm based mechanisms (2018)
Izu, T., Takagi, T.: A fast parallel elliptic curve multiplication resistant against side channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 280–296. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45664-3 20
Peng, B.-Y., Hsu, Y.-C., Chen, Y.-J., Chueh, D.-C., Cheng, C.-M., Yang, B.-Y.: Multi-core FPGA implementation of ECC with homogeneous Co-Z coordinate representation. In: Foresti, S., Persiano, G. (eds.) CANS 2016. LNCS, vol. 10052, pp. 637–647. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48965-0 42
Rivain, M.: Fast and regular algorithms for scalar multiplication over elliptic curves. Cryptology ePrint Archive, Report 2011/338 (2011)
Seo, H., Liu, Z., Großschädl, J., Choi, J., Kim, H.: Montgomery modular multiplication on ARM-NEON revisited. In: Lee, J., Kim, J. (eds.) ICISC 2014. LNCS, vol. 8949, pp. 328–342. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15943-0 20
Solinas, J.A.: Generalized Mersenne numbers. Technical report CORR-99-39, University of Waterloo, Waterloo, Canada (1999)
State Cryptography Administration of China: Public key cryptographic algorithm SM2 based on elliptic curves. Specification (2010). http://www.sca.gov.cn/sca/xwdt/2010-12/17/content 1002386.shtml
State Cryptography Administration of China: Recommended curve parameters of public key cryptographic algorithm SM2 based on elliptic curves. Specification (2010). http://www.sca.gov.cn/sca/xwdt/2010-12/17/content 1002386.shtml
Venelli, A., Dassance, F.: Faster side-channel resistant elliptic curve scalar multiplication. In: Kohel, D., Rolland, R. (eds.) Contemporary Mathematics, vol. 512, pp. 29–40. American Mathematical Society (2010)
Zhao, Y., Pan, W., Lin, J., Liu, P., Xue, C., Zheng, F.: PhiRSA: exploiting the computing power of vector instructions on Intel Xeon Phi for RSA. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 482–500. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5 26
Zhou, L., Su, C., Hu, Z., Lee, S., Seo, H.: Lightweight implementations of NIST P-256 and SM2 ECC on 8-bit resource-constraint embedded device. ACM Trans. Embed. Comput. Syst. 18(3), 1–13 (2019)